AGC034

Bを通して37.0、Cを通して36.8。BをACして順位表を見ると意外と低い順位だったが、それでも気分はよかった。B問題がすごくよかったから。

A - Kenken Race

要するに連続した石がなければいい。Bの人(ふぬけ君)が先に動けば干渉することもない。その辺をじっくり抜けがないか考えて、5分くらいしてC>Dを考える問題だと気づく(遅いよ)。追い抜くためには、3マス連続したスペースが必要。それもじっくり考えて、やや不安はあったが提出してAC。考察内容のわりにACしてる人が少ないのも不安だった。ちゃんと証明できればそんなの関係ないのだが。

B - ABC

これ好き。問題を目にした瞬間嬉しい。色々考えて、解けそうな(自分に解けるという意味ではない)問題だとは思えたものの、かなり曖昧な考え方しかできていなかったが、BCを塊として捉えることに気づいて見通しが立った。BCが左へ沈んでいくと思えば、AとBC以外で切りつつ左のAの数を持って足していくことで答えが求まる。解けてる人多くて、天才以外お断りコンテストは実際に天才ばかり出ていると思った。

C - Tests

X点まで上げたときの効率がいい順にX点とって残りをどれかで取るという最も普通っぽい解法に行くまでにかなり時間がかかった。思いつかないとかじゃなく順調に進んでて。さて、X点取るにはX時間勉強する必要があり、時間が一定なのでイメージより簡単。点数が高くなるほど効率がよくなるので、X点を取らないものが複数あると風船みたいに片方へ全部行きそう(つまり一つしかなさそう)。まあ行けそうなのでサンプルで様子を見るが、通らない。サンプルすら通らないというのはわりと想定外。変なケースを置いててくれたということで、考える(サンプルが複雑なので正解を自分で計算することはできない)。半端を処理する部分のコストを優先することはありそうだと思いつく。計算量が爆発しそうだが、半端をO(N)通り試して、残りは大きい順に全部なのが明らかだから、O(N)で行ける。実装するが、やはりサンプルは通らない。単純ミスを疑い、不等号が逆なのを発見する。この単純ミスがなければサンプルは最初から通っていたのだ!これは運がよかった。単純ミスを考察漏れと勘違いして漏れを発見できた。そしてAC。これは嬉しかった(ガッツポーズした)。

漏れは発見したが、他の漏れがないという確信はなかった。そもそも、残り30分で「普通の貪欲みたいなので時間をかけて書いたのでとりあえず提出してみるか」みたいな感じだった。運良く漏れを発見したので行ける可能性も高いと思っていたが。想定解は二分探索で、X点とる個数がわかっているというのが明快だ。自分の解法は、まず貪欲にX点をとっていくことでとりあえずの答え(真の答えはこれと同じかより小さい)が求まる(半端は全探索)。ここでX点をk個とったとすると、k個以下なのは確定。k-1個+半端だとすると大きい順にk個をとるより劣るので、k個。正しいのでは?よくわからん。そもそもコンテスト中はなんも証明してなかった。半端の位置を決めればあとは大きい順にとるだけという問題だった。半端の位置を先に決める。そのときに、X点とるのを何個にするかは確かに定まらないか。