フィボナッチ数列の最大公約数について

Codeforces#140「Anniversary」で出てきた

(Fib(x), Fib(y)) = Fib((x, y))

を簡単に導出してみようと思います。

隣り合うフィボナッチ数は互いに素

隣り合うフィボナッチ数が互いに素ではなかったと仮定します。そのとき、

(Fib(x), Fib(x+1)) = d, d>0
となるようなdが存在します。このとき、フィボナッチ数の定義より、

Fib(x-1) = Fib(x+1) - Fib(x)
なので、d | Fib(x-1) となります。これを繰り返すと、d| Fib(1)となりますがこれはFib(1) = 1と矛盾します。 よって背理法より、隣り合うフィボナッチ数は互いに素となります。

フィボナッチ数の加法定理

x>2,   y>1について、

Fib(x+y) = Fib(x)Fib(y+1) + Fib(x-1)Fib(y)

という性質が成り立ちます。数学的帰納法を使うと証明できるそうですが、ここでは簡単に上の定理が正しいことを説明します。

Fib(x)は階段を１段ずつ、または１段飛ばしで登っていき、x段目に辿り着いたときの上り方のパターン数と考えることができます。Fib(x+y)はx+y段目まで登るとき（最下段からx+y-1段登ったとき）のパターン数です。
最下段からx+y-1段登るときのパターン数を、x段目を通るか通らないかに場合分けすると、

(x+y-1段登るときのパターン数)
= (x段目を通るパターン数) + (x段目を通らないパターン数)
= (x-1段登ったあと、y段登るパターン) + (x-2段登った後、1段飛ばしをして、y-1段登るパターン)
= (x-1段登るパターン数 * y段登るパターン数) + (x-2段登るパターン数 * y-1段登るパターン数)

ということで、まさにこれが加法定理と同じです。

(Fib(x), Fib(y)) = Fib((x,y))

さて、いよいよ目的の定理を考えます。まずは、Fib(x)とFib(x+y)の最大公約数を考えてみます。

(Fib(x), Fib(x+y))
= (Fib(x), Fib(x)Fib(y+1) + Fib(x-1)Fib(y))     (∵加法定理より)
= (Fib(x), Fib(x-1)Fib(y))     (∵ Fib(x) | Fib(x)Fib(y+1)より)
= (Fib(x), Fib(y))     (∵ (Fib(x), Fib(x-1)) = 1より)

はい、来ました。 (Fib(x), Fib(x+y)) = (Fib(x), Fib(y))
です。これを再帰的に繰り替えしていくとユークリッドの互除法（の引き算バージョン）によって、

(Fib(x), Fib(x+y)) = Fib((x, x+y))

となります。よって、目的の定理が成り立ちます。

Codeforces #139 Unsolvable

問題概要

z = [x/2] + y + xy, z > 0
を満たす正の整数x, yが存在しないようなzのうち、n番目に小さなものをMOD 1000000007で答えよ。ただし、[a]はaの整数部を表す。

方針

こういう数論系の問題は好きです。Editorialのように式変形していくと、メルセンヌ素数と関連する値になることがわかります。

ソースコード

const long long MOD = 1000000007LL;
int mers[] = {
    2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607,
    1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941,
    11213, 19937, 21701, 23209, 44497, 86243, 
    110503, 132049, 216091, 756839, 859433,
    1257787, 1398269, 2976221, 3021377, 6972593,
    13466917, 20996011, 24036583
};

int main() {
    int n;

    cin >> n;
    int x = mers[n-1];
    long long ret = 1;

    REP(i, x-1) {
        ret <<= 1;
        ret %= MOD;
    }

    cout << (ret+MOD-1)%MOD << endl;
    
    return 0;
}

おまけ

2^p - 1が素数となるためには、pは素数でなくてはいけません。1023とかパッと見、素数っぽいですが、2^10 - 1で10は素数ではないため、1023は素数ではありません。
いや、、こんなことしなくても、1023は3で割れることが一目瞭然なので、素数じゃないのは明らかか。。

Codeforces #139 Snake

問題概要

