読者です 読者をやめる 読者になる 読者になる

第9回日本情報オリンピック予選 解説ソースつくってみた

C++での解答例。

問題1

/*
 * JOI 2010 予選 問題1 C++解答例 by qnighy
 */

// 問題:
// レシート
// http://www.ioi-jp.org/joi/2009/2010-yo-prob_and_sol/2010-yo-t1/2010-yo-t1.html

// 豆知識:
// iostreamは遅いので、僕はstdio.hを使っています。
// cstdioはC++用のstdio.hです。
#include <cstdio>

using namespace std;

int main(int argc, char **argv)
{
    int s = 0;
    for(int i = 0; i < 10; ++i) {
        // scanfを二回書きたくなかったので、合計額とレシートの両方をここでスキャンしています。
        int n;
        scanf("%d", &n);
        i == 0 ? (s+=n) : (s-=n);
    }
    printf("%d\n", s);
    return 0;
}

問題2

/*
 * JOI 2010 予選 問題2 C++解答例 by qnighy
 */

// 問題:
// すごろく
// http://www.ioi-jp.org/joi/2009/2010-yo-prob_and_sol/2010-yo-t2/2010-yo-t2.html

#include <cstdio>

using namespace std;

//すごろくのマス情報
int tbl[1010];
int main(int argc, char **argv)
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &tbl[i]);
    }
    int cur = 0;
    for(int i = 0; i < m; ++i) {
        int t;
        scanf("%d", &t);
        // さいころによる移動
        cur += t;
        if(cur >= n-1) {
            printf("%d\n", i+1);
            return 0;
        }
        // マス目の指示による移動
        cur += tbl[cur];
        // こっちのif文を書き忘れると4点減点。116点の人は多かったようです。
        if(cur >= n-1) {
            printf("%d\n", i+1);
            return 0;
        }
    }
    return 0;
}

問題3

/*
 * JOI 2010 予選 問題3 C++解答例 by qnighy
 */

// 問題:
// パーティー
// http://www.ioi-jp.org/joi/2009/2010-yo-prob_and_sol/2010-yo-t3/2010-yo-t3.html

#include <cstdio>
// memsetを使うのでincludeしてます
#include <cstring>

using namespace std;

// 2人は友人関係にあるかどうか
bool mat[500][500];
// >>1さんの友達や友達の友達かどうかのフラグ
bool flags[500];

