8772053214553.691 な一方、出力例が 8772053214538.5976562500 となっている。差は 15 とちょっと。これが「出力は、真の値との絶対誤差または相対誤差が 1e-6 以下のとき正解」という条件を満たすかどうかの判断がひとつの分かれ目だったらしい。自分は何か月か前あたりに、絶対誤差と相対誤差を正確に計るとこういう式になるのだけど……(でも必ずしも停止条件を厳密に計る必要はないよね)、的な文章を読んでいて、大きい値の相対誤差は(絶対値的には)そこそこ大きい値でも許されるんだなあ、というような、今では式もよく覚えてないけど意外性の発見があったことだけは覚えていたので、通るような予感があった。祈りながら提出して 1 WA でも返ってきたらどうしようもないなと戦々恐々としていたのも本当のところだけど。解法は g を探索する整数の二分探索(Range#bsearch)。だけど g におけるタイムと g+1 におけるタイムを比較して判定条件にしたので実質的には三分探索だった。こんなに簡単素直な解法でいいのかと疑ったけど、20210401p01.03 に書いたように ABC174-E「Logs」が自分が初めて解いた解を二分探索する問題で、二分探索に対する発想の転換があるまでは解けなかったことを思い出すと、D 問題でこの素直さはありなのかなあとも思った。早々に解析解を提出している人はすごいね。分数とかルートとか、もはや紙と鉛筆があってもなんとかなる気がしない。■E 問題「Cheating Amidakuji」(水 diff)。題意を理解するのがちょっと難しい。ざっくり言うと、A 数列の値に従って B 数列の隣接２要素のスワップを繰り返したとき、B 数列の要素１がどこへ移動するかを追跡する。A 数列の要素の１つを無視した場合(スワップを１つ飛ばした場合)の答えを A 数列の長さと同じ数だけ答えてね、という問題。スワップ対象の
B_{A_k+1} が B_{A_{k+1}} と紛らわしくなかった？ HTML ソースを読んで判断したよ。結局は同じことをしているのかもしれないけど、人によって全然解法の背景にある考え方が違いそうな気がする。自分はといえば、まず最初に A 数列を順番に使用して B 数列のスワップを最後まで完了させた。そして B 数列の初期位置と最終位置の対応を記録した。そして B 数列を初期化してからもう一度スワップを繰り返した。その際に、A 数列のこの要素が関わるスワップを飛ばしたとしたら答えにどう影響するかを考えた。スワップする２つの要素がどちらも１ではなかったら、１の最終位置は変化しない。どちらかが１なら……。■■■@2022-12-07 F 問題を振り返ってなかった。F 問題はボールから箱を引くデータと、箱から箱ラベルを引くデータと、箱ラベルから箱を引く３つのデータを用意した。最初からこの方針だったのだけど、Find 関数の停止条件が明らかではなかったり、箱と箱ラベルを混同したりでなかなかサンプルが合わせられなかった。合ったら合ったで TLE だったしね。箱というのが普段の UnionFind で取り扱う頂点なのだけど、この問題では箱が表に出て来ない。ボールや箱ラベルから間接的に参照されている。こういうのは初めてだったし、要件に対して用意するのがこの３つのデータで間違いないという確信も持てないまま実装していた。自分としては ABC273-E「Notebook」(青 diff) を解いたときと同じ頭の部分を使っていたのであり、そのときみたいにさささっと８分で解きたかった>20221015。でもこっちの問題は骨格を決めた後の実装がちょっとややこしかったね。G は i 回目の移動で頂点 u にレベル X で来る確率が p だとすると、知りたいのはすべての i と」 これがヒントであって答えでないのは、これを読んでさえさっぱり遷移が書けなかったから。何度も何度もガチャガチャやって考えてガチャガチャやって考えてお風呂に入って考えた。提出 #36502350 (TLE×13)。書けなかったのは 29 行目と 30 行目と 32 行目。それで苦労の結果が TLE。計算してみたら N,M,K≦3000 で Ds.size=3 で E.sum(&:size)=2×M で C0.size+C1.size=N だからループの回数が K×(3×2×M+N) = 6300 万。Ruby は 1000 万回を超えたあたりから厳しくなってくるのでこのままでは無理だよ。C_u=1なる u についてpX^2の和。(i,u) を状態として\sum pX^2を管理しようとすると、レベルアップの処理が\sum pX^2\rightarrow\sum p(X+1)^2=\sum pX^2+2\sum pX+\sum pとなる。よって\sum p、\sum pX、\sum pX^2を管理しておけば更新も含めて計算できる。
sumf 変数をこの式にしたい。最初の提出の時点で考えなかったことはないけど、全然まとまらないねってそのときは思った。HI/LO を入れ替えた２つの和を左からと右からでまとめてるっぽい？■D 問題「XOR Tree Path」。最初はビット列を掛け合わせて寄せていく解法(名前がわからん)かと思ったけどだんだん木 DP が見えてきた。葉ノードから寄せて上げていく。記録するのは、反転操作を親に伝播させるときに部分木がいくつの黒ノードを含むかと、そうでないときにいくつの黒ノードを含むか。木 DP の肝は子ノードのマージ部分だけど、ここに罠があった。子ノードが１つしかないときに「反転操作を親に伝播させるときに部分木がいくつの黒ノードを含むか」という数字を反転しない場合の数字に反映させる方法はない。反転操作を打ち消し合う他の子ノードが存在しないから。提出 #36339752 (AC / 602 Byte / 286 ms)。■E 問題「Name Value」。制約が、特に A,B 文字列の長さがやばすぎるだろうと思ったけど、クエリ文字列のスキャンが前方/後方から貪欲に行えるので、それを効率的にやるために準備を頑張ればいい。文字種×(A,B 文字列の長さ) = 2000 万要素くらいの遷移表を用意して許されるのか考えたよね。うーん、ありかなあ。でも１要素ずつスクリプトでコピーするとダメかも。提出 #36341147 (AC / 509 Byte / 1309 ms)。許された。最初は遷移表に添字を記録していたけど、遷移先の遷移表を持たせるのがより直接的ではないかと気がついてそのようにした。人間が脳みそに余計なステップを持っているとコンピュータにも無駄な回り道をさせがち。こういう無駄を詰める思考はコードゴルフと通じている。提出 #36348178 (AC / 392 Byte / 1216 ms)。Array#dup メソッドの呼び出しを省いた(20201207)のと遷移表のサイズを半分にしたのと無駄な Array#min を省いたのと添字を記録していたなごりの無駄な変数を省いた。遷移表のサイズを半減した引き替えに整数の引き算がループの中に４回出現している。メモリ大量確保＆コピーとちょっとした整数演算ではどちらが時間を食うかという判断。平均的に速くなったけど重いケースではそれほど変わらず。１度に１要素しか更新しない遷移表を毎回丸々コピーするのがもったいないんだよなあ。空間がではなく時間が。でもたぶんそれをやめると探索が必要になって log が付くのでは？ インチキみたいなうまい方法があればなあ。遷移表の行と列を入れ替えるみたいな方法はたぶんうまくないんだよなあ。２要素の遷移表……。■F 問題からは解けません。■G 問題「Count Arithmetic Progression」を考えてる。傾きに注目するにしても直線の切片に注目するにしても 10 の 12 乗以下という制約がネックになって部分点しか得られない(答えが違えば部分点ももらえないが)。注目するなら 30 万以下の要素しかない L,R 整数列になるのかなあ。それで解く方法が見えないけども。@2022-11-11 部分点をもらいました>提出 #36390042。部分点の制約でも青 diff は下らないと思うなあ。探索できる要素ってある？ １ずつ計算せずに済むような単純な比例関係があったりする？ どっちも(見つから)ないんだよなあ。DL,DU 変数を賢いデータ構造で仮想化して妥当な計算量で求められるとしたらどう？ DU,DL 変数は傾きの上限下限だから傾きを制約する数字が連続的に変化していったら結局 10 の 12 乗に比例したステップが生じると思う。まとめてひと束で計算できる状態の単位が見えない。数列の要素数に比例したステップしか生じなかったりする？ じゃあ傾き制約の変化点を順に知る方法は。■@2022-11-16 解説を読んだ。Convex Hull Trick の名前を知った。「Convex Hull Trickを知っていますか？僕は知っています。 - Qiita」「傾きの単調性が要らない Convex Hull Trick - kazuma8128’s blog」 読んだ。直線をソートして順番に交点を求めて上限/下限の変化が知れるらしい。蟻本で既出だったことも知った(初版 286 ページ K-Anonymous Sequence)。しかし書けない。0=a1<...<an=M-5 や 5=a1<...<an=M など、初項 a1 が取り得る値が 0 から 5 の 6 通り考えられるのでこれを掛ける。困ったのは、+3 操作の上限を決めて 0 個、1 個、2 個と挿入する場合の数の合計も、+1 操作の上限を決めて 0 個、1 個、2 個と挿入する場合の数の合計も事前に累積和を計算しておくことで定数時間で求められるのだけど、初項が取り得る値のバリエーションを累積和に掛ける方法がわからなかった。たとえばメインループで +3 操作の回数を決め打ったとする。追加で可能な +1 操作回数の上限がわかるので累積和を引く。しかし +1 操作回数が 0 回のときに初項が取り得る値の種類数と 1 回のときに取り得る種類数は異なる。+1 操作の選び方に階段状の倍率を掛けたものの累積和が欲しい。倍率はスライド式であり、×5,×4,×3 かもしれないし、×3,×2,×1 かもしれない。あるいは初項の前へのプラス操作が他と統一的に数えられたら。困ったときはお風呂で考える。普通の平坦な累積和と階段状の累積和を組み合わせればいける。いけなかったのは、N,M の制約上限が普段より厳しい 10 メガなのであり、コンビネーションの事前計算に加え累積和を２本も作成する 3N の処理で制限時間の４秒を超えてしまったこと。10 秒まで実行されるコードテストで 4.4 秒からなかなか縮まなかった。■提出 #36313584 (AC / 773 Byte / 3938 ms)。C1 メソッドの値から A 数列を作成するときに呼び出し回数を半分に節約したり、メソッドの中身をインライン展開したり、メインループの共通項を ICI として括り出したり、fn 数列の前部を切り捨てて添字のオフセット計算を省略したり、いじましい努力の結晶ですよ。Ruby によるすべての提出を見ると、tinsep19 さんの提出は最悪ケースこそほぼ同じタイムだけど、内訳を見ると１秒早かったり倍早かったりするものが多い。４秒ぎりぎりの最悪ケースの位置が異なってるのが面白い。向こうの最悪ケース(１つだけ)はこちらの最悪ケース(13 個)ではないのだ。■メインループを逆順にすると必要なのが累積和の末項だけになって事前の作成が不要になる気がするなあ。■提出 #36318378 (AC / 736 Byte / 3061 ms)。メインループを逆順にして累積和が配列２本から変数２個になった。*smallN* ケースだけやけに遅くて最適化の余地があるみたいだけど、それ以外は概ね良好かな。汚いという意味では良くないけど。■「スナネコ「ABC276Gの解説に追記しました」 https://t.co/9pw10g1SOS https://t.co/bRGlSd8RcW」。異次元からの眺め。さっぱりすぎる。