ICPC 2006 国内予選

ICPC

7位きたーーーー！！！国内予選としては過去最高順位ですよ．去年の台北大会に並ぶ7位．ただ今回はもうちょっと行けたかもしれない．とりあえずSFCにも勝てて京大にも勝てて専大にも勝てたので満足です．まだ正式順位じゃないけど，地区予選へは行けるのでおｋ．

今回は何と言うか，簡単な問題3問＋難しい問題3問って感じでしたね．バリバリのグラフがなくて残念．もう一問がグラフだったら5問解けてた自信あるのに．後は戦国時代的な感じで．絶対的本命がいなかったので，どうなるかなぁと思ってたら，やっぱり東大でしたね．そして会津がすごい．毎年順位上げてきて，遂に2位ですか．尊敬します．

僕らはミスなく4問解いたんですが，Eに時間がかかりすぎた．完全なる勉強不足ですね．慣れてたら30分で解いてもおかしくない問題だと思うけど，1時間半くらいかかっちゃいました．．．

以下しょぼい問題の解説．問題は次のページからどーぞ．

http://icpc.logos.ic.i.u-tokyo.ac.jp/icpc2006/common/top_guest_en.php

  • A - Dirichlet's Theorem on Arithmetic Progressions

等差数列中の素数を求める問題．エラトステネスでふるって，素数を一個ずつカウントしていく．これはたぶん15分くらいで解いたのかな．

  • B - Organize Your Train part II

列車の並び方問題．part IIの意味がよく分からないけど，たしかによくある問題ではある．

こいつも力技で，全部の場合をぐおおおおっと調べるだけ．これを解いた時点で，たぶん40分くらい経過．

  • D - Curling 2.0

氷の上を滑りながら移動するものとして，ゴールまでの最短経路を求める．

マップのサイズが小さいし，マップの枠で反射しないし，10手まで調べれば良いので，深さ優先の全探索でおｋ．これ解いてたぶん1時間経過．

ここまではさくさく問題が解けたというか，選択の余地がなかったので，楽勝．他の二人が問題を読んで，ペアプログラミング的な感じでやってくれたので，細かいミスはあったものの，順調にやってきた．しかし，ここでちょっと悩む．残り3問は難しい．まだ2時間あるから，ゆっくり落ち着いて一番簡単そうなEを解くことに．

  • E - The Genome Database of All Space Life

構文解析の問題．n個の連続するアルファベット列aを，n(a)と表す．ただし，aの長さが1のときはnaと書いても良い．

たとえば，"2(4(AB)3(XY))10C"は，

2(ABABABABXYXYXY)CCCCCCCCCC

となって，

ABABABABXYXYXYABABABABXYXYXYCCCCCCCCCC

となる．

問題は，展開されたアルファベット列の中のm文字目を求めろという問題．

とりあえず全部展開するだけ展開してみる．基本的には，

  • 現在の文字が数字のとき
    • 次が'('のとき
    • 次がアルファベットのとき
  • 現在の文字がアルファベットのとき

ってな感じで場合分けして解析関数を再帰．こんな感じでまあ，acceptをもらえると思ってた時期がオレにもありました．

はまったのは，閉じ括弧の処理に関することで．文章で書くのは難しいんですが，閉じ括弧を，それに対応する開き括弧と同じ再帰レベルで処理しなくちゃならないんですよね．それが上手く行かなかった．たくさん書いてきたdfsとかと違って，構文解析の再帰処理が頭でイメージできない．．．

はまるはまるはまるはまるはまるはまるはまるはまるはまるはまるはまるはまるはまるはまる．

全体で2時間くらい経過したところで，括弧の数をカウントするというアイディアをもらう．それだ！オレはカウント用変数を組み込んだ．

g++ E.cpp

./a.out < E-in

・・・・・・・・・・・・・・・・・・・・・・・・・・・・（コンピュータ無反応）

こねえええ！！！！！！！！

細かいインデックスのミスとか，もう分けわかんなくなりながら，「もっかい書き直す？」と言われながら，骨組みは合ってるはずだと思って書き直しまくる．このあたりで他の問題を解こうかなと思ったけど，無理っぽいので諦める．

なんとかデバッグが終わったところで新たな問題．サンプルの4つ目の入力から分かるように，展開された列の文字数は恐ろしいことになり得る．ところがちゃんとmには制約があるので，実際に展開することなくm文字目を求めるようにしなくちゃならない．

これもただ，現時点での文字数をmよりちょっと大きな値と比べれば良いんだけど，上手くいかない．考えは合ってるのに，プログラムが書けない．変数を間違えたり，なんだりとしてる間に2時間半くらい経過．

もうだめぽ・・・．そう思って色々弄ってみる．すると何故か（え）サンプルが通るように！！もう舞い上がっちゃって．恐る恐る入力のデータセットを入れてみる．

・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・

固まるコンソール．

遅い・・・だめか・・・・

・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・

数秒後・・・

・・・・・・・・・・・・・・・・・・・・
・・・も・・・もう！！
・・・しゅ・出力なんて出してあげないんだからねっ！！！

ぐあああああああああっと出力

$（点滅）

ツンデレコンピュータきたーーーー！！！アウトプットきたーーーーーーー！！！通った！！！！！ジャッジに送りつけるとCorrect Answer！！！俺たちは2個目のデータをおもむろにリダイレクトしたついでに送ってみたりした．

どきどき・・・．

Congratulations！！！

くぁｗせｄｒｆｔｇｙふじこ！！！！！！！！！
ばっちこおおおおい！！！

しかしこの時点で残り15分とかだったので，諦めつつもFを解こうとしてみたり．ここで初めて順位を見ると，もう5問解いてるチームいたのでがっくし．でも7位だったので素直に喜ぶ．

CとFは難しいね．Cは全く分からない．蛇の動き方にルールがあるんだろうけど，思いつかず．Fは何となく，ノード間を結ぶ直線がなす角の二等分線を使うのかなぁ，とか思ったけどよく分からない．でも残り1時間あっても，CもFも解けなかったと思う．5問解いたとこはFを解いたのかな．Cがこんなに難しいとは思わなかった．

何はともあれ，とりあえず一安心で．学部の後輩も突破したようですね．えがったえがった．ま，ホームでお前らを迎えうってやるからどうかよろしくお願いいたします候．お手柔らかに候．

とにかく参加した皆さんお疲れ様でした．地区予選も頑張りましょう．