第10回日本情報オリンピック予選 (2010-2011)

去年なぜか問題3を全部落として，満点を逃したのが悔しかったので，本選に出られないのを承知で参加した．

結果から言うと惨敗だった．

結果

問題6以外はすべて答えを提出．
問題6は解法が思い浮かばず，全探索で1つだけ提出．
よって，点数は

max	min
104	0

こんな感じ．

はじめの4問は短時間で解けたので，最後の問題が解けなかったのがすごく悔しい．来年またs（ry

問題5は，Segmentation fault を起こしている原因がなかなかつかめず，30分ぐらいかかった．残りは，問題6を考えるのに使った．

解法概略

問題1

足し算，割り算，剰余が出せれば大勝利．

問題2

文字列が扱えるか否かの勝負．
C++のくせに，charの配列を使って解いたのは内緒．
あとで与えられる文字列の先頭をずらしながら，先頭から比較．

問題3

剰余を使いましょう．
全部埋めながら確かめると，計算量が大きくなります．1辺が1000以下のテストケースについてしか解けません．(圧倒的に時間がたりない．)

問題4

DP(動的計画法).
テストケースの時点で，DPができていないと解けない．
現在みている数字の番号と，現在の数値についてDP．

問題5

幅優先探索．
JOI予選では初めて見た．単に古いのをやっていないだけなのかもしれない．
S→1→2→...→ n の順でしかたどれない．(問題文から明らか．)
Sを0とみて，iに0 〜 n-1 まで整数を代入し， 'i' と 'i+1' の最短距離の総和を出せば勝利．BFSは苦手なので，少し時間がかかった．

問題6

JOIerによるとビットDPらしい．
数値の制限的にそうかな〜とか思ってたけど結局解法はわからず．
再帰を使って無理やり解くと4点．
前の列(行)のどの位置で，J,O,Iのどれを使っていたか見るDPで12点．
．．．という予想は立てた．
来週末にでも再びチャレンジする．

ソースコードは恥ずかしいので今のところは公開しないです．
解答が全部あっていると確認が取れた上で気持ち体裁を整えupします．
僕が上げなくても，他の人達の素敵なソースが挙げられていると思います．