読者です 読者をやめる 読者になる 読者になる

dohatsutsu’s diary

日記を書いています。

【No.005】「ACM-ICPC アジア つくば大会 2015 参加記」


コンテストの感想 (完全に僕目線です)

・まず先輩が環境設定等を行っている間にA問題を読みました。

・数分後、先輩に環境設定が終了したことを告げられ、すぐにA問題の実装を開始しました。

・とくにバグることもなくAC

・振り返ってACしたことをチームメイトに話すと、D問題を読んでほしいとのことだったのでマシンを先輩と交代しD問題を読みはじめました。

・D問題は似ている問題が去年の天下一予選で出題されていたことを思い出し、すぐに解法が分かってしまいました。

・先輩がB問題をACした時、僕は約半分の紙コーディングが終了した状態で、後輩はまだC問題を考えている途中だったため、とりあえずD問題の実装を行うことにしました。


・D問題の実装の約7割が終了した時、C問題が解けるという話を先輩から聞いて、とりあえず書き掛けのD問題のコードを印刷してマシンを交代することにしました。

・印刷したコードを読み返していると、終わりの角度ではなく始まりの角度でソートしているというバグを発見しました。

・後輩がC問題のデバッグをしているようだったのでマシンを交代してもらい、紙コーディングしたD問題を書き写しつつソートのバグを修正してACしました。

・実はこのとき、6つあるサンプル入力のうち最初の3つだけを試してから提出していました。(隠された残り3つのサンプル入力の存在に気付いたのはAC後)

・そのあと後輩とマシンを交代したらすぐにC問題もAC。

・順位表を見るとなんと2位に

・先輩に状況を確認すると、E問題とF問題が読めただけでまだ解法ができていないとのことだったので、まずその2つの問題概要を説明してもらいました。

・概要を聞き終わった後、E問題が桁DPっぽいことに気づき、実際にどのくらいの状態数になるのかという情報を空いていたマシンを使って試してみることにしました。

・各桁を掛け算した値の種類が意外と少ないため桁DPで解けることが発覚し、僕がE問題を実装することにしました。

・はじめに僕が先輩に実装をお願いしたものの、先輩がマシンの前に座ってから数秒後に「やっぱり僕が実装します」と言って自分に代わってもらいました。
(先輩と比べて僕の英語を読むのがとても遅いため)

・しばらくしてコードが完成したもののサンプル入出力が合わずどうするか迷っていたとき、ちょうど後輩がF問題の解法を思いついたらしいのですぐにマシンを後輩と交代
して自分は紙デバッグを行うことにしました。

・印刷したコードを先輩に説明しながら1行ずつ読み返していくと、入力を整数として読んでいるために020という入力が20という入力になってしまうことを先輩に指摘されま
した。

・Fを書いている途中の後輩に少しの間だけ交代してもらい、E問題を修正して提出するもTLE

・手元だと最大ケースっぽいサンプル入力がほぼ1秒で終了しているので、とりあえずの高速化としてmapをunorderdmapに変えてみたらACしました。

・その後、僕と先輩でG問題の考察をしている間に後輩がF問題をAC

・その後、先輩がG問題の解法を思いつき、先輩が実装をしてAC

・あまりもの嬉しさにハイタッチ

・後は残った問題をいろいろ考察したり愚直解を作っていろいろ試したりしていたらコンテスト終了

・凍結前の順位は6位、そして最終結果も6位でした。


個人的に、この結果の要因は問題担当の割り当てが良かったことだと思います。


それぞれが実装を担当した問題は

先輩:B,G

僕:A,D,E

後輩:C,F

でした。

・面白いことにB問題を読んだのは後輩で、C問題は先輩ですが、B問題を実装をしたのは先輩で、C問題は後輩でした。

・偶然僕が読んだD問題は、ほぼ似ている問題を知っていたため絶対に解ける自信があり、チームメイトに問題概要を伝えることもありませんでした。

・E問題、F問題、G問題はそれぞれ解法を思いついた人自身が実装を担当しました。

・完璧に3人にバランスよく問題を割り当てることができたため、負担が多くなってしまった人が途中で疲れきってしまうことが無かったのも大きい気がします。