Search on the blog

2012年9月28日金曜日

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

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)は階段を1段ずつ、または1段飛ばしで登っていき、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))
となります。よって、目的の定理が成り立ちます。

2012年9月24日月曜日

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;
}

2012年9月22日土曜日

JSONView

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

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



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

2012年9月9日日曜日

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^

2012年9月1日土曜日

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;
}

デザインパターン(7) Builder

まえおき
以下の書籍でBuilderパターンについて勉強した。


まとめ
  • 構造を持ったインスタンスを組み上げるときに利用する。
  • Builder、ConcreteBuilder、Director、Clientによって構成される。
疑問点
  • Builderパターンはオブジェクト生成のためのデザインパターン。Factory Methodパターンと何が違うのか?
Factory Methodパターンは異なる種類のオブジェクトを生成するときのパターンで、Builderパターンはオブジェクトの生成手順をきれいにまとめるためのパターンなので、目的がまったく違う。以下のような記述が参考サイト[1]にあった。
The rule of thumb I noticed after some time was the following: Consider a restaurant. The creation of "Todays Meal" is a factory pattern, because you tell the kitchen "get me todays meal" and the kitchen/factory decides what object to generate. based on hidden critereas.

The builder appears if you ordered a custom pizza. In this case, the waiter tells the chef/builder "I need a pizza, add cheese, cheese, onions and bacon to it!". Thus, the builder exposes what attributes the generated object should have, but hides how to set them.
  • パッと見、Template Methodパターンと同じに見えるんだけど、何が違うのか?
これは明確な違いが自分ではよく分からなかった。Builderパターンの方が抽象度や独立性が高いような気がする。Template Methodパターンだと親-子クラスという関係があるし、同じ部品を別の処理フローでテンプレート化したいときに処理フローの数だけ親-子のペアを毎回書かないといけないような気がする。それに比べて、Builderパターンの方はdirector-builder間の関係が移譲なのでそれぞれの独立性が高いのかなと思う。参考サイト[2]になんとなくしっくりくるような説明があった。

Template method is really just a way to define some methods that each subclass must define.

The builder pattern is used to construct a more complex object.

Lets say that we want to construct different Saab (car brand) models. Each model has different engines,lights etc.

If we were to use the template method pattern we had to create one class for each single combination of cars or use some nasty inheritance hierarchies. A lot of those methods would also contain duplicate code.

With the build pattern we can instead take different parts and compose those together to a complete car. Hence we can reuse a engine for every model if needed and we can also customize each part of the car.

その他
  • 書籍の練習問題がおもしろかった。久しぶりにswingでGUIを書いた。今度簡単なゲームか何か書いてみようかな。
参考サイト
  1. When would you use the Builder Pattern? [closed]
  2. Differences between builder pattern vs template method