通学路（動的計画法）

void calc(void)
{
    int t[17][17] = {};
    for (int j=1;j <= a;j++) {
        for (int k=1;k <= b;k++) {
            if (j==1 && k==1)
                t[k][j] = 1;
            else if (point[k][j] == 1)
                t[k][j] = 0;
            else
                t[k][j] = t[k][j-1] + t[k-1][j];
        }
    }
    m = t[b][a];
}

mainはさっきの記事と同じ

動的計画法ってよく出てくるんですけど、使いこなせていないのが現実orz

数学的な思考が足りてませんかそうですか

再帰の場合は計算量が抜群に増えていきますが、動的計画法ではそれほど気になりません。

5番目の一番大きい入力ファイルで時間を測ってみたところ

再帰　：　500ミリ秒

動的　：　0ミリ秒

圧倒的といえば圧倒的ですね。

5番目のファイルの先頭を16 16から19 19に変更するとさらに差が広がります。再帰だと10秒以上かかりますが、動的計画法だと数ミリ秒で終わります。この差はデカイ！

通学路には

誰も知らない秘密なんたらかんたら。誰の歌だっけ？

JOI 2006-2007 予選　問題6


いかにも高校生らしい問題ですねコレ。昔は無理やり数えてテストで回答したことがありました（笑）

相変わらず自分の中に無理矢理さは残っているようです

ソース短いので載せときます

#include <iostream>

int point[17][17];
int a, b, m, n;

void calc(int x=1, int y=1)
{
    if (x == a && y == b) {
        m++;
        return;
    }
    if (point[y][x+1] != 1 && x+1 <= a)
        calc(x+1, y);
    if (point[y+1][x] != 1 && y+1 <= b)
        calc(x, y+1);
}

int main()
{
    int x, y;

    cin >> a >> b;
    cin >> n;
    for (int i=0;i < n;i++) {
        cin >> x >> y;
        point[y][x] = 1;
    }
    calc();
    cout << m << endl;

    return 0;
}



とりあえず、いちばんわかりやすい方法でしょうね。強引に解くってのは。

縦横それぞれ最大16ってのと、入力ファイルが上手い具合に作られてるので5番目の入力ファイルでも時間はほとんどかかりません。

intとかlongの上限が42億程度（unsigned指定）なので、それほど計算量がかかる経路は作れないはず

まぁ、スマートな方法とは言えません。再帰はすっきり書けるけどね

解説の方では

・二重forループ（DPっぽい）

・再帰

・全数調査

の3つが挙げられてますね。DPのやってみようかしら

情報オリンピック

JOI 2006-2007 予選　問題５　品質検査

のるむさん に教えてもらった情報オリンピックの予選問題を解くことに

大体問題番号が進むにつれ難しくなっていくのですが、ACM-ICPCの問題よりは簡単ですね。

（そりゃ高校生のためのコンテストですからorz）

問題の内容としては、いくつかのテストケースの結果を用いて各パーツの良不良を答えなさい。というシンプルなものです

自分の考えとしては

（1）上手くいったケース（r=1）の時は、そのケースのパーツは良品で確定

（2）良品が2つあるがr=0の時は、残りの一つのパーツが不良品で確定

（3）他のパーツは不良品かどうかわからないことにする

の3ステップを踏んでやりましたが、解答し終えたあとに解説をみたら同じような内容でした

2^a+b+c通りの組み合わせを考えて強引に解く方法もあるみたいですが、2のべき乗で計算量が増えるので、現実時間内に解くのは無理でしょうね。最後の入力ファイルは a = b = c = 100 だし。

メモ：

基本的に入力はパイプで

diff <自分の回答ファイル> <公式ページの解答ファイル>

で何も出なけりゃOK！

日本一の大学

アルゴリズムとデータ構造

東京大学の講義資料、２年生のやつらしい

B問題は基本できる（と思う、見た感じは）

Aは解けないやつもあると思う（スパムフィルタはちょっと・・・）

さて、Fラン大の一学生がどこまで出来るでしょうかね

電話帳

電話帳の登録件数の少なさでは定評がある俺ですorz

学校の課題で出たのが、基本情報技術者試験の問題をちょっと変えたやつだったそうです。

確かにちょっといつもの課題とは毛色が違った感じがしたわけよ

電話帳クラスを作れって話なんですが、

メンバ関数は

・新規登録

・削除

・検索

・初期化←いずれコンストラクタを扱うときに直すんだろうなぁ・・・ｗ

＋α

・番号にハイフンを付ける

・一覧表示

・登録件数の確認

etc

んでメンバ変数は適当に。

とりあえず上に書いたやつはできたので、並べ替えるやつくらい追加して完成にしちゃおうかな～