drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder600点 ABC-G 黄色diff 二分探索 木 グラフ 木DP DP ゲーム ゲームDP マージ可能ヒープ マージテク 変化・遷移先が限られる 木上のゲーム 駒(コマ)や石やコインを扱う問題 グラフ上のゲーム 得点差最大化ゲーム NoviSteps3D ある値より「大きい」「小さい」という2値の問題に帰着する めっちゃ面白い問題だった！ 問題へのリンク 問題概要 頂点 0 を根とする頂点数 の根付き木が与えられます。頂点 0 以外の頂点 には数値 が書かれています。今、頂点 0 にコマが置いてあります。 高橋くんと青木くんが次の動作を交互に繰り返します。 青木くんは、好きな頂点を選んで、その頂点の値を 0 にする 高橋くんは、コマを子頂点のいずれかに移動させる。移動できないときはその場でゲームを終了する 高橋くんは任意のタイミングでゲームを終了できます。そしてゲーム終了した時のコマの置かれた頂点の数値が、ゲームのスコアとなります。 高橋くんはスコアの最大化を目指し、青木くんはスコアの最小化を目指しま… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2022%2F04%2F04%2F023800" title="AtCoder ABC 246 G - Game on Tree 3 (3D, 黄色, 600 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20220404/20220404022834.png Hatena Blog https://hatena.blog 2022-04-04 02:38:00 rich https://drken1215.hatenablog.com/entry/2022/04/04/023800 1.0 100%