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