AtCoder Beginner Contest 194 反省

今回からコンテストの反省を書くことにした。いつもいつも何千字も書けるとは限らないが、可能な限りやろうと思う。

解法にはあまり触れない。解に至る過程で辿った思考と精神状態を中心に書いていこうと思う。

結果を鑑みて

1500(1) 39:09

レートが+1された。簡単な問題で詰まったり変なミスが多かったので微増で耐えたのがほぼ奇跡のようなものだが、低難易度に対する直観力が少し鈍っている気がする。新adminになってから少しずつコンテストの傾向も変わってきているので弱点を作らないように取り組んでいきたい。

A - I Scream

パッと見た感じでは場合分け、B問題相当に見えた。

解いていくと「A問題だしいいだろ」と思って読み飛ばしていた部分に重要なことが書いてあったりして結局3分も使ってしまった。

単純な場合分けだが、乳固形分が与えられないとかラクトアイスは乳脂肪分ではなく乳固形分が3%以上であるとか、詰まる部分がままあった。

B - Job Assignment

パッと見た感じ、ただのソート系の問題に見えた。B問題として妥当そうな難易度だと思った。

解いていくと、ソートして貪欲にそれぞれアサインした時に同一人物かどうかの判定が必要になることに気付いた。これだけなら(かかる時間, index)を持たせてソートしてあげれば判定は容易だが、その判定が何度も連続したりすると色々面倒くさそうに見えた。

第一感はそんなわけではずれ。ちらと制約を見ると二乗で良さそうなことに気付けるので後は普通に二乗ループを書いて通した。

第一感に引きずられて制約を見落としてしまい、4分も使った。

この時点では予想外の出遅れに焦ったが、どうせ後ろの方の問題で巻き返せるだろうと自己暗示をかけることでなんとか平静を保った。

C - Squared Error

Errorというのはこの場合は誤差のことだと思うが、この形式で何が誤差なんだろうか。（というより何が真値になるのやら）不思議だね。

パッと見た感じ、「こういうのはパターンが決まってるから得意なんだよな〜」という気分になった。C問題にしてはやや難しめ、D問題相当に見えた。先ずは雑な展開により総和と二乗和を使う方法が思い浮かんだ。

この時の第一感は正しかった。何度かこのような問題を解いているのでこうなることはすぐに直感できていた。しかし、暗算でやった雑な展開でどうも係数をミスったらしく答えが合わず首を傾げていた。

そのまま10分近く経過し、流石にまずいと思ってループを回すことにした。ループとΣやΠは読み替えが効きやすい。iを固定してjについて計算することを考え、なんとかiの逆順に回していい感じにコードを書いてACできた。

最初で躓いてえらい目にあう という経験はABCで何度か経験しているので「ああ、またこれか......神よ......」といった焦りを通り越した諦念の気持ちでその後の問題を解き進めることとなった。

D - Journey

基本的に期待値を使う問題は簡単なものしかやっていないのであまり慣れていないところがある。だからパッと見た感じは少し嫌な気分になったが、ここまでくると何をやろうがビハインドなので落ち着いて読んだ。文自体は短く、そのおかげもあってか考察がこれまでとは打って変わってすんなりと進んだ。

コンプガチャ系の問題にありがちな、ある状態へ遷移するために必要な操作回数の期待値がその状態へ遷移する確率の逆数になっているという性質、そして状態は頂点番号ではなく未踏の頂点の個数を持つだけで十分だということに気付いた。

前述したように、期待値問題はあまり自信がないので祈りながらコードをテストした。コーナーとかもよくわからないのでエイヤ！と提出するとACが返ってきた。このときは相対誤差とかあまり気にしていなかったがdecimalを使わされることになるかもしれないし、ちゃんと制約は読んだ方がいい。今回はここまでかなり読み飛ばしによるミスが多かった。

結局この問題は2分ほどで片がついたので精神的には少し楽になった。

E - Mex Min

見慣れない制約の書き方をしていて、ひょっとして有効数字が2桁だからN=1549999とか出るのか とか意味わからんことを考えた。

パッと見では「たぶん解けるな」と思った。制約から察するになんだか線形計算量で解けるっぽい。SWAGや尺取法が似合う問題に見えた。

第一感はおそらく正しかったが、5分ほど考えたあたりでふと部分問題に何となく既視感を感じた。試しに range mex queryで検索すると見たことのあるウェブサイトに到達した。どうもSegment Treeで区間mexクエリ（この問題のものとは少し違うが）が解けるという内容っぽく、詳しく読むとこれを利用した解法が思いつけた。

線形計算量の方針で考え続けても恐らく解法にはたどり着けたのではないかとは思うが、たぶん時間かかって破滅していたと思う。それまでの考察を一旦置いてgooglingできたのはコンテスト中のムーブとしては悪くなかったと思う。

それはそれとしてSeg木を引数でバグらせて1ペナつけたのは注意力散漫としか言いようがない。

とはいえ、だいたい考察を置いて検索に頼る時というのは行き詰まっている時なのでこれは後で線形計算量で解いてみようと思う。

F - Digits Paradise in Hexadecimal

これは解けなかった。

パッと見た感じ、桁dpに見えた。順位表を見ると自分より10分も前に手をつけている人たちがこれを通せていなかったので一筋縄ではないんだろうなと思った。

桁dpを考えると状態数だけでO(logN * (2^16))となり、とても間に合わない。

「こういうタイプの問題は遷移のうまい省略でインラインdpにするんですよね〜」と思って考えるが、時間ばかりが過ぎた。

そんなこんなであんまりうまく進んでいなかったが、終了20分前くらいで境界を走っていない状態（たとえばN=1000なら09??とかを含む状態）からは遷移させずとも組み合わせの計算でちょうど種類数がKになる時の場合の数が計算できそうだということに気付いた。そこからは集中して取り組み、コンテスト終了後30分まで考えることができた。

考えた結果、この解法の過程で必要になる包除の計算量がデカすぎるということになった。ああ〜〜（脳みそが溶ける音）

この問題も方針新たにもう一度解く。

総括

変なミスや読み飛ばしが多かった。注意力散漫だったと思う。奇跡的に冷えずに済んだが、-30ぐらいあってもおかしくないムーブが多かったので気を付けたい。こういう注意力が散漫な日、みたいのは実際の心配事に起因している可能性があって、実際に私は来週の月火と心配の要因になるような出来事がある。だからといって対処案はないのだけれど。

BGMは環境音がいいという話を聞いて、コンテスト中のBGMを図書館の環境音にした(BG"M"とは言わないかもしれないけど)

1年間同じBGMでコンテストに臨んでいたのでこれによるルーティンのアドバンテージはないけど、これが今後うまくいってくれると嬉しい。