ICPC2011福岡大会

@eagletmtさんと@draftcodeさんと一緒にhaskell-loverで出ました.B,A,D,F,Hを解いて全体11位,大学別8位.
基本的には,みんなで分担して問題を読んで,解けたのから実装していく方針.実装は自分と@eagletmtさんがやり,@draftcodeさんは実装してる人とペアプロしてバグを抑制する.

B

ドーナツの画像を見てうげーと一瞬思ったものの,言いたいことは上下と左右がそれぞれ繋がってる格子があるよというだけ.入力サイズがかなり小さいので,各マスから8方向にたどって文字列を生成し,mapにつっこんで数えるだけ.最初は部分文字列いらないと思っていてサンプルが通らなかったけど,問題読み直してAC.

A

@eagletmtさんが先に実装していたけど,どうもバグっているらしいのでデバッグに参加.説明を聞いたところ日付の変わり目の処理が怪しげで,そこを指摘したら今のコードで修正するのは面倒とのこと.問題聞いた瞬間にシミュレーションの感じがしたのだけどコードはそうなってないらしい,ということもあって書き直してもらう.AC.

D

どう見てもダイクストラだったので実装するだけ.

F

JAGの模擬国内予選でこんなの見たような…….[使った文字列のset][最後の文字列]のメモ化再帰を書いて投げたところRE.なんだこれーと思いつつデバッグしたら,どうも包含されている文字列を除去するところで消去しすぎているっぽい.@draftcodeさんの助けを借りつつ修正.TLE.二つの文字列どうしを繋げるとき,どの位置で結合できるかを再帰の中で毎回計算していてどう見ても非効率だったので前計算するようにしてAC.

H

他に解けそうな問題ないし,どうせパーサだしということで@eagletmtさんと@draftcodeさんが書く.文法がかなり優しい構造になっているのでやるだけらしい.40分くらいで書き上げて一発ACしていた.ぱない.

G

ぱっと見では貪欲かと思ったけど,すぐに決めにくい所があるので違う方法を考える.グラフにして最小費用流で解けるんじゃないかと思って一時間くらい考えてたけど,結局うまく落としこめなかった.探索すればいいらしい..

C

これも方程式とかで行けるのかなーと思ったけどやはり枝刈り探索らしい.語数少ないしアルファベット26文字しかないし,枝刈りでいけるかなーとは思ったんだけどオーダーがわからなかったので放棄してしまった.もったいない…….

E

H解いてもらっている間に正20面体を転がす規則を紙の上で考える.規則がわかったと思ったあたりでHが通ったので一気に書くがサンプルすら通らない…….必死でデバッグしていたら,どうも頭の中で展開図を組み立てるときに裏返しに組んでしまっていたらしいことがわかった.
@draftcodeさんが最後10分くらいで問題用紙を切って20面体作ったけど,あえなく時間切れ.あとで@ororogさんに,この問題は見た瞬間にサイコロ作るべきと言われた.

総評

とにかくCかGは解けるべきだった.ICPCじゃなくてこういう問題出されたらとりあえず枝刈り探索書くよなぁ,と分かっているだけに,ICPCだからオーダーが見積もれるはずだという思考に陥ってしまったのが残念すぎる…….
あとはAやBからじゃなくて,問題全体を見てから簡単そうなのを解くべきだなぁとか.あとでりんごさんに聞いたら,Dが一番問題文短かったから解いたと言ってた.
来年は世界大会行きたいですね.