AtCoder Grand Contest 032
約一年半ぶりのAtCoder参加。結果としては2完だった。悲しい。
A問題は、A問題としては難しいなと思った。解法は想定解法通りだった。14分かかっているけど、とりあえず良いということにする。
B問題に異常に手こずった。想定解法は綺麗に解いていて、なるほどとしか言いようがなかった。言われてみれば当たり前な気がするが、コンテスト中には思いつかなかった。僕は以下のような良く分からない解法で解いた。
とりあえず書き出してみて法則を考えている中で、頂点数が個（奇数個）の場合には和が
になるグラフが簡単に構成できるということに気づく。このグラフは
番の頂点の次数は
、それ以外の頂点の次数は
となる。
このグラフを元に頂点数が個の場合のグラフも構成できる。頂点数が
個のグラフの全ての頂点の番号を1つ大きくした場合には、元のグラフの
番目の頂点のみ和が
増加して、それ以外の頂点の和は
増加する。よって、新しいグラフに番号1の頂点を追加して、頂点の番号が最大のもの以外の頂点と辺を結ぶと条件を満たす。
こういう面倒なことをしていたらB問題を解くのに1時間かかった。結果論でしかないが、ちゃんと想定解法のように法則を考えるべきだった。
C問題は明らかに時間が足りなかったので諦めたが、解法だけ考えていた。想定解法を見ると発想は間違っていなかったことは分かった。これが解けるようになりたい。
今回のコンテストから得た課題は大きく二つ。1つは数学的な要素が大きい問題について。B、Cのような問題は、数学の証明問題を解くような気持ちで丁寧に考えられるようになりたい。競プロになるとどうしても雑になってしまう。2つ目は典型的なアルゴリズム・データ構造の練習が足りていない。C問題の解法を考えているときに明らかにグラフについてのプログラミングに慣れていないということを感じた。精進していきたい。
AOJ 1161 Verbal Arithmetic (ICPC Domestic 2009)
permutation(10)ができるので、数え上げるだけの問題。実は、少し前にコードは書いていたのだが想定以上に実行時間がかかってしまい通すのを諦めていた問題。
良い機会だったので遅くなっている部分を調べてみたところ、mapがボトルネックになっているということが分かった。以前のコードでは式をstringで保持していてcharからintに変換するmapを使っていたのをやめて、最初にintに直しておくことにした。
昨日知ったのだが、ICPC国内だと時間制限は無いらしいので最初の解法でも大丈夫ということを考えると少し安心するが、自分の想像以上にmapが遅いということを知見として得た。このあたりの知識というか感覚が乏しいので、時間制限が厳しい場合には注意したい。
AOJ 1610 Bamboo Blossoms (ICPC Domestic 2016C)
1週間ほど春休みがあり、他の大学の研究室にお邪魔をしていた（ということを言い訳にした）ので競プロをサボっていた。
その間にチームメイトにaoj-icpcの問題数を抜かれてしまったので、簡単な問題を解いて問題数を水増しすることにした。
C問題ではあるが難易度としてはB問題くらいだと思う。エラトステネスの篩の要領で解く。僕の実装か解法が悪いのかもしれないが時間がかなりギリギリで、最初は最大値を少し余裕を持って取っていたのでTLEとなった。例題で提示されている最大値に設定したら通ったが、それでも7秒台だった。
AtCoder Grand Contest 030
予定があるので出場できるか分からないが、近いうちにAGCがあるので前回のAGCを解くことにした。順位表を見る限り、問題はかなり難しいということが分かる。ひとまず2完を目指したが、結果としてはA問題しかできなかった。
A問題は5分くらいでAC。
B問題は、とりあえず300点の想定解法だと思われるメモ化再帰でで解く解法を思いついたので実装した。しかし、なぜか部分点サンプルの最後の2個だけREが出てしまい、原因がいまだに分かっていない。
B問題の想定解法は頭が良かった。確かに、一定の条件を満たせば毎回反転するのが最適になるということは分かったのだが、最初の方向と反転回数で条件付けるという発想に至らなかった。
悲しい結果になってしまった。AGC032はおそらく参加できるので、2完はできるように頑張りたい。
Codeforces Round #545 (Div. 2)
今日から10日ほど予定があって競プロのコンテストに参加できなさそうだったので、朝4時5分開始だが頑張って参加した。
A問題は見返したら17分もかかっていた。寝起きなので許してほしい。
B問題はどちらもできる人を1番目のグループに何人配属して、clownしかできない人を1番目のグループに何人配属するか、というのを全て試して等式が成り立つ場合が存在したら出力した。これがなぜか40分かかっている。考察に少し時間がかかったが、それ以上に実装が冗長になっている。
C問題は行と列のそれぞれについて同じ値は同じランクになるランキングを作成して、各交差点について下から何位か、上から何位かという値を保持しておく。これはで構成できるので通る。各交差点について、行・列におけるランキングの下からの順位の最大値と上からの順位の最大値を足した値が答えになる。これも40分くらいかかった。
D問題は最初に読んだときに完全に勘違いをしていて異常に簡単な問題だと思ったが、部分列が重なる場合がある（1WAしてから気づいたので頭が悪い）。と
が一致する最大の
を求めれば良いのだが、これが愚直に判定して間に合うという幻想が見えていてTLEを食らって時間切れになった。
後から知ったのだが、この問題にはz-algorithmというアルゴリズムが知られていてで判定できるらしい。知識で負けたという感じもするが、愚直にやって間に合わないということが分かっていれば時間内に調べられた気もするので、単純に頭が悪かった。
D問題に50分残せたので、C問題までは悪くなかったと思う。Dが解けなかったのは悲しい。
AtCoder Beginner Contest 116
競プロを再開してから初めてABCで解けない問題があった。悲しい。
C問題は書くだけ。しかし10分くらいかかった。
D問題が解けなかった。DPかなと思ったのだが制約が厳しくて愚直な方法では通らない。そこからDPを効率良くできないかと考えてしまったのが良くなかった。
p種類のネタを使ったときの最大値を考えるという発想はあったのだが、想定解法に至らなかった。確かに解説を読んでしまったらなぜ思いつかなかったのか不思議だが、DPだという先入観があったので良くなかった。
Educational Codeforces Round 61
A、B、Cはpretestが通ったが、Cがhackされてしまった。C問題は本当に計算量が大丈夫なのか少し自信がなかったが、WAでhackされていたので不思議に思って確認してみると、iとjを書き間違えている部分があった。なぜprerestに通ってしまったのだろう。
C問題は単純に累積和を取ってから取り除く塗装屋の全ての組み合わせを試していたら間に合わないので、枝刈りをした。おそらく、担当する全ての区間に三人以上の塗装屋が担当している人を取り除けば間に合うということが分かるのだが、厳密に示してはいない。とりあえず、それでACは取れた。想定解法ではない気がするので、Editorialが出たら確認したい。
（追記）Editorialをみた。賢くやると普通に全ての組み合わせが試せるということがわかった。僕の枝刈りと使っている情報は同じなのだが、明らかに想定解法の方が綺麗だし、時間複雑度が明らかなので良いですね。
F問題も単純にDPだろうと思ったのだが、なぜか通らなかった。他の人の解法をみてみると凄く効率の良い書き方をしていて、十数行程度でかけるらしい。しかし本質的な部分は変わらないように見えるので、僕のコードがなぜ通らなかったのかは未だに良くわかっていない。
F問題の想定解法は普通に頭良いと思うんだけれど、多くの人が全く同じ解法で解いているので典型的な解き方なのかもしれない。
F問題はともかくとして、C問題は勿体無かった。しかしレートが1500に戻った。とりあえず今回のCとFみたいに解法が分かる問題はしっかりと取れるようにしたい。
あと最近気づいたことだけれど、僕は実装が遅いというだけではなくて特にレート上位の人に比べると単純にコードが無駄に長いということが分かってきた。これはバグが多い原因の一つでもあると思う。時間複雑度が間に合う解法を思いついたらすぐに書き始めてしまうのだけれど、効率の良い短いコードで実現できるかを考えてから書き始めるようにしたい。
