パナソニックプログラミングコンテスト(ABC195) 反省

よかったんじゃないかな。うまくキリ番を踏めれば賞金もありうるというところ。

結果を鑑みて

2400 46:58

橙パフォ、全体33位、レート+60とかなり良い成績だった。B問題の凶悪さにもペースを乱されることなく進むことができた。周りもBで詰まっていたので遅れを感じずに済んだのが大きい。

実装の軽い問題が多く、いずれの提出コードも700byteを超えない程度のものであったことも速解きにつながった。

A - Health M Death

パッと見た感じ、ただの倍数判定なのでやるだけだった。46秒で通した。

B - Many Oranges

パッと見た感じ、除算についての問題でO(1)で解けるものだろうと踏んだ。同時に細かな処理（切り捨てとか切り上げとか） が面倒臭く、実装によってはコーナーケースが無限に生じうることを予感した。あとMがキログラム単位でびっくりした。サンプル見て首を傾げていたのだけれど、これに気付くとちょっとだけむっとした。

制約を見ると、全探索が可能そうに見えた。つまり、O(1)を頑張るか全探索するか選べる問題だと理解した。こういうときは経験的に全探索を選ぶのが速さ・正確さ共に安定することを知っていた。そういうわけで全探索路線に切り替えた。

全探索できる項目は少ないので、すぐにオレンジの個数についての全探索が思い浮かんだ。そしてこのときの最適な１個当たりの重さは個数nに対してW/nであることもさっと証明できた。（２つのオレンジの重さをW/nからずらそうとするとW/nであった時より得をすることは絶対にない。）

そういうわけで何とか通せた。解法の逡巡などがあり8分かかった。CかD問題相当に見えた。周りも同じくらい手こずっていたので焦りは感じずに済んだ。

これが初参加のコンテストの人とかってこの問題でどういう気持ちになるんだろう。

 

C - Comma

パッと見た感じ、O(logN)の解法がぼんやりと浮かんだ。10^3, 10^6, ...といったカンマを打つタイミングの数に注目した。

この第一感は正しく、特に証明はしなかったが適当に式を合わせるとサンプルも合ったので提出した。2分ほどでACできた。Bの方が難しかったなと感じた。この時点ではそこそこ良い順位だったとおもうので（スピードが出ている時は順位表を見る癖がある。精神安定に繋がる。逆の時は逆の作用を持つ。）良いテンポで進んでいたと思う。

D - Shipping Center

パッと見た感じ、制約や入力などからナップザック問題の前計算によってクエリO(1)、あるいは半分全列挙のbitDPなどの解法を連想した。（実態に即してはいない。あくまで「そういう解法があてはまるかもな〜」という予想。）

内容がごちゃごちゃしているように感じて、すべきことや本質などを探るのに時間がかかった。全体感を掴み取るのに5分近く使っていたのではないかと思う。これは、ちゃんと考えればすぐに掴めた本質をエスパーで適当にさらって掴もうとしたために起きたロスだと思う。それでもエスパーをやめてちゃんと考える方にシフトできたのはよかった。

ちゃんと見ると制約や入力はナップザック然としているが問題は全くナップザックではないことに気付いた。それと同時に雑な貪慾法が生えた。O((NM+MlogM)Q)程度の計算量だが、パッと考えたところ計算量には十分な余裕があるように見えた。ソートと貪慾の正当性は感覚で理解していたが最後までナップザックオーラを放つ問題文が怖くて祈りながら提出した。何とかACをとれたのでよかった。

この問題は焦ると解法ガチャをミスったりそれに固執したりして取りこぼしやすいような問題に見えた。パッと見た感じはE問題相当、解くとD問題として妥当な難易度に思えた。

この時点でかなり精神に余裕が生まれた。

E - Lucky 7 Battle

パッと見て、ゲームdpかな という感じだった。

大正解、というかこの形式だともうそれくらいしか疑う方法がないのだが。問題文についてサンプルなどを見て理解しながらコードを組んだ。

ゲームdpは最終局面から遡るのが定番である。S, Xは予めreverseしておいてdpを書いた。ループ中では7*Nの状態を追うことになるが、ゲームdpを書いたのが久しぶりなのがあって、逆再生するような配るdp(つまるところ貰うdp)として組む時に少し遷移を書くのに手間取った。最適戦略の基本に立ち返ることで何とか遷移を決めることができた。

あと、ゲームの始状態は0 mod 7の状態になるわけだが、 これがなんだか自信がなくてこれも祈りながら提出した。間違っていても取り返せるくらいには先行しているし という気持ちがあって思い切って出せた。なんとかACを取れた。この問題には12分近く使った。コードの構築に一番時間がかかった。

F - Coprime Present

パッと見た感じではB-Aについての奇妙な制約が目に止まり、区間篩を連想した。また、なんかすごい方法によるbitDPもどきとか。あとは独立集合の数え上げについてググった。

3~5分のうちにとんでもないひらめきがあった。73以上の倍数が72個の連続する整数に2度以上現れることはないのではないか というものである。このアイデア自体は恐らく何度か目にしたことのあるものである。

この気付きの後は上記の解法を並行して考えつつおはなつみに向かった。リフレッシュは大切で、精神的な余裕は解法を落ち着いて精査する余地をもたらしてくれた。ここで大方の方針は決まり、戻ってくると72以下の素数の個数をググった。

あとはいい感じに進み、ただpypy特有のTLEが怖かったのでインラインにしたりなど適度な定数倍改善を含みつつ提出し、ACを得た。

Bで2ペナくらいしてたら焦りでこの問題は解けなくなっていたと思う。

総括

制約をがっつりと見てそれに即した解法をエスパーしたり、それとは関係ない方向にも考えたり、今回のムーブはバランスが取れていて理想的だった。実生活における心配事は減ってきていて（というか際限なく後回しにしているだけなのだけれど）、それが安定したプレイングの土台になったのかなと思う。

ちなみに、INHOPではないがこの週は乾燥させたホップの株から出したハーブティーを毎日のように飲んでいた。香りは香ばしく精神安定作用があるように感じた。味は......

因果関係はないのかもしれないけれど、ひとつひとつの小さな調整が実を結んでいってくれるといいな。次はどうなるのかな。