ARC099

2完。虐殺回だったね。僕は虐殺回わりと好きだけど、今回は自分の力のなさ・不甲斐なさを見せつけられてへこんだ。

C - Minimization

ちょっと考えると、全部1にするしかないというのがわかる。なんかNがKの倍数でN/K個に区切られてて区間を1個ずつ1で埋めていくイメージ。数に重複はないからN-1個の数を1に変える必要がある。1回の操作で1にできるのはK-1個まで(あ、K個ではなかったね)。なので答えはN-1/K-1を切り上げたやつ。んー、割り切れないときも有利にしか働かない気がするし、Kが2のコーナーケースも大丈夫そうだしまあいいかと提出。AC。3分台でかなりいいタイムだが、ちょっと俺の考察が軽い。今回はたまたまACだったが、細部をきちんと詰める必要があると思った。

D - Snuke Numbers

大体どんな問題かはすぐわかった。しかし具体的にどこなのかはさっぱりイメージできない。なんかグラフを描いて上か下に曲線(張った糸みたいな)を当てて糸と点が接しているところみたいなパターン。今考えると、NとN/S(N)をプロットしたんじゃそのパターンにはならんね(本当に?)。NとS(N)なら?いやわかんねえよ。まあまあその話はおいといて。
15分くらい考察して全然進まず難しすぎると思い実験に着手。1000くらいまで見てみると、けっこうわかりやすく規則性がある。少なくとも1の位が増えているときは、S(N)も同じだけ増えてNのほうが大きいのでN/S(N)は増え続ける減り続けるどっちだか忘れたよもう。ほんと認識しづらい問題だ。まあどっちかだとわかればいいのだ。で、まあそういう法則性があってもおかしくない。解説に難しい証明が書いてあるのが目に浮かぶ。きっとみんな実験してどんどんAC取ってるよ。俺も提出しよ。WA。
証明してないから100%俺が悪いですね。Nが100万までN/S(N)を計算して、逆から辿ってすぬけ数らしきものを出力してみる。ああ、普通に間違ってた。なんで行けるところまで実験しない。1024で終わらしたときはすぬけ数でないのも目視で確認してたからね。しかし100万以下のすぬけ数候補を表示させなかったのは意味わからんな。早くEをやりたいなあ。とか言ってね、もうね、早く楽になりたいんですよ。新たな実験結果を元に形だけの考察をして、考察は進まず、法則性に従ってコードを書き直し提出。WA。コードを軽くデバッグしてみたが、Sを求める関数がintだった。目視で確認する前提だったから意識してintにした記憶があった。そこを直して提出、AC。
なんか、500は通過点みたいに思ってたんだよね。そういうこともあるだろうけど、少なくとも今回は難しかった。しっかりした問題だった。それを適当に提出してWAをもらい、適当に提出してACをとった。あとからすごい自己嫌悪が襲ってきた。

E - Independence

DのACを確認してEの問題文をざっと読んで、そこから45分くらいは残っていた。連結成分は1つと仮定して、それを2つに分けたとき間にある辺を多くしたい、みたいなのを考えてた。太字で「直接」と書いてあるのに気づいたのは残り20分になったとき。なんじゃそりゃ。これは同じくらいのサイズに分けたいってことか。辺の有無を逆にするとか。いや調べるべき組み合わせが多すぎて無理でしょーとなって終わった。なんか色々問題外だった。
Highest更新した。こんなに嬉しくないHighest更新は初めてだ。