蛇がN*Mサイズのブロックを動き回る。りんごに辿り着くまでに蛇が移動しなければならない最小移動数を求めよ。

方針

（蛇の頭の座標、蛇の体部の相対座標）を状態数にしてBFSする。この「相対座標を状態数にとる」という発想はおもしろいと思いました。各部位について、相対座標は2bitで表現します。蛇の体部は最大で8つの部位から成り立っているので、全体として2^16あれば頭以外の部分の位置を表現できます。

ソースコード

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

typedef pair<int, pair<int, int> > pii;

const int INF = 1<<30;
int r,c;
string bd[16];
int vis[16][16][1<<16];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
vector<pii> snake;

struct status {
    int x;     // x of snake's head
    int y;     // y of snake's head
    int dir;   // directions of snake's body
};

int getDir(int sx, int sy, int tx, int ty) {
    if (sy == ty) {
        if (sx < tx) return 0;
        return 2;
    }
    else {
        if (sy < ty) return 3;
        return 1;
    }
    return -1;
}

bool hitBody(int x, int y, int dir) {
    int hx = x;
    int hy = y;

    int N = snake.size();
    int mask = (N-2)*2;
    FOR (i, 1, N) {
        int d = dir >> mask & 3;

        if (d == 0) ++x;
        else if (d == 1) --y;
        else if (d == 2) --x;
        else ++y;
                 
        if (x == hx && y == hy)
            return true;

        mask -= 2;
    }
    return false;
}

int main() {
    cin >> r >> c;
    REP(i, r) cin >> bd[i];
    
    REP(i, r) REP(j, c) if ('1' <= bd[i][j] && bd[i][j] <= '9') {
        snake.push_back(make_pair(bd[i][j]-'0', make_pair(i, j)));
    }

    sort(snake.begin(), snake.end());
    int dir = 0;
    FOR (i, 1, snake.size()) {
        dir <<= 2;
        pair<int, int> p1 = snake[i-1].second;
        pair<int, int> p2 = snake[i].second;

        dir += getDir(p1.first, p1.second, p2.first, p2.second);
    }

    int ret = -1;
    queue<status> q;
    pair<int, int> head = snake[0].second;
    q.push((status){head.first, head.second, dir});
    memset(vis, -1, sizeof(vis));
    vis[head.first][head.second][dir] = 0;

    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int dir = q.front().dir;
        
        if (bd[x][y] == '@') {
            ret = vis[x][y][dir];
            break;
        }

        q.pop();
        
        REP(k, 4) {
            int xx = x + dx[k];
            int yy = y + dy[k];

            if (xx < 0 || xx >= r) continue;
            if (yy < 0 || yy >= c) continue;
            if (bd[xx][yy] == '#') continue;

            int dir_t = dir >> 2;
            dir_t += getDir(xx, yy, x, y) << 2 * (snake.size()-2);
            if (hitBody(xx, yy, dir_t)) continue;
            
            if (vis[xx][yy][dir_t] == -1) {
                vis[xx][yy][dir_t] = vis[x][y][dir] + 1;
                q.push((status){xx, yy, dir_t});
            }
        }
    }

    cout << ret << endl;

    return 0;
}

JSONView

Google Chromeに「JSONView」を入れました。これで、ブラウザから綺麗にインデントされたJSONを見ることができます。日本語もエスケープされていない状態で表示されます。

インストールは以下のページで「ADD TO CHROME」を押すだけです。

https://chrome.google.com/webstore/detail/chklaanhfefbnpoihckbnefhakgolnmc

便利すぎる。もっと早く入れておけばよかった。。

gitチートシート

自分用メモ。

glossary

• working tree: 実際にローカルで編集しているリソース
• staging area(index): コミットする予定のリソースを格納する場所
• local repository: 自分のPCにあるレポジトリ
• remote repository: リモートにあるレポジトリ
• HEAD: 最新のコミット

checkout

• hoge.txtをindexの状態に戻す。→git checkout hoge.txt
• カレントディレクトリ配下をindexの状態に戻す。→git checkout .
• hoge.txtをHEADの状態に戻す。→git checkout HEAD hoge.txt

