AtCoder Grand Contest 032 - 鴨井遼競技プログラミング

約一年半ぶりのAtCoder参加。結果としては2完だった。悲しい。

A問題は、A問題としては難しいなと思った。解法は想定解法通りだった。14分かかっているけど、とりあえず良いということにする。

B問題に異常に手こずった。想定解法は綺麗に解いていて、なるほどとしか言いようがなかった。言われてみれば当たり前な気がするが、コンテスト中には思いつかなかった。僕は以下のような良く分からない解法で解いた。

とりあえず書き出してみて法則を考えている中で、頂点数が $2n+1$ 個（奇数個）の場合には和が $(2n+1)n$ になるグラフが簡単に構成できるということに気づく。このグラフは $2n+1$ 番の頂点の次数は $2n$ 、それ以外の頂点の次数は $2n-1$ となる。

このグラフを元に頂点数が $2n+2$ 個の場合のグラフも構成できる。頂点数が $2n+1$ 個のグラフの全ての頂点の番号を1つ大きくした場合には、元のグラフの $2n+1$ 番目の頂点のみ和が $2n$ 増加して、それ以外の頂点の和は $2n-1$ 増加する。よって、新しいグラフに番号1の頂点を追加して、頂点の番号が最大のもの以外の頂点と辺を結ぶと条件を満たす。

こういう面倒なことをしていたらB問題を解くのに1時間かかった。結果論でしかないが、ちゃんと想定解法のように法則を考えるべきだった。

C問題は明らかに時間が足りなかったので諦めたが、解法だけ考えていた。想定解法を見ると発想は間違っていなかったことは分かった。これが解けるようになりたい。

今回のコンテストから得た課題は大きく二つ。1つは数学的な要素が大きい問題について。B、Cのような問題は、数学の証明問題を解くような気持ちで丁寧に考えられるようになりたい。競プロになるとどうしても雑になってしまう。2つ目は典型的なアルゴリズム・データ構造の練習が足りていない。C問題の解法を考えているときに明らかにグラフについてのプログラミングに慣れていないということを感じた。精進していきたい。