ABC132

新ABCのrated回で初めて全完嬉しい!心の調子は悪いと思っていたけど、なんか簡単だった(つまり得意なセットだった)。結局、立ち回りとかじゃなくて問題との相性で決まっちゃうのかね。Eを通して37.1、全完して37.0。すぐ解けたからというのが大きそうだが、わりと落ち着いてやれた。

今回もややトラブルがあった。この前の救済措置で自分のパフォ思ったより落ちたんで、被害にあった人の被害はけっこうでかいのだろうと思う。(「Pythonだけ不利」みたいのは絶対ダメだけど、条件が同じとか運次第とかならratedでいいとは思ってる(得意セットだったとかもぶっちゃけ運だし))

A - Fifty-Fifty

問題が表示されるまでに50秒くらいかかった(ちょっと勘弁してほしい(自分が有利になるとしても))。かなり面倒。p[26]={};しようかと思ったが、さすがに牛刀かなあと思い、ソートして条件を書く。全部同じ文字でもダメなのが難しい。

B - Ordinary Number

簡単じゃんと思い、2番目判定が面倒なことに気づく。別の配列にコピーしてソートした。

C - Divide the Problems

これは考えれば簡単。ソートして真ん中で二つに分ける、つまりd[n/2-1]とd[n/2]を分けることができるか。あの今気づいたんですけど分岐不要でしたか(これはつらい)(d[l - 1] == d[l]とd[l] - d[l - 1]がまとめられることには気づいていてそのまま提出した)(今回は精神的体力のなさを自覚して全体を通し省エネ殺法で臨んでいた)。

理想的なABCのCという感じでかなり好き。

D - Blue and Red Balls

仕切りを入れるやつね。「ほんとに足してnCkになるのか?」って気にしてたけどまあ普通に解いて提出しちゃった。青と赤の両方で仕切りをやって、赤のほうは両端は0個でもいいという。まあ解けたんだけど、背後に何があるとかはわからないね。

E - Hopscotch Addict

最短経路を求めるなら簡単だが、これは長さが3の倍数の経路を求めたい。とりあえず、最短経路を求めて3の倍数なら答えがわかる、というところまではわかる。しばらく考えて、頂点を3倍にすればいいと気づく。何だっけ、けっこう前のchokudaiさんの(個人のではない)ニコ生で頂点を2倍に増やすダイクストラ法をやってて「へーすごい」って思ったのが印象に残ってる。エネルギーを節約するため、BFSではなく、使い慣れたライブラリのダイクストラ法を使う。ていうかこれも3回やる必要なかったですか。対称性から1回でよかったのでは。言い訳すると、s*3からt*3+1へみたいなことも考えてたので。同じ色(言葉にはしてなかったが頭の中では頂点に3種の色が付いていた)のゴールへ行ければいいのね。で、解説読んで気づいたけどDFSでも行けるん!(ん、ちょっと計算量がわからんけど(あれ、アルゴリズムをわかってないのか))

DもEも普通に解いただけのつもりが、相対的にはかなりの早解きになっていた。その余裕から、EとFを落ち着いて考えることができた。

F - Small Products

パッと見簡単そうだけど、状況を把握すると捉えづらい。ただ、これいかにもDPという形をしている。O(N*K)のDPができそうだ。さて、たとえば数列が3で終わってた場合、次の数はN/3以下ならいい。つまり、O(√N)の個数にまとめて考えることができそうだ。しかしここからが大変だ。1から√Nまでと、Nを1から√Nまでの数で割ってできた数を境界とする区間。2種類を扱うからね。DPするのにj以下の通り数にするかjの通り数にするかも迷った。順番に累積やっていくイメージはあったので、「累積要らないんじゃ?」「でもそれだと伝播しない」「じゃあもっと簡単に解けるんじゃ?」という思考をした。しかし、もっとよく考えると累積の向きが逆だ。ここは本当にややこしい。幅が1でない区間区間内のどの数を選んでも同じことなので区間の幅を掛ける。もう思考が無限ループするのだが、なんとか対称性があると信じてきれいに書くことで答えに近づこうとする。サンプルは合わないが、まだ粗削り。0番目の数の左に1があると考えてもよいのでDPの初期化はもっと簡単にできた(コメントアウトして一応残す)(同じことを2回書いたら怪しいと思うべきだなあ)。サンプルが合わないのは√N付近の処理だろうからそこをちゃんと考える。N以下N/2より大きいという区間があり、...、N/(int)√N以下N/(1+(int)√N)より大きいという区間があり、(int)√Nだけからなる区間がある。3つ書いたけど、真ん中のやつ。これN/(int)√Nは(int)√N以上なので最悪でも区間の長さを0にすればいい。N/(1+(int)√N)っていうのが間違いなので(int)√Nだけから成る区間と被らないように調整する(要するに「(int)√Nより大きい」とする)。これでもサンプルは通らない。しばらく考えて、これ累積の向きが別の意味で逆だ。どうしよう。forループを全部逆にするだけでいいのではと気づく。ループの向きを逆にして2つのfor文を入れ替える。サンプルが通った!もう一山ある可能性も考え、すぐ提出。AC。

この内容で全完は本当に嬉しい。Eまでの早解きと、重量級のFをやり遂げたこと。Eの早解きでそれなりの順位が保証されていたため、Fの実装で困っているときにいつものような焦燥感がなかった意味はある。そんな中でも淡々と(当時は進んでいるかもわからない状態だったが)解き進めることができた。結果的に、全完までのスピードもなかなかのものだった。