ビビジランテソンテネグロホメストーニカルマンドーレポポス

さあ、いつまでたってもオレンジコーダーになれない子はどんどんしまっちゃおうねー

ICPC 2018 国内予選 参加記

ICPC2018国内予選大阪大学からチーム BFS として参加しました. 大阪大学からは2チームが参加し,それぞれ4完38位(チーム BFS)と3完87位(チーム osaka_PFN)という結果になりました. 全員でアジア地区予選に行けるようにチーム分けをしたのですが,アジア地区予選に行けそうなのは1チームだけという残念な結果となりました.

f:id:refine_P:20180708002143p:plain

チーム紹介

チーム名は,メンバーのハンドルネームの頭文字を取ってきて,いい感じに並べたら出来上がりました.
メンバーの実力は,自分とsntea君が青で,Badlylucky君が水色といった感じです.
一応,自分のレートがチームの中で一番高いのですが,sntea君の方が圧倒的に有能なので,結果的に自分は半分置物みたいな感じになってしまいました.アジア地区予選ではちゃんと活躍できるように頑張りたいです.

本番前

記録的な大雨の影響でBadlylucky君が大学に来れず,リモートでの参戦となってしまいました.
複数台のパソコンでの同時ログインはルール違反となるため,sntea君のパソコンで全てのコーディングを行い,Badlylucky君には問題の読解と考察を担当してもらうという割り振りになりました.
話し合いの結果,Badlylucky君がBの読解,sntea君がAとBの実装,自分がCの実装を担当して,後は流れでといった感じの作戦になりました.

本番

A問題は見た感じやるだけだったので,sntea君に丸投げしました.そしたら,sntea君は有能なので瞬殺してくれました.

B問題は見た感じヤバそうだったので,一抹の不安を感じつつ,自分の担当のC問題を解くことにしました.
緊張でテンパって無駄に式変形しまくったけど,よく考えれば考えるべきフロアの総数は高々sqrt(b)程度しかないことに気づいて楽勝じゃんってなりました.
sntea君がBの実装にかなり苦しんでいたので,パソコンを奪い取ってCの実装をしました. 実装量はそこまで多くなかったので,あまり苦しまずにACできました.

D問題はsntea君が問題文は読んだといっていたので,自分はE問題を読むことにしました.
しかし,問題の内容が全く理解できなかったので,Badlylucky君にEの読解を投げました.
Badlylucky君が問題を読んで自分に色々教えてくれましたが,それでも理解できなかったので諦めて別の問題を解くことにしました.

他の問題を一通り見た結果,G問題がワンチャンありそうだったので,Gを解くことにしました. 括弧内の式に関して,値が n になるものの個数を先に計算すれば,それ以降は括弧部分を式の計算結果の値として扱ってよいというアイデアが思いついたので,後は+と*をどう扱うかだなという気持ちになりました.
式の長さが長くなれば,計算結果の値も増えるから尺取りで何とかなるかなあという感じになったので,Bの実装に苦しむsntea君からパソコンを借りてGの実装に取り掛かりました.

Gの実装で詰まったので,sntea君にパソコンを返して,自分はD問題を読むことにしました(sntea君がDは問題文を読んだだけだと言っていたので).
Dは見た感じ制約が小さそうなので枝刈りDFSかなという結論が出たところでDを放棄して,自分はG問題を考えていました.

そうこうしているうちに,sntea君がB問題をACしてくれたので,sntea君を褒め倒しつつ二人でD問題に挑みました.
自分は枝刈りDFSで解けそうと言ったのですが,sntea君から半分全列挙じゃないとダメだと言われてしまいました.
sntea君が説明してくれた半分全列挙解法が今ひとつ理解できなかったので,思考停止で丸投げしました(お前丸投げしてばっかだな). そしたら,sntea君は有能なので気づいたらACしてました.

sntea君がDの実装をしている間にG問題が中々厳しいことに気づいたので("*1"の扱いが面倒),Gを放棄して二人でE問題を解くことにしました.
自分がE問題の内容をsntea君に説明しているうちに,どうやら自分がEを誤読していた挙げ句(最終的にs=a*nになると思っていた.正しくはs=a*(n+1)),全く問題の主旨を理解していなかったことに気づきました.
Eの考察をsntea君が詰めてくれて,多分それで解けそうという感じになったので,実装をsntea君にお願いしました.
sntea君がEの実装をバグらせて辛そうにしているのを隣で見ながら祈っていると,EをACできないままコンテストが終了.
4完38位,学内1位でアジア地区予選進出圏内だったので,ひとまず安心といった感じでした.

反省

E問題を思いっきり誤読していたのが明らかにマズかったですね. Eの解法自体はそこまで難しいものではないので,自分が考察を詰めておけば5完できた気がします.

後,D問題の解法が枝刈りDFSだと主張するなら,枝刈りの仕方とかをしっかり考察しておくべきでした.
今回はたまたまACできましたが,半分全列挙は結構バグらせやすいイメージがあるので,バグったときに枝刈りDFSに方針を切り替えられるようにしておくべきでした.

それと,僕がコンテスト時間内に頑張って考察していたG問題も,他のチームが全然解いていない時点で切り捨てるべきでした.
考察自体はそこまで間違っていなかったと思いますが,明らかに実装が重いので,解かないという判断がベストだった気がします.

さいごに

記録的な大雨の影響により,中々厳しい戦いを強いられましたが,これも良い思い出になったかなと思います. (個人的に,Badlylucky君に対して通話で不定期に行われる生存確認がツボでした)

ひとまず,アジア地区予選には行けそうなので,osaka_PFNの分まで頑張れたらなと思います.