水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

CODE THANKS FESTIVAL 2018:F - Coins on the tree

問題

atcoder.jp

解法

問題文の条件より,i 枚目のコインをある頂点 v に置くと決めた場合,(i + 1) 枚目以降のコインを頂点 v とその子孫の頂点に置くことが出来なくなる.よって,1 枚目のコインから順に置く場所を決めていく.

(i - 1) 枚目のコインまでで S 回操作したとき,i 枚目のコインをある頂点 v に置くことを考える.このときにかかる操作の回数は (頂点 v の深さ) + 1 になる(根の深さを 0 とする)ので,i 枚目のコインまでの操作の回数は (S + depth_v + 1) になる.

このとき,(i + 1) 枚目のコイン以降で操作しなければならない回数は (K - S - depth_v - 1) になる.この回数が多すぎると全てのコインを置いても操作の回数が余ってしまい,少なすぎると全てのコインを置くことができなくなってしまう.この判定は,少なくとも (i + 1) 枚目のコイン以降で操作しなければいけない回数を minSum,多くても (i + 1) 枚目のコイン以降で操作しなければいけない回数を maxSum とすると,

minSum <= (K - S - depth_v - 1) <= maxSum(*)

を満たすかどうかで可能.minSum は深さが小さい頂点 (M - i) 個,maxSum は深さが大きい頂点 (M - i) 個それぞれにコインを置くのにかかる操作の回数の合計になる.

以上のことを踏まえて,各 i についてその時にコインを置くことが可能である頂点の中から(*)の条件式を満たす最小の v を探せばよい.もし,このような v が1つも無い場合に答えは -1 になる.O(M * N^2).

解答

atcoder.jp

一発 AC 出来たのでよかった.

f:id:babcs2035:20190108204517p:plain