ゲーム
場からカードを手札に入れない方が良い場合があるの、すごい！ あと、局面状態を数値情報にエンコードするかを迷ったけど、エンコードしなくても通った。 問題へのリンク 問題概要 はじめ、高橋君は整数 の書かれた 枚のカードを持っていて、青木君は整数 の…
面白かった！！ 実験で思いつけるかもしれないし、気づいたら証明したい系。 問題へのリンク 問題概要 先手と後手が石取りゲームをする。2 個の山があって、最初それぞれ石が 個積まれている。交互に次の操作をする。 2 個以上の石が積まれている山を 1 つ選…
一見、 の DP に見えたが、その必要はなかった。 問題へのリンク 問題概要 グーとパーしか出せないジャンケンを 回する。相手が各回に何を出すかが予めわかっている。ただし、どの時点でも (それまでに出したグーの回数) (それまでに出したパーの回数) を満…
ChatGPT が問題文コピペのみで解けたと話題になった！ 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。 先手と後手が交互にゲームする。交互にまだ残っているカードのうち、表の値が等しいか、裏の値が等しいような 2 枚のカー…
これは整理するのが大変！！！ 問題へのリンク 問題概要 高橋君は 個のアメを持っていて、青木君は 個のアメを持っている。 交互に自分のアメを食べていき、先に食べられなくなった方が負けである。 ならば高橋君が先手、 ならば青木君が後手。 どちらか勝つ…
データを上手に持って、差分更新する系の問題 問題へのリンク 問題概要 のグリッドがあって、各マスは文字 '#' か '.' のいずれかが書かれている。先手は '#' の個数が得点となり、後手は '.' の個数が得点となる。双方得点を最大化したい。 先手は行を 1 つ…
モノグサ社内で同僚と一緒に解いた！ 問題へのリンク 問題概要 要素からなる数列 が与えられる。各 に対して次の問に答えよ。 先手と後手が交互にプレイする。整数 を管理する。最初 である。 先手は初手は を選び、 と に更新し、数列からその整数は削除す…
考察に時間をかけすぎた 問題へのリンク 問題概要 文字 'A' と 'B' のみからなる長さ の文字列 が与えられる (先頭の文字を 0 文字目とする)。各 について、次の問に答えよ。 Alice と Bob が交互に、以下の操作を合計 回行う。Alice が先手である。なお、最…
ゲーム探索 + bit DP。やや実装重たい。 問題へのリンク 問題概要 先手と後手が交互に のグリッドの各マス目に o や x を書いていく。先手は o を書き、後手は x を書く。 書き終わったとき、次のように得点を計算する および に対して、 マス とマス が同じ…
いわゆる「相手との得点差を最大化したい」タイプのゲーム DP ですね！ 問題へのリンク 問題概要 太郎君と次郎君が数列 を使ってゲームをします。太郎君を先手として、交互に次の操作を行います。 数列の先頭要素または末尾要素を除去する 除去した値の分だ…
相手との得点差を最大化したいタイプのゲーム DP！ 問題へのリンク 問題概要 2 つの山があります。 1 つ目の山には 個の物が積まれていて、上から順に価値は となっている 2 つ目の山には 個の物が積まれていて、上から順に価値は となっている 先手と後手は…
いわゆる「得点差を最大化したい」というゲーム DP！！ 問題へのリンク 問題概要 個の石が積まれた山を使って石取りゲームをします。先手と後手は交互に次の操作を行います。 個のいずれかの個数の石を取り除きます ただし、 が残っている石の個数よりも小さ…
慣れないと頭がごっちゃになるけど、一度慣れればもう機械的に解ける系！！ 問題へのリンク 問題概要 のグリッドがある。各マスには '+' か '-' のいずれかの文字が書かれている。 最初、左上マスにコマが置かれている。高橋君と青木君は交互に、次の操作を…
少し前処理が面倒な DP。PCK の予選突破ライン上の問題のようですね！ 問題へのリンク 問題概要 個の整数 が黒板に書かれている (各整数は 100 桁までありうる)。 奇数の精と、偶数の精がいる。 奇数の精は、黒板に書かれている数字がすべて奇数となるように…
めっちゃ面白い問題だった！ 問題へのリンク 問題概要 頂点 0 を根とする頂点数 の根付き木が与えられます。頂点 0 以外の頂点 には数値 が書かれています。今、頂点 0 にコマが置いてあります。 高橋くんと青木くんが次の動作を交互に繰り返します。 青木く…
コンテスト中にアダマール変換を思い出せたのはよかった！ 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…
Grundy 数は Grundy 数でも、「山を分割していく」というタイプの Grundy 数ですね。 問題へのリンク 問題概要 個の区間が与えられる。 個目の区間は となっている。 Alice と Bob は次のようなゲームを行う。 まだ残っている区間のうち、「今までに選ばれた…
面白かった！ 問題へのリンク 問題概要 個の石の山がある ( は偶数)。 番目の山には 個の石がある。先手と後手が交互に以下の操作を行う。操作できなくなった方が負けである 石の山のうち、まだ石が 1 個以上残っている山をちょうど 子選ぶ そのそれぞれの山…
Grundy 数がフラクタルっぽい構造を示していた！ 問題へのリンク 問題概要 個の石の山がある。各山には 個の石がある。先手と後手が交互に以下の操作を繰り返す。 山を一つ選ぶ。その山には石が 個あるとする。 その山の石の個数が 個または 個となるように…
これを本番間に合わせられたなかったのは辛かった... あと、数え上げパートがあんなにスマートにはできなかった。無限に から落とせなかった... 問題へのリンク 問題概要 黒石さんと白石さんは、一列に並んだ 個のマスからなる盤面を使って遊んでいます。 マ…
シンプルだけど、すごい好き 問題へのリンク editorial 問題概要 マス と区切られた マス上でゲームする。 Alice は最初マス に、Bob は最初マス にいる。交互に左右どちらかに動かす。ただし「マスの外」や「相手のいるマス」には動かせない。 先に動かせな…
こないだの ARC でめっちゃ似た問題が出たので！これは、SolveMe を含む、りんごさんによる伝説のセット。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 のグラフが与えられる (入力は の隣接行列で与えられ、初期状態では非連結である)。この…
これの原案だった！！ 「対称戦略」が印象的なゲームの問題を作ろうとして作った 問題へのリンク editorial 問題概要 1 × 1 × 1 の立方体を の直方体形状に積み上げたものがある。これを使って 2 人でゲームする。 交互に、直方体のある面のあるマスを選んで…
とてもシンプルな設定で面白かった！でもバグらせてそうで、提出するのは怖かった。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。初期状態では頂点 1 と頂点 は非連結である。 先手と後手が、交互に 1 本ずつ辺を追加していく。た…
これ結構好き！ 問題へのリンク 問題概要 それぞれ 枚のコインの入った 枚の袋と、 枚の皿 (初期状態ではすべて空) がある。これらを使ってゲームをする。先手と後手が交互に以下のように手を打つ。 (コインが入った袋が 1 つ以上存在するとき)：コインが入…
これはマジで天才やと思うやが... いや本当にどこから Grundy 数を導けるのか、わからぬ... 問題へのリンク 問題概要 頂点数 のグラフが 3 つ与えられる。それらのグラフのカルテシアン積を考える。この頂点数 のカルテシアングラフの独立集合のうち、以下の…
シンプルで楽しい感じ 問題へのリンク 問題概要 要素からなる数列 がある (互いに相異なる)。交互に以下の操作を行う 数列から 2 つの整数を選んで、その差を数列の末尾に追加する ただし、「その差の値」がすでに数列中に含まれる場合は、この操作を行うこ…
すごく面白かった！ 問題へのリンク 問題概要 個の袋があって、それぞれには 激辛バナナが 本 美味しいバナナが 本 がある。先手と後手が以下のことを交互に行う。 激辛バナナを 0 本または 1 本取り出す 美味しいバナナを好きな本数だけ取り出す ただし、激…
Deque に似てる。けど、Deque と違って、先手と後手がとりうる選択肢は常に一緒 (最初、先手は左から、後手は右からと誤読した)。 問題へのリンク 問題概要 長さ の数列に対し、先手は左から順に、後手は右から順にとっていく。どのターンもとった値の合計値…
200 点となってるけど、他の 300 点と同じくらいに感じた！ 頭の整理が大変だった...けど、面白い 問題へのリンク 問題概要 個の根付き木が与えられる。それぞれの木の頂点数は となっている。これらの木を使って、ゲームを行う。 最初、駒がスタート地点 (…
