ICPC国内予選参加記録

東工大からid:eagletmtさんとhaskell-loverとして参加しました。ちなみに自分はHaskellは好きだけどloverと言えるかと言うと・・・。嫌いなのではなく、あんまり使ってないので愛してるなんて言う資格はない気がするという話。
結果はABC解いて総合27位/学内5位でした。残念。
以下記録。
問題が出て、とりあえずA問題。いーぐるさんと少し解き方確認しつつ任せる。自分はその間にBを読む。
Bは単純に迷路を解くだけだけど、壁の配置がverticalとhorizontalがあって少しめんどくさい感じ。考えてから紙の上でコードをガリガリ書く。20分くらいで読み込み部が大体書けて、CとDを流し読みしたところでA問題がAC。続いてB問題。さっき書いたコードにダイクストラくっつける。AC。ここまでで40分くらい。
続いてC、D。いーぐるさんがCを読んでいたので説明を聞く。四面体数A_iをi番目までの三角数の総和と定義して、この四面体数を組み合わせて総和をNにしたい。最小のものは何通りか、という問題らしい。これって四面体数をk個使ってある整数が表現できるかをvector<bool>で持っておいて、DPぽくぶん回せばいいんじゃないのーと提案したものの、最大で一つのkにつき2億ループ来るけどどうなの？ということで却下。いーぐるさんがsetを使って書き直し始める。その間にDを解読する。
Dはテトリスを積み重ねたとき、崩れるか崩れないか判定しろという問題らしい。ブロックの重心が、下のブロックで支えられてる範囲より外側に出たらダメということらしい。それは分かったけどinputきもい・・・。ほんとにこんなの出来るんだろうか。サンプルも自分の解釈が微妙に合ってないしよくわからん。とりあえずE読もう・・・。
E。有向グラフのエッジに文字列が与えられてて、スタートからゴールに行くとき、通り道の文字列を全部concatして辞書順最小のものを作れという問題。一瞬ダイクストラか？と思ったけど、一つの頂点に来た時の部分文字列が強いか弱いかは一意に判定できないよなぁ・・・。しばらく考えるも謎。Cの方はサンプルと答えが合わないらしく、もう少しかかる雰囲気。
もう一度D。そうか、ブロックの重心はブロック座標+0.5の所にあるのか！なんか分かってきたぞ！しかしこの入力読むのやだなぁ・・・。とりあえず解けそうなのはDしかないので頑張って書く。
読み込みがなんとなく出来たところで、Cが組み上がる。でも終了する気配を見せない・・・。しょうがないので回したまま放置してDを書く。ここで18:00くらい。
10分くらいして、Dを書いてる途中でC-1が終わる。投げる。AC！さあC-2だ！もう一回ぶん回して放置。
いーぐるさんがEを考えている間、こっちでDをガリガリ書く。その間にC-2も終わる。AC！これで3問。しかし時間は18:30。すこし焦りつつDを書き進め、とりあえず完成ぽくなる。が、実行するとSegmentation Fault・・・。ここで、いーぐるさんがEを思いついたらしいのでソースを印刷して交代。
その間紙面デバッグ。がんばる。20分くらいして、ダメだった報告が入る。ワーシャルフロイド2回でできると思ったらそうでもないらしい。ちょっと見てても解決しなさそうなので、再交代。紙面デバッグ分を書き写す簡単なお仕事。
できた。実行。またSegmentation Fault・・・。どうもブロックの塗りつぶしで失敗しているらしい。ちょっと探して発見。まだおかしい。調べてると色々とバグが見つかる。
この辺で残り20分くらいだったので、一問通すことに専念しようということでいーぐるさんとペアプロ。デバッグ出力を付けつつ、サンプルの実行結果と比べる。一つ直ったと思ったらもう一つバグが見つかるという悪循環・・・。コーディング力なさすぎわろた。
結局、最後のバグを修正して、サンプルに正しい答えを返すようになったところでタイムアップ。本当にあってたか判らないけど惜しい・・・。

後でHello Wand!!の人に話を聞いたところ、Cはvector<bool>的なので普通にすぐ実行終わるらしい。なんという・・・。

そんな感じでした。後一年がんばれば国内予選突破できるんじゃないかなぁ、と思った。これでDが合っていればだけど。