(K-x).downto(0){|i| ds[i+x] += ds[i] })があえての降順なのはなぜか。今ループの遷移結果に対して再帰的に遷移操作を施してはいけないからだ。+x 操作が 0 を x に移すのも x を 2x に移すのもいいが、0 から移ってきた x を 2x に移すのはやりすぎ。DP 配列を遷移回数と同じだけ用意して退屈なコピー操作を書くのもひとつの方法だけど、ループを逆順にして書き込む前に読み込むことを確実にするのも手。巻き戻しをするときはそのような工夫が通用しない。すでに遷移が済んだあとの場合の数から、最終ループで加算した場合の数を求めて引き算しなければいけない。■提出 #46049349 (AC / 276 Byte / 1183 ms)。なんというか、きれいにはまって驚くんだけど、ループを昇順にすることで巻き戻しと再帰的な影響を取り除くことが同時にできる。■「この手の場合の数は母関数です。y^K の係数が場合の数です」というような内容をいくつか読んだけど、残念なことにそれはすでに武器を持っている人にしか役立てられない情報なのだな。(1+x)^N なら x^K の係数は自分でもコンビネーションで求められるけど、今回のように x の部分が何乗なのかいろいろな場合に、いろいろ掛けた結果 x が K 乗になるものがいくつあるのか知りたいとなっても、それこそ DP をして求めるしか方法を知らない。そしてそれができたら今回の問題は解けている。つまり「形式的べき級数解説 | maspyのHP」という武器を持っていない人間にとって言い換えはただの言い換えであって答えには近づいていない。残念だなあ。理解できないんだもんなあ。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 を思い起こさせる問題ではあったかな。そっちの方がひどいね。■計算量のことを考えないなら、操作区間の先頭と、操作により最初に置き換えが起こる位置のペアを考える。置き換えが起こる位置が最も後ろのもので、区間の先頭が最も前のものが答えだと思う。結局のところ、計算量を改善するアルゴリズムを組み立てる問題だった。ケチなことを考えると色々ミスが出るのはしかたないね。
ここで、1≤Pi≤8 が制約として保証されます」がどう活用できるのか。最初は８×８の 64 通りに qi+X を分類して答えを求めておけばいいかと思った。でも足りなかった。１から８までの LCM である 840 通りであれば足りた。だけど 840×N≦8400万は Ruby にはつらい数字。D 問題に続いて E 問題まで答えは出せても TLE というのは残念すぎるので、先日の精進(20230831)にならって C++ で提出したら 624 ms で AC だった。制限時間は３秒。Ruby でも２秒を切れるみたいだけど、どんな考察が求められているのかまだわからない。■F 問題「Fighter Takahashi」。薬を飲む順番を総当たりして許される制約。敵はポーションのまわりに集約できる。ポーションは直列と並列に並べられる。あとは効率良く総当たりしたいけど、うまく書けなかった。DFS でやるんかな。■■■F 問題。すでに飲んだ薬の集合をキーとして、倒せる敵をすべて倒したときの強さの最大値を記録したものを状態とする。次に飲む薬を選び、倒せる敵をすべて倒し、記録する。これでいけると思う。DFS だと飲んだ薬の集合ではなく薬を飲んだ順番を区別してしまうので、計算量が危険？ 10 の階乗はだいたい 370 万やからいけるやろって思ってたんだけど、案外遷移に時間がかかる？ つまり、倒せる敵を倒しつくすのに(※薬の倍率が１以上なので薬を飲む前に倒せる敵を倒さない選択肢はありません)。プライオリティキューを使って、敵の数×log(敵の数)＜5000。あっ、これはいけない。状態数を 1<<(薬の数) (1024 以下) に抑えてやっとなのだな。■ところで、Ruby ですでに AC になっている提出 #45433698 を答え合わせに使ってデバッグをしていたのだけど、こういう No ケース (４つの頂点が１列に並んでいて、１の直接の子が強さ９の敵) に Yes が返ってきて困ってしまった。答えが２択だとこういうこともあるかな。こちらは大丈夫みたい>#45434962 (require があって実行がやや面倒)。■提出 #45461169 (AC / 1755 Byte / 94 ms)。通った！ こんなに不安だった提出はそうそうない。Octopus (20230902) とか？ 提出をためらっているあいだに変数にコメントをつけたりなんかして。しかも２桁 ms なのが嬉しい。1.7 KB も文字を打った甲斐がある。ちなみにプライオリティキューは使ってないよ。敵は木構造を持って整列しているので線形時間のマージ操作を書いた。敵を倒すときも線形時間で走査する。これは５問目の橙 diff AC。ABC の高難度評価は当てにならないらしいけど、相対的に十分難しいのはたしか。
X.zip(L).map{|x,l| x-l }.min が十分。Ruby だから関係ないんだけど、制約が 61 ビット使うといっているので 10 倍 100 倍してテキトーに小さい数を初期値にすることをためらってしまった。それが WA の理由のひとつ。もうひとつが等距離にあるが右にあって近づいてくるお宝と左にあって遠ざかっていくお宝の扱い。近づいてくる方を短い触手に割り当てる方がお宝がつかめる可能性を高める。いやいやいやそんなんわかりませんて。ランダム入力を何十回試してもそれによる不一致は出てこないんだよ。まあ、無限ループなのでいずれ見つかるんだけど。■今日の日記にここまででタコの腕とタコの触手が出現しているけど、問題文ではタコの足になっている。実際のところタコのあれはなんなんだろう。「タコの足の本数は何本？タコの足の数はなぜ８本なの？腕が再生して９６本！ | BIJOH [ビジョー]」を読むと腕と足は間違いではないが触手には言及がない。触手について「無脊椎動物の体の前端や口の周辺にある糸状またはひも状の突起。先端に多くの感覚細胞が分布し、触覚や捕食の働きをする」と明鏡国語辞典に書いてあるのを読めば当てはまるような気がするが、違うと言われれば糸でもひもでもないからかなあとも思う。でもそんくらいしか違わないよね。ナチュラルに触手ってワードが出てくると、すわエロアニメによる刷り込みかという警戒心が働くのだけど、別に不自然な言葉選びではなかったのではないか。でもそれをここにこうして書くのはダメだと思う。
while b*b<=a; if a%b==0; c = a/b end b+=1 end なら AC で、while b<=c; if a==b*c; end c = a/b+=1 end なら TLE。AC の方では足し算１、掛け算１、剰余演算１が毎回で、約数が見つかったときだけ割り算が１。TLE の方は足し算１、掛け算１、割り算１を毎回やっている。剰余と割り算のコストが同程度なら剰余を求めないで済んでる分得かなと思うんだけど、そういう結果ではない。違うんだ？ ループ回数は同じだと思うし、どこで差がついてるのか本当にわからない。■３桁 ms の２つの提出(#20120433, #20414187)を読んだ。約数列挙に工夫があった。最初に素数を列挙している。たしかに１ずつ加算して割り切れるか確かめるより、素数について指数を調べる方が効率が良さそう。