AtCoder nikkei2019-2-qual A, B, D 解法メモ
C が解けたら参加しようと思ったけど解けなかったので NoSub..
A: Sum of Two Integers
$ 1.. \lfloor N/2 \rfloor それぞれと残りの数でペアを作れる。 N が偶数の場合は $ (N/2, N/2) が相違なる数の条件を満たさないのでそれを省く
B: Counting of Trees
まず頂点$ 1 は距離$ 0である必要があり、また距離$ 0である頂点は頂点$ 1のみである必要がある。そうでなければ答えは$ 0となる。
頂点$ 1との距離が$ Dである頂点の数を$ C_Dとする。
距離 $ D の頂点は距離 $ D-1 の頂点と結ぶ必要があり、距離$ Dの一つの頂点の結び方は$ C_{D-1}個ある。距離$ Dの全ての頂点$ C_D個の頂点の木への結び方は $ (C_{D-1})^{C_D} 個となる。
これは他の頂点の結び方と独立しているから、頂点$ 1のみからなる木の状態$ 1通りから始めて、距離を増やして上記の数をかけ合わせていけば良い。
距離$ Dの頂点を木に結ぶ際、距離$ D-1の頂点が無い場合は$ 0としないといけないが、その場合は上記の計算の中で$ 0となるので特に意識する必要はない。しかしその場合に break しないのであれば、 $ 0^0が演算されうるので、便宜的に適当な値が返るようにしておく必要がありそう。
D: Shortest Path on a Line
1. 逆向きコストゼロの辺を貼ってダイクストラ
解説の方法。
「$ L \leq s \lt t \leq Rなる$ s, tで $ s->$ tにコスト$ cの辺がある」は
「$ L->$ Rにコスト$ cの辺があり、任意の$ iについて$ i+1-> $ iにコスト$ 0の辺がある」
と頂点間のコストに変わりは無い。前者は辺の数が$ N^2になり得るのに対し 後者は辺の数が $ N+Mで押さえられる。よって後者であればダイクストラが使え、 $ O((E+V)log V)より $ O((N+M)logN)で解ける。
2. 遅延セグメントツリー
遅延セグ木を使えば範囲$ Nに対する取得・更新が$ O(log N)で行えるため、それが使える。
スタートから各頂点までの最短距離を配列で持ち、先頭だけ$ 0、残りは$ \inftyで埋めておく。
辺を左端でソートし、順番に距離配列に反映させていくことを考える。$ [L, R] にコスト$ cの辺を適用させるには、セグ木でこの範囲の最短距離$ dを取得し、セグ木でこの範囲に対して$ c+dの方が小さければ置き換えるという操作を行えば良い。$ M回セグ木の取得・更新が行われるから$ O(M logN)?
3. イベントソート風なやり方
スタートから順に最短距離を埋めていくことを考える。ある頂点に注目し、それを左端とした辺がある時、以降の頂点ではその辺が閉じるまで「その点の最短距離 + 辺のコスト」が最短距離の候補になる。これを multiset で持つようにし、辺が現れる度に追加、辺が閉じる度に削除するようにする。
こうすると、ある頂点に注目した時、 multiset の最小値がその点の最小距離になることがわかる。
実装上はまず multiset を見てその頂点の最短距離を決定し、その後に multiset の更新を行う。 N 回 multiset の先頭取得、M 回 multiset の追加・削除が行われるから $ O((N+M)logN)?