死にました。こう、反例に気づく力って大事よね。 あと文章読解力。まだ速解きしてれば死ななかったんだが・・・w というわけで今回はABの2完でしたとさー。perf1200くらいじゃねーのこれｗ
$n$ の大きさが無限大までいけるってことに気づかないかねー。 $n$ が 合成数ならOK.ただし素数のべき乗の値はだめ。 ある２つの値、$n$ の何らかの素数で割った約数ともうひとつこれとは違う何らかの素数で割った約数を用意する。 これでもまだ $N$ にとどかないので、あとは $1$ を入れ続けると、作れる。
まず $K$ 回単調増加してるところがあったらただ $P$ を出力すればいい。 そうでない場合、絶対に $P_{N-K+1}$ よりも左の値を変更してはいけない。 なぜなら、一番右でソートした値よりは小さくなっちゃうからだ。 だけれど、例えば、$P_{N-K}$ がその右にある $K-1$ 個の値よりも小さかったら、 ソートしても $P_{N-K}$ は位置を変化しないので何も変化がない。 しかも、ソートするところを左にずらせるので、一番右でソートするよりも辞書順で大きくなる。
次に $P_{N-K-1}$ についても $P_{N-K}$ よりも小さいことをまず条件にして (これがないと$P_{N-K+1}$ よりも左の値が変わってしまうため)、 $P_{N-K}$ がその右にある $K-2$ 個の値より小さかったら・・・というのを見ていく。 これをどんどん左に調べていく。以後見ている数列は単調減少でないといけない。 とにかく添字 $N-K$ 以下の $P$ を変化させず、ソートができればOK.
これを調べて、一番左でソートできるところを探しておしまい。
一番の肝が$N-K$ 以下の添字のものをいじっちゃいけないということだった。 あとはソートを検討するだけと考えれば考えが単純だったのかもしれない。 そこに気づかなくて、反例を持った考えを大量にしてしまったのが遅解きの原因となった。
時間をBで食ったのでそこまで見てない。わからないー。最大流を疑ったけど違うよねこれ。
今回は辞書順の問題がやけに多い気がする。これも全然わからず。
まだ問題すら理解できてない。見たは見た。
ソート系？はなにか感じるものがあるが、当てた考えはだいたい崩れ去った。
普通に難しいと思う。ただ B はそんなに難しくなかったはずだから、速解きできたと思う。
速解き出来ていればこんな悲惨なことにはｗ
昨日言っていたパフォの下限の話が全部次の日にパーになるとは思わないじゃないか(perf=1397 水！)。
まあ、そんなに気に病まないでやっていきたい。