titiaのノート: yukicoder contest 421 (NUPC2023)

2024年3月16日土曜日

　AB二完でした。

No.2673 A present from B

　後ろから見ると良いというヒントを見てAC。

　次のように、答えを徐々に更新していく。

・最終手まで見て、そこから配列に何かを付け足すと考えると、最終手の後できている配列のindexにより答えを更新できる。

・その一手前を見る。そのとき、A[x]とA[y]がd個離れているとすると、そこにd個挿入してA[y]をA[x]の位置へ持っていくことができる。つまり、ANS[A[y]]をd+ANS[A[x]]で更新できる。

　以下これを繰り返すと、計算回数N*N*Mになる。解説を見ると、もっと速く解けるみたい……と思って考え直したところ、ここに書いた方法でも累積minを取れば計算量N*Mになりそうですね。

　おおまかな方針はあっていたけどWAを取ることができなかった。テストケースを見ながらデバッグしてAC。

　難しい問題ではないけれどコーナーケースを探すのが難しい。コンテスト中にACした人はえらい。

　全方位木DPというタグを見てAC。

　自分の全方位木DPのライブラリをほぼそのまま使えたにもかかわらず実装で混乱した。自分の全方位木DPライブラリが良くないのではないかという気持ちに。

　辺属性のDPと考えているので、UP[x]とDOWN[x]を同じ辺に関する値にしたくて、

・UP[x]:xをROOTとする部分木（xを含み、xおよびxより葉に近い頂点たち）に関する値

・DOWN[x]はParent[x]をROOTとする部分木（xを含まない。xより根を含まない頂点たち）に関する値。

　としていたのだけど、分かりにくくない？

　自力AC。これは簡単だった。

　横に1001個頂点をつなげておき、そのうち一個は、一個の頂点がx個ついているようにする。他の1000頂点は、二個連なった頂点がx+2個ついているようにする。(xは適当な数。4とか)

　すると、最適なのは、最初の一個の頂点を選ぶことだが、問題文で与えられた解法では他の次数の高い1000個の頂点の中から選んでしまう。