AB小森健。Eの四完。紫に落ちました。辛い。
コンテスト後のツイート
C 区間が大きい方ブロックしていく。サンプルにあるけど、一個だけの区間もブロック可能なことに注意。
— titia (@titia_til) July 31, 2022
E トポソ順にマージしていったら通った。計算量も答えの最大値もよく分かっていない。
D. Magical Array
解法ツイートを見てAC。
不変量を探す問題なのだろう、とは思ったが、それを探すことができなかった。
正しい不変量は、
・i*A[i]の総和
・累積和の総和
（どちらでも良い。どちらも不変量）だった。
なぜ思いつかなかったかというと、A[i]とA[0]の差に着目してしまったというのが大きい。ある配列からの差分を考えているのだから、差分が重要なのだろう、と考えていた。
どう思いつけば良かったんだろうか。
累積和くらいとってみても良かったのでは、というのは一つある。
他には、Operation 1とOperation 2の違いは、足すindexが一つ違っているというだけなのだから、index*（何か）みたいに、indexを使った不変量があるはず、という風にして思いつく方向性もあったかもしれない。
解法ツイートで見たのだけど、配列を頻度分布とみなせば、操作1では総和が1増え、操作2では総和が2増える、ということから考えることもできた。
これは凄く自然で納得できる。が、頻度分布とみなすところが難しいなぁ。
0 件のコメント:
コメントを投稿