データを上手に持って、差分更新する系の問題 問題へのリンク 問題概要 のグリッドがあって、各マスは文字 '#' か '.' のいずれかが書かれている。先手は '#' の個数が得点となり、後手は '.' の個数が得点となる。双方得点を最大化したい。 先手は行を 1 つ…

ゲーム探索 + bit DP。やや実装重たい。 問題へのリンク 問題概要 先手と後手が交互に のグリッドの各マス目に o や x を書いていく。先手は o を書き、後手は x を書く。 書き終わったとき、次のように得点を計算する および に対して、 マス とマス が同じ…

いわゆる「相手との得点差を最大化したい」タイプのゲーム DP ですね！ 問題へのリンク 問題概要 太郎君と次郎君が数列 を使ってゲームをします。太郎君を先手として、交互に次の操作を行います。 数列の先頭要素または末尾要素を除去する 除去した値の分だ…

相手との得点差を最大化したいタイプのゲーム DP！ 問題へのリンク 問題概要 2 つの山があります。 1 つ目の山には 個の物が積まれていて、上から順に価値は となっている 2 つ目の山には 個の物が積まれていて、上から順に価値は となっている 先手と後手は…

いわゆる「得点差を最大化したい」というゲーム DP！！ 問題へのリンク 問題概要 個の石が積まれた山を使って石取りゲームをします。先手と後手は交互に次の操作を行います。 個のいずれかの個数の石を取り除きます ただし、 が残っている石の個数よりも小さ…

慣れないと頭がごっちゃになるけど、一度慣れればもう機械的に解ける系！！ 問題へのリンク 問題概要 のグリッドがある。各マスには '+' か '-' のいずれかの文字が書かれている。 最初、左上マスにコマが置かれている。高橋君と青木君は交互に、次の操作を…

めっちゃ面白い問題だった！ 問題へのリンク 問題概要 頂点 0 を根とする頂点数 の根付き木が与えられます。頂点 0 以外の頂点 には数値 が書かれています。今、頂点 0 にコマが置いてあります。 高橋くんと青木くんが次の動作を交互に繰り返します。 青木く…

何も考えずにゲーム DP 毎ターン「実質的に取れる選択肢が二通りしかない」というパターン という包畜を含む教育的問題。 問題へのリンク 問題概要 先手と後手は初期状態で と と書かれたカードを持っている。 枚の山札があってそれぞれ の数値が書かれてい…

後退解析を用いる問題。queue に不慣れなので、急に queue を使えるように。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えられる。各頂点 には値 X_v が割り振られている。先手と後手とで以下の対戦を行う スタート時には駒を頂点 1 に置く 各プレイ…