脳log[20240424]

2024年04月24日 (水) [AtCoder] 精進。「最近解けていなかった期待値の問題」３問から２問。■ABC314-E「Roulettes」。これもループを含む試行。「素直な問題設定」だった ABC350-E「Toward 0」と何が違うというのだろう。何も違わないと思う。でも難しく感じる。ABC350-E に提出した解答を想起しながらなぞるようにしてやっと解答が作れた。提出 #52759461 (AC)。■同じく ABC314 から F 問題「A Certain Game」。見え見えの UnionFind なのはわかる。でも UnionFind をしながら期待値をどこにくっつけるのが適切か、その期待値はどういう意味合いの数字か、よくわかりません。試合をした２チームを UnionFind で併合する。その後の期待値の増減は併合されたチームメンバー間で共通なので、根っこの期待値を代表にして操作する。ではメンバー個々が保持する値は何か。根っことの差分だけど、どこで根っことの差分が生じるか。勝ったチーム負けたチームと、大きいチーム小さいチームが必ずしも一致しないのがややこしいけど、小さいチームの期待値は試合後に大きいチームの期待値を基準にした差分として表現されるので、チームの併合操作の前後で小さいチームの期待値が変化しないように、大きいチームの期待値を打ち消すようにして差分が生じる。提出 #52760322 (AC)。……ということが理解できてから実装を始めたけど、重み付き UnionFind の実装は死ぬほどややこしい。E 問題の AC から１時間 20 分ほどかかっている。それはコンテストが始まってから終わるまでの時間とほぼ同じだ。■「最近解けていなかった期待値の問題」を具体的に特定してから書いたわけではなかったけど、あと心当たりがあるのは ARC174-C「Catastrophic Roulette」。この３問あたりが最近の解けなかった期待値の問題だったと思う。もう今日は ARC-C まで考える気力がない。■F 問題。Ruby によるすべての提出を眺めてると、どうやら、前半で UnionFind をしながら必要な情報を付加して、後半で逆向きにたどる構成の解答がほとんどみたい。うーん？