ABC252

7完。Eまで通してFGを読んで順位表を見たときは予想よりだいぶ低い順位だった。FもわからんしGは難しそうだし、苦手セットだと思った。が、順位表を見てFの解法を思いつき未証明で通し、Gは区間DPがわりとすぐ見えて、いい順位に。これで黄色復帰。青に落ちて(落ちたこと自体はたまたまだと思うけど)少しして初めてスマホを持ったりして、なかなか調子が戻るタイミングがなかったけど、ようやく。

A - ASCII code

charにキャストして出力するだけ。やや怖いので何か間違えてないか確認したが、それ込みでも33秒。

B - Takahashi's Failure

やや複雑だが、それでもB問題レベルの簡単さ。最大値を求めて、それが嫌いなものの中にあるかチェック。問題文の意味がとりづらかった。

C - Slot Strategy

リールが知らない言葉だったけどまあわかる。同じ位置に目的の数字がある複数のリールを同時に止めることはできない。ということでシミュレーションでいいんだが計算量がパッとわからない。なのでNが大きくても使える解法を採用。どの数字に合わせるかを固定し、その数字がj個目にあるのが何個あるかをカウント。その最大値の回数だけ周回する必要がある。ただし、最後の周は最後に現れる最大値の場所まででいい。すっきり解けてはいるのだが、階層がかなり深く抽象的になっていて自信がなかった。

D - Distinct Trio

難しい。包除とそれ以外で迷うが、どちらも見えない。しばらくして、単に3個とも同じ数になる選び方と、2個が同じでもう1個がそれとは違う選び方を引くことができると気づいた。2個が同じとき、仲間外れの1個の位置関係を固定するとわからなかったが、固定しなければ単に自分と違う数の個数でいい。10^6以下の数の3乗なので気にせず計算して大丈夫。ループを2*10^5回回す。

E - Road Reduction

こんなの解けるわけがない。プリム法っぽさは感じるので、現在の(頂点1を含む)木につながる辺であって頂点1からの現在の木にその辺を加えたものでの距離が最短のものを貪欲に選んでいく。手でいくつかの例を試し反例が見つからなかったのでそれで実装して提出。未証明どころか何の言い分もなくそれっぽく解法を錬成しただけ。実装にもけっこう時間がかかった。運良く(?)AC。

なんかこれ、ダイクストラ法っていうらしいです。解説読んだけど、いや確かにダイクストラ法ってそういうふうにやるよな。いやダイクストラ法なのかこの問題で問われていたのは。全然気づかなかった。そうだったのか。各頂点への最短経路を重ねて木にすることができるのか。言われてみればそうなりそうだ。あと、自明な上界が達成できるという問題でもあるんだな。これも気づかない。

F - Bread

二分木を描いて、葉以外のサイズを最小化したい。わからない。ここでGも読んでから順位表を見る。Eを通したのに順位が悪いのにも驚いたが、Fもけっこう解かれている。それを見て、逆から考えることを思いつく。バラバラのパンを全部つなげる最小コスト。余るパンが1つでいいかもわからなかったが、逆から考えれば1つでよさそうに思える。つなぐときは、できるだけ合計が小さくなるように。最終的には同じだから、最初のほうを小さいの同士、やはり二分木の平衡みたいになる。priority_queueで小さい2個を合体させていく。パンが余らない場合の処理が間違っていて、サンプルに助けられた。未証明AC。

G - Pre-Order

手でいくつか試して、順列に意味がある(Nが同じなら同じ答えになるとかではない)ことを確認。先が見えない問題だけど、DPを考えたときに制約がまさに区間DPで、行きがけ順は区間だ。何かの子というか、部分木から根を除いた部分とO(N^2)個の区間を対応させ何通りあるか求める。迷ったけど、普通の区間DPと同様に幅が小さいものから計算していく。幅が1以下は1通り。区間のうち、最初の1個は最初の子になることが確定。それ以外を、最初の1個の子孫とそれ以外(最初の1個の兄弟)に分けるのを全通り試す。兄弟は(存在すれば)最初のより大きい番号でないといけない。全体で時間計算量O(N^3)。思いがけず短時間でAC。