脳log[20220925]

2022年09月25日 (日) [AtCoder] 精進。昨日あったトヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)-F「Transportation」(青 diff)。すごく正統派の応用問題という感じで、解けて嬉しい。教科書で最小全域木を学んだあとで、さあ解きましょうと与えられるのにふさわしい問題だと思う。■道路と空港と港を使って最小コストで全域をつなぐ。２島間をつなぐ道路だけなら普通に UnionFind でクラスカル法をする。それに加えて、空港を造った島どうし、港を造った島どうしなら互いに行き交いできるとするとどうなるか。■港(空港)の建設コストが特殊なのは２点を結ぶ辺のコストではないというところ。１島だけが港を造ってもどことも繋がらないし、A 島と B 島が港を造って繋がるコストというのは、それだけにとどまらず A 島と C 島、B 島と D 島が港で繋がるためのコストの一部でもある。■原理的には、道路だけを使って最小全域木を構成する各ステップにおいて、各連結成分ごとに港の建設コストが最小の島に代表として港を造らせる、あるいは空港を造らせる、という仮定を置いてコストが計算できれば、道路と港と空港のベストバランスが発見できると思う。これは全探索なので非現実的な時間がかかる。どうにかして道路港空港の各手段を一列に優先順位をつけて並べて後戻りなくコストを調べたい。■頂点の偶奇を区別して同時に扱うために頂点数を倍加して UnionFind をしたりする。「おしゃれ解法@chokudai」の例もある。４つの平行世界を扱うために４倍の頂点を扱うことができる。４つとは、道路だけで繋がる世界、道路と港で繋がる世界、道路と空港で繋がる世界、道路と港と空港で繋がる世界(結果的に同時に扱う必要はなかったので４倍ではなく４回繰り返しただけだった)。港を必ず使う、空港を必ず使うと想定することで、港(空港)の建設コストを辺のコストへと変えられる。どういうことか。さっき書いた原理的な話において、港を使って繋がるとは、連結成分ごとに建設コスト最小の島に代表させて港を造ると書いた。全体を通して建設コストが最小の島は、どの連結成分に属していても必ず港が造られることがわかる(コスト最小が複数ある場合はどれでも１つだけ選んで決めて大丈夫)。１つを除いた他の島における港の建設コストとはコスト最小の島と繋がるための辺のコストと見なすことができる。■頂点４倍はコンテスト中に考えていた。全体で最小の建設コストが必須コストだということは終了後に考えていた。それでも昨日は答えにたどりつけなかった。サンプルの３が合わなかった。どうしてか。道路の建設コストの昇順に UnionFind を行うクラスカル法をベースにしていながら、道路をつなぐと同時に最初に仮に造っておいた港をなしにしてコストを節約するスペシャルな処理をしていた。これはクラスカル法だろうか。辺を処理する順番は島どうしをつなぐ真のコストの昇順になっているだろうか。変なところでオリジナリティを出してアルゴリズムの根幹を歪めては間違える。問題をアルゴリズムにあてはめる思考も必要。■提出 #35161366 (AC / 613 Byte / 1956 ms)。答えにつながる正解の方針がなかなか引けなくて四苦八苦していたのだけど、正解の方針はクラスカル法で決まっていた。珍奇な処理をでっちあげるより既知の処理に落とし込む方法を考えるべきだった。■港でつながる N+1 番目の島、空港でつながる N+2 番目の島を追加する解答を見た>提出 #35151300。スマートだなあ。何度か見聞きしてるけど頂点を追加する解法を自分で考えついて書けたためしがない。■イコール１文字のミスで二分探索を無限ループ化させてしまって TLE に終わった E 問題については書くまい。99% 解けていた問題より F 問題に時間を使う方がおもしろかったんだから。でもあれが通ってたら 50 分(+２ペナ)５完だったのになあ。自分のすべての提出。■■■E 問題。「E二分探索なんて頭いい事しなくても愚直スレスレの掛け算祭りで通るやん。rubyなのに」 二分探索はいらなかったらしい。自分の提出だけど、こっち(#35144735)がソート+累積和+二重二分探索で 151 ms。こっち(#35204328)がソート+線形探索で 138 ms。ソートのウェイトが大きいので大差はないけど、log^2 の有無で 10 ms ほど得をした、という感じ？