int main(int argc, char **argv)
{
    // 初期化
    memset(mat, 0, sizeof(mat));
    memset(flags, 0, sizeof(flags));
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i) {
        int a,b;
        scanf("%d%d", &a, &b);
        // ここでは0スタートの番号にしたいので1ひいてる
        // 両方向のフラグを立てることに注意
        mat[a-1][b-1]=mat[b-1][a-1]=true;
    }
    for(int i = 0; i < n; ++i) {
        if(mat[0][i]) {
            // 友達フラグ
            flags[i] = true;
            for(int j = 0; j < n; ++j) {
                if(mat[i][j]) {
                    // 友達の友達フラグ
                    flags[j] = true;
                }
            }
        }
    }
    // 自分は除外
    // 友達の友達が自分だったりするので
    flags[0] = false;
    // 数えて出力
    int cnt = 0;
    for(int i = 0; i < n; ++i) {
        if(flags[i])cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

問題4

/*
 * JOI 2010 予選 問題4 C++解答例 by qnighy
 */

// 問題:
// カード並べ
// http://www.ioi-jp.org/joi/2009/2010-yo-prob_and_sol/2010-yo-t4/2010-yo-t4.html

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n,k;
// できた数字を全て記録
int a[10000];
// 記録している数字の個数
int i;
// 使えるカードn枚
int cards[10];
// 現在そのカードを使っているかどうか
bool cuse[10];
// 再帰
// 左からカードを並べる
// numは現在の数字、dは並べた枚数
void search(int num, int d) {
    // 既にk枚並べていたら、その数字を配列に追加
    if(d == k) {
        a[i++] = num;
        return;
    }
    // まだk枚並べていないとき
    for(int j = 0; j < n; ++j) {
        // そのカードをまだ使っていなかったら
        if(!cuse[j]) {
            // そのカードを使って、d+1枚にする
            cuse[j]=true;
            search(
                    // 10未満だったら
                    // ex)  197[9] = 197*10 + 9
                    // 10以上だったら
                    // ex)  197[17] = 197*100 + 17
                    cards[j]<10 ? (num*10+cards[j]) : (num*100+cards[j])
                    , d+1);
            // そのカードを外して、次のカードを試す
            cuse[j]=false;
        }
    }
}

int main(int argc, char **argv)
{
    scanf("%d%d", &n, &k);
    for(int j = 0; j < n; ++j) {
        scanf("%d", &cards[j]);
    }
    // 初期化
    i = 0;
    memset(cuse, 0, sizeof(cuse));
    // ありうる数字を全て列挙
    search(0, 0);
    // 数字を小さいものから順に並べる
    sort(&a[0], &a[i]);
    // 異なる数の個数を数える
    int prev = -1;
    int cnt = 0;
    for(int j = 0; j < i; ++j) {
        // 直前の数と違うなら、カウント
        if(prev != a[j]) cnt++;
        prev = a[j];
    }
    printf("%d\n", cnt);
    return 0;
}

問題5

/*
 * JOI 2010 予選 問題5 C++解答例 by qnighy
 */

// 問題:
// 通勤経路
// http://www.ioi-jp.org/joi/2009/2010-yo-prob_and_sol/2010-yo-t5/2010-yo-t5.html

#include <cstdio>

using namespace std;

// 剰余計算を簡単に書くためのクラス
// intと同じように使える
template<int m>
class mint
{
private:
    int i;
public:
    mint() : i(0){}
    mint(int i): i((i%m+m)%m){}
    mint operator+(const mint& o){return o.i+i;}
    mint operator*(const mint& o){return o.i*i;}
    mint operator-(){return -i;}
    operator int() {return i;}
};

// mmint a; とか宣言すると、勝手に剰余計算してくれる
typedef mint<100000> mmint;

// ある交差点に辿りつく組みあわせ
// 正確には、
// tbl[x][y][0] 直進の結果、交差点(x,y)に西から辿りつく道の数
// tbl[x][y][1] 直進の結果、交差点(x,y)に南から辿りつく道の数
mmint tbl[100][100][2];
// このようなtblは、以下のように漸化式を組みたてられる。
// ・最初は西にも南にも進めるので、
//     交差点(0,1)に南から辿りつく道は1通り
//     交差点(1,0)に西から辿りつく道は1通り
// ・その他の場合、ある交差点に直進の結果辿りつくには
//     その交差点で直進する
//     その交差点で曲がった後直進する
//   の2通りが考えられる。
// ・最終的に交差点(w-1,h-1)に辿りつくには
//     最後に直進する
//     最後に直進してから曲がる
//   の2通りが考えられる。
//
// この漸化式を計算する。

int main(int argc, char **argv)
{
    int w,h;
    scanf("%d%d", &w, &h);
    for(int x = 0; x < w; ++x) {
        for(int y = 0;y < h; ++y) {
            mmint a = x-1>=0 ? tbl[x-1][y][0] : (mmint)0;
            mmint b = x-2>=0 ? tbl[x-2][y][1] : (mmint)0;
            mmint c = y-1>=0 ? tbl[x][y-1][1] : (mmint)0;
            mmint d = y-2>=0 ? tbl[x][y-2][0] : (mmint)0;
            tbl[x][y][0] = a+b;
            tbl[x][y][1] = c+d;
            if(x==1 && y==0) {
                tbl[x][y][0] = 1;
                tbl[x][y][1] = 0;
            } else if(x==0 && y==1) {
                tbl[x][y][0] = 0;
                tbl[x][y][1] = 1;
            }
        }
    }
    mmint sum = tbl[w-1][h-1][0] + tbl[w-1][h-1][1] +
        tbl[w-1][h-2][0] + tbl[w-2][h-1][1];
    printf("%d\n", (int)sum);
    return 0;
}

問題6

/*
 * JOI 2010 予選 問題6 C++解答例 by qnighy
 */

// 問題:
// 方向音痴のトナカイ
// http://www.ioi-jp.org/joi/2009/2010-yo-prob_and_sol/2010-yo-t6/2010-yo-t6.html

#include <cstdio>
#include <cstring>
// mallocつかったので
#include <cstdlib>

using namespace std;

int w,h;
// 地図
int tbl[10][10];
// 家番号の逆引き
int htbl[10][10];
/* int dp[1<<24][24];*/
// ↑だとプログラムサイズがヤバいので、mallocを使う方法に変更↓
int (*dp)[24];
// 家の位置
int hxs[24];
int hys[24];
int main(int argc, char **argv)
{
    scanf("%d%d", &w, &h);
    // 家の数(教会含む)
    int hcnt = 1;
    for(int y = 0; y < h; ++y) {
        for(int x = 0; x < w; ++x) {
            scanf("%d", &tbl[x][y]);
            htbl[x][y] = -1;
            if(tbl[x][y] == 1) {
                htbl[x][y] = hcnt++;
                hxs[htbl[x][y]]=x;
                hys[htbl[x][y]]=y;
            } else if(tbl[x][y] == 2) {
                // 教会の家番号は0
                htbl[x][y] = 0;
                hxs[htbl[x][y]]=x;
                hys[htbl[x][y]]=y;
            }
        }
    }
    // dp[訪問状態][現在位置の家番号]
    //   その状態に至る道順の数を記憶する
    //   dp[X][Y]な状態からdp[X'][Y']な状態へと移動できるとき
    //   dp[X'][Y'] += dp[X][Y] とすることで、道順を計算できる
    // 訪問状態は↓で解説
    dp = (int(*)[24])malloc(sizeof(*dp)*(1<<hcnt));
    memset(dp, 0, sizeof(*dp)*(1<<hcnt));
    dp[0][0] = 1;
    // state(訪問状態)は、それぞれの家について、訪問済みフラグを保持する
    // stateの下からNビット目は、家番号Nの家が訪問済みなら1となる
    // N番目が訪問済みかどうかは、ビット演算でstate&(1<<N)とやればわかる
    // ここでは、0から(1<<hcnt)、つまり全ての訪問状態についてループを回す。
    // また、この順番が重要。
    // 例えば、B,Cに訪問済みの状態は、B,C,Dに訪問済みの状態より先に処理される。
    for(int state = 0; state < (1<<hcnt); ++state) {
        // curは現在位置
        for(int cur = 0; cur < hcnt; ++cur) {
            // 現在位置なのに訪問していない状態はありえないので飛ばす
            // ただし、初期位置(教会)だけは例外
            if(!(state==0 && cur==0) && (state&(1<<cur)) == 0)continue;
            int x=hxs[cur];
            int y=hys[cur];
            // 東西南北に進める範囲を調べる
            for(int i = 1; x+i<w ; ++i) {
                int htcur=htbl[x+i][y];
                // 訪問済みなら探索をやめる
                if(htcur>=0 && state&(1<<htcur))break;
                // 未訪問の家なら、今の状態から次の状態へ組みあわせを加算
                if(htcur>=0)dp[state|(1<<htcur)][htcur] += dp[state][cur];
            }
            for(int i = 1; x-i>=0 ; ++i) {
                int htcur=htbl[x-i][y];
                if(htcur>=0 && state&(1<<htcur))break;
                if(htcur>=0)dp[state|(1<<htcur)][htcur] += dp[state][cur];
            }
            for(int i = 1; y+i<h ; ++i) {
                int htcur=htbl[x][y+i];
                if(htcur>=0 && state&(1<<htcur))break;
                if(htcur>=0)dp[state|(1<<htcur)][htcur] += dp[state][cur];
            }
            for(int i = 1; y-i>=0 ; ++i) {
                int htcur=htbl[x][y-i];
                if(htcur>=0 && state&(1<<htcur))break;
                if(htcur>=0)dp[state|(1<<htcur)][htcur] += dp[state][cur];
            }
        }
    }
    // 「全ての家に訪問済みで、最後に教会に到着した」パターンを調べる
    printf("%d\n",dp[(1<<hcnt)-1][0]);
    free(dp);
    return 0;
}