commit

• 直前のコミットを修正する。（ログのコメントも修正可）→git commit --amend

config

• デフォルトのエディタを変更する。→ git config --global core.editor emacs

diff

• 空白文字の変量を無視して差分を取る。→ git diff -b
• working treeとindexの差分をとる。 → git diff
• working treeとHEADの差分を取る。→ git diff HEAD
• working treeと1つ前のコミットの差分を取る。→git diff HEAD^
• indexとHEADの差分を取る。→git diff --cached
• 色を付けてdiffを見やすくする。→git diff --color
• ファイルの内容は表示せず、ファイル名のみ表示する。→ git diff --name-only

reset

• 直前のコミットを取り消す。（working treeには何もしない）→ git reset --soft HEAD^
• 直前のコミットを取り消す。（working treeの内容もHEAD^の状態に戻す）→ git reset --hard HEAD^

Codeforces Round #136 (Div. 2)

結果

ひさびさにプロコンに参加した。最近は(Java, Eclipse)ばっかりだったので、(C++, Emacs)でうまく書けるか不安だったが思ったより鬼は黒くなかった。 3/5AC、160位/1925人だった。（配列の最大要素数をミスってて問題DはRuntime Errorで死んでいた。それがなかったら20位くらいだった。もったいない。）

　問題D、Eがおもしろかった。解答は以下のとおり。

D. Little Elephant and Array

[l, r]区間に現れる回数がちょうどxとなるような正の整数xの個数を求める問題(1 <= l <= r <= n)。xの候補となるような正の整数はたかだか√n個程度になることに気付くかどうかがポイント。[1, y]区間にそれぞれのxが何回現れるかをメモリ上に保持すると(1 <= y <= n)、1クエリーがO(√n)で捌ける。

using namespace std;

const int MAX_LEN = (int)1e5;

int xs[MAX_LEN];
int nums[500][MAX_LEN+1];

int main() {
    int n, m;
    cin >> n >> m;
    
    map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        cin >> xs[i];
        cnt[xs[i]]++;
    }
    
    vector<int> vs;
    for (map<int, int>::iterator itr = cnt.begin(); itr != cnt.end(); itr++) {
        if (itr->second >= itr->first)
            vs.push_back(itr->first);
    }
    
    int l = vs.size();
    memset(nums, 0, sizeof(nums));
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < n; j++) {
            nums[i][j+1] = nums[i][j];
            if (vs[i] == xs[j])
                nums[i][j+1]++;
        }
    }
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        
        int ret = 0;
        for (int j = 0; j < l; j++) {
            if (nums[j][b] - nums[j][a-1] == vs[j])
                ++ret;
        }
        cout << ret << endl;
    }
    
    return 0;
}

E. Little Elephant and Shifts

長さnの順列a, bが与えられる。bのn個の巡回シフト集合に対して、それとaの距離を求める。2つの順列の距離は、 minimum |i - j|, that ai = bjと定義される。multisetをうまく使うと解ける。multisetまでは分かったんだけど、lower_bound使うってのが閃かなかった。データ構造の使い方を問う良問。

using namespace std;

#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)

int main() {
    int N;
    cin >> N;

    vector<int> a(N);
    vector<int> b(N);

    REP(i, N) cin >> a[i];
    REP(i, N) cin >> b[i];

    vector<int> x(N);
    vector<int> y(N);

    // set postions of a[i] and b[i]
    REP(i, N) x[--a[i]] = i;
    REP(i, N) y[--b[i]] = i;
    
    multiset<int> dis;
    REP(i, N) dis.insert(y[i]-x[i]);
    
    REP(k, N) {
        int ret = 0x7fffffff;
        __typeof(dis.begin()) itr = dis.lower_bound(k);
        ret = min(ret, *itr-k);
        if (itr != dis.begin())
            ret = min(ret, abs((*--itr)-k));
        cout << ret << endl;
        int head = b[k];
        dis.erase(dis.find(y[head]-x[head]));
        dis.insert(N-1-x[head]+k+1);
    }

    return 0;
}