脳log[20211014]

2021年10月14日 (木) [AtCoder] 精進。ABC160-F「Distributing Integers」(ギリギリ黄 diff)。最近よく見る全方位木 DP。20210928p01.01、20211010p01.06。ノード間の式は ABC217-F「Make Pair」に提出したものと同じ(#25683515)。各ノードが自身を含めて A 個の子孫ノードを塗る方法(順番列)を B 通り持っているとき、２つの子ノード以下を塗る方法は B1×B2×(A1+A2 個から A1 個を選ぶ組み合わせ)で求まる。提出 #26559753 (AC / 1028 Byte / 1548 ms)。これで黄 diff の AC は９個目。かなり貴重。■■■全方位木 DP と言えば第八回 PAST の H 問題「最短経路」。制約が N≦3000 だから全ペア 900 万通りの全探索が想定解法かなーと想像したんだけど、Ruby にはやや厳しく見える数字。最近覚えた全方位木 DP で>提出 #26574539 (AC / 72 ms)。子ノードのマージ部分が全方位木 DP 問題唯一のアイデンティティ。各ノードに子孫ノードへの距離一覧をハッシュ表で持たせた。あとは全要素更新を避けるためのオフセット値を表とは別に持たせたりマージテクなどの時間節約術。ところで、提出した解法を全方位～と呼んでいいのかはよくわからない。全ノードを起点にした距離を調べてはいるんだけど、距離って指向性がないので頂点ペアを片方向しか調べなくていいわけなので、ただの木 DP と同じように根への１パスで処理が終わっている。■BFS で全点間距離を調べる方法はやっぱり厳しかった。ゴルフしながら１秒前後で通してる提出が多数あるからそうでもないのかなって思ってたけど、実際厳しかった。あの短いスクリプトのどこにどんなアルゴリズムがあるというのか。ともあれ最終的には BFS でも通った>提出 #26823765 (AC / 814 ms)。どういう時短術を使ったか。X を超える距離はすべて X 以上という扱いにしてそれより遠くの頂点は調べなかった。その場合でも最内ループでチェックをすると TLE がひどいので(#26823520 の 13 行目)、その１つ外でチェックをした(AC コードの 11 行目) (よく考えると TLE がひどいのは距離表の更新がスキップされてるからで、X を超えていてスキップするのはキューへの追加だけにすべきだった)。最も効いたのは、すでに距離一覧を調べてある隣接ノードの結果を流用したこと。そうすると、開始点から出る辺のうちの１本から先にあるノードは距離を調べずに済ませられる。そのために距離表はオフセット値とセットにして初めて実際の距離を表す。この点は全方位木 DP でのやり方と一緒。くらべて不利な点は、距離一覧ではなく具体的な頂点とのあいだの距離を一覧して持っていて等距離にある２点を同一視できていないので扱う数字が多いことと、結果の流用が辺の１本に対してしかできていないこと。これらの差で全方位木 DP に負ける。辺に重みがあるんだから BFS ではなくダイクストラ法を使うべきだというのはあるかも。実装も定数倍も重くて気が進まないわけなんだけど。■同じアイディアでちょっと前の ABC で制約が厳しくて想定解法のワーシャルフロイド法が通らなかった問題が通せないかな。