2 人ともが話すことの出来る言語が存在する」ことと「
2 人ともが X とコミュニケーションを取ることが出来る」ことの違いをよく意識しなければいけない。２つの条件でそれぞれ使われている「共通言語が存在する」ことと「コミュニケーションが取れる」ことはイコールではない。共通言語の存在は再帰関数の停止条件であり、コミュニケーションが取れることは共通言語の存在により再帰的に定義されている。後になって問題を反芻していたとき、X 以外の別の人間を介在させてコミュニケーションが取れると判断してはいけない気がして、なんで AC だったのか疑問に思って問題を読み直して、表現の違いに気がついたのだった。■なんだかんだで青 diff が半分くらい埋まってきてるので、そろそろ青入りさせてくれてもいいんですよ。
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を管理しておけば更新も含めて計算できる。