2 1 4 3 という順列は前半後半の２グループに分かれていて、１回のスワップで達成できる辞書順最小は 2 3 4 1 なので、1 と 3 をスワップする必要がある。何をどう判断して 1 と 3 をスワップすることができるのか。さっきのルールでは 4 を見ているときに 1 を引っぱってくることになって良くない。グループの末尾の位置にあっては多少の妥協をして現在の要素より大きい値を引っぱってくることになっても他所のグループとスワップをしなければいけない。それで 1 を見ているときに 3 を引っぱってくることができる。そうした結果が本当に辞書順最小かというのは実はよくわからないところだけど……。■提出 #46663066 (TLE×18) のち 提出 #46665195 (AC / 772 ms)。アルゴリズム的な違いはない。スワップ候補というのは１度に２つだけ準備できていればいい。最小の要素を持つグループと、２番目に小さい要素を持つグループ。現在見ている要素と異なるグループが実際のスワップ対象になる。この２つの要素を配列の外に出して変数で参照するようにしたりして配列参照を減らしたら TLE が AC になった。■グループの管理とスワップ候補の管理を同時に行うために、UnionFind のルートの決め方をいつものようにサイズの大きい方を新しい代表にするのではなく、値が小さい方を新しい代表にしている。そうすると Find 関数での書き換え回数が増えてまずい場合があるのだけど、代表と最小要素を別々に管理するのは煩雑でミスが避けられない雰囲気だったのでそうしている。スワップ候補の列について。最初にソートして用意するんだけど、スワップ１回につき１つの候補が列から消えることになる。現在見ている要素の代表が消える場合もあり必ずしも先頭２要素のどちらかが消えるとは言えないし、Ruby には SortedSet がない。今から BIT を持ち出すのは大仰で気が進まないし、消す操作を配列に対して素直に行うと実行時間が足りないので、スワップ候補の先頭２要素についてだけ今もまだスワップ候補(グループの代表)のままであるかチェックをするようにして、結果的に削除操作を遅延させている。こういう部分であるとか、数列を先頭からひとなめするだけで辞書順最小を達成するだとかいう部分があるから、効率良くやるのがたいへんな問題だったと思う。スワップするためには最小の要素がどこにあるかを知る必要があって、それを追跡する逆引き配列を予め作成してスワップの際には同時に更新しもしている。たいへんだなあ。そのときそのときで全体を見て最適な選択ができたならもうちょっと簡単だった。■昨日のコンテスト成績証。解くべき問題を解いて -5。まあ順当。B 問題が解けたのえらかったと思う。約分なんて高等数学テクニックとか式をにらんでの２の素因数探しとか、そんなんもう何十年も前に忘れてんねん。■■■「そうした結果が本当に辞書順最小かというのは実はよくわからないところだけど……」。この問題の設定においては位置と値が等価だということをよく考えれば納得できるのではないかな。「グループの末尾の位置にあっては多少の妥協をして現在の要素より大きい値を引っぱってくることになっても他所のグループとスワップをしなければいけない」と書いたけど、この「グループの末尾の位置」というのは必ず１を含むグループの末尾のことだし、「他所のグループ」というのは必ず全メンバーが後方を占めているグループのことなので、そういう関係を踏まえればスワップの位置づけがわかる。いや……、考えれば考えるほど「必ず１を含むグループ」であるということが俄には承服しがたいな。やっぱりそうだと思うんだけど。A.all?(A[0]) でも A.uniq.size==1 でもお好きな方で。■B 問題「3-smooth Numbers」。素因数が２と３だけかどうか確かめる。２と３で割れるだけ割って１になるかどうかでわかる。■C 問題「Error Correction」。これ３つの問題がひとつになってるよね。強いて言えば２つは対称な問題だったので、２種３通りの解答を書くのがとても面倒でした。文字数が１つ多いときは、１度だけ比較をスキップできるということ。それで他の全ての文字が一致するなら可能性がある。文字数が１つ少ないときは、文字数が１つ多いということです。■D 問題「Square Permutation」。意外に Ruby での AC が少なかった問題。13 の階乗は数が多すぎるので、平方数の方から攻める。２乗して 13 桁を超えるのは数百万くらいの数からだったので列挙できる。ところでね、サンプルの２に「異なる並べ替え方でも、並べ替えた結果の数が同じなら 1 つと数えることに注意してください」と書いてある。そんな大事なことは本文に書いておけよと思って今読み返してみたら。本文には「
(1,…,N) の順列 P=(p1,p2,…,pN) によって i=1∑Nspi10N−i と書ける整数のうち、平方数であるようなものがいくつあるか求めてください」と書いてあった。うーん？ 順列ではなく順列によって表される整数を数えろって書いてあるのかな？ まあいいや。自分のこの提出(#46569450)には順列を数えた部分がコメントとして残っている。無駄な時間を使ったぜ。しかも最初の提出は WA×1 だった。ゼロは平方数に入りますか？ 入るみたい。式をよく見ると順列を数える場合でも答えに足すのは固定値なんだな。単に大きな固定値を足すか１を足すかの違いでしかなかったのに、つどつど無駄に数を数えていたのは自分が足りないせいだったな。■E 問題「Joint Two Strings」。これも最初は違う問題を解こうとしていた。この問題の部分文字列とは連続とは限らない部分文字列のことでした。問題文にちゃんと書いてあるんだから、読むだけでなく頭に入れてくださいね。制約が大事。「
S1,S2,…,SN の長さの総和は 5×10^5 以下」と書いてあるのだから、S をなめるような処理を書いてその中で T をスキャンしたりしなければ間に合う。S ごとに T を前から何文字カバーできるかを数え、同じように T を後ろから何文字カバーできるかを数え、足して T の長さより短くない組み合わせを数える。これは罠なんだけど、入力の N は T の長さではありません。今日の入力は、C 問題 と E 問題が共通して変則的だった。なぜ関連するわけでも同種でもない入力を１行にまとめるのか。(たとえ使わないにしても)今回に限って文字列長を先行して与えないのはなぜなのか。入力の処理が面倒だった。■F 問題「Beautiful Path」。比率は扱いが難しい。最終的に分子を最大化して分母を最小化したいんだけど、中間値についてたとえば比率が同じでも (美しさ)/(コスト) = 100/100 と 10/10 を同列に扱ってはいけない。100/100 を 10 % 改善するには美しさを 10 足す必要があるけど、10/10 を 10 % 改善するのには美しさを 1 足すだけでいい。以前に濃度の問題を２問解いている。「Sugar Water 2」(20230319) と「食塩水」(20220714)、それともうひとつ「おまかせ」。それでもやっぱり解法に悩むし 30 分はかかるんだね。途中で G 問題を読んだりなんかもして、でも F 問題の制約が「１アイデアで解けるよ」と訴えていたので F 問題に注力することにした。解法は以前の日記に書いたように、濃度を決め打てば溶質の過不足が具体的な値として求まるので、これを最大化するようにして最終的にゼロを上回ればいい。二分探索で。■コンテスト成績表。遅い６完だったけど青パフォでした。明日の ARC にはいくつのレートを捧げることになるのかな。■D 問題。提出 #46587508 (gmmtea さん / 971 ms)。他の Ruby の提出にほぼダブルスコアの差をつけて１番早い。列挙に工夫があるのかなと思うけど、よくわかんないことをしてる。すごい。■ちょっとお風呂で考えて Send More Money (20210412p01) と共通点があるかと思った。あれは DFS で無駄なく列挙することで４桁 ms が２桁 ms まで劇的に縮んだ問題だった。この問題も２乗する数を１桁ずつ確定できないかなと思った。確定済みの値が cba で次の桁が d のとき加算する値は d000 であり、２乗した数は (d000+cba)^2 = d000*d000+2*d000*cba+cba*cba になる。増分は d000*d000+2*d000*cba の部分。増分の末尾ゼロ３つが確定しているので平方数の下３桁には影響を与えられない。そんな感じで平方数の確定した桁と使える数字とを見比べて違反があれば即座に以降の列挙を打ち切れるのではないかなと。実際にやったけど答えが合わないしサンプルの３が却って遅くなったのでやめにした。
(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 を思い起こさせる問題ではあったかな。そっちの方がひどいね。■計算量のことを考えないなら、操作区間の先頭と、操作により最初に置き換えが起こる位置のペアを考える。置き換えが起こる位置が最も後ろのもので、区間の先頭が最も前のものが答えだと思う。結局のところ、計算量を改善するアルゴリズムを組み立てる問題だった。ケチなことを考えると色々ミスが出るのはしかたないね。