2 個以上の (相異なるとは限らない) 正整数」の和で N を作らなければいけないので、素因数が１種類しかないときには１の項を付け加える必要がある。■提出 #45760781 (AC / 150 Byte / 114 ms)。Ruby によるすべての提出を見ると不自然に１秒以上かかっている提出が複数あって、これなんでなんだろうね「
AtCoderの新ジャッジ、Rubyの一部提出がメチャ遅い実行時間になっているのだけど require 'prime' があると遅くなるみたいだなー」。■B 問題「Sliding Window Sort 2」。操作について気がつくこと。辞書順最大の数列が欲しいのに、範囲を昇順にソートする操作というのは得をすることがない。良くて範囲内がすでにソート済みだった場合の現状維持。N も K も制約上限が 20 万なので、範囲に対して愚直に線形時間でソート済みかどうか確かめて O(N^2) にしてはいけない。問題名に sliding とか window とか見えるからスライド最小値を使うことを考えた。つまり、ある要素がその要素から始まる K 個の区間の最小値であるとき、その区間は少なくとも操作の候補ではある。操作をしても先頭の要素が置き換えられることがないので、その１点では損をすることがないから。ところが話はもっと簡単で、ソート済みの区間が見つからないときはできるだけ後ろの方で操作をすればいいんだよね(本当に？)。■提出 #45778696 (WA×2)。ソート済みの区間は累積和で探した。サンプルの３によれば必ずしも一番後ろで操作するのが最善ではないとわかるので、直前の項を調べて操作区間をちょっとずつ前にずらすことにした。そうしたらみごとに after_contest に殺された。■提出 #45780788 (AC / 476 Byte / 164 ms)。説明が難しいな。ソート済みの範囲が見つからないとき末尾 K 個を操作の候補にする。だけど、新しく繰り入れる部分が操作による影響を受けない場合に限り範囲を少し前にずらすことができる。またそうすることで範囲から外れる部分を操作の影響から外すことができる。ずらす幅は最大で K-1 個分(※ K 個ずらして問題がないならソート済みの区間を見逃してたってことだ)。繰り入れる部分が広義単調増加(ソート済み)の場合に限る。また、最初に候補とした末尾 K 個のうちまだ範囲内に残っているものの最小値が新たに繰り入れた範囲に(操作によって)漏れ出してこない場合に限る(※この条件が抜けていたのが after_contest にやられた理由)。自分で解かないと何言ってるかわからんよ。結局この部分にスライド最小値を使うことになった。セグメント木でもいいと思う。これが B 問題で水 diff ってマジなのですか。でもまあ、A 問題で水 diff だった Reverse and Count を思い起こさせる問題ではあったかな。そっちの方がひどいね。■計算量のことを考えないなら、操作区間の先頭と、操作により最初に置き換えが起こる位置のペアを考える。置き換えが起こる位置が最も後ろのもので、区間の先頭が最も前のものが答えだと思う。結局のところ、計算量を改善するアルゴリズムを組み立てる問題だった。ケチなことを考えると色々ミスが出るのはしかたないね。