けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

ゲーム

AtCoder ABC 078 D - ABS (ARC 085 D) (青色, 500 点)

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

CPSCO 2019 session2 D - Two Piles

これ好き!!! しばらく、CPSCO の良さげな問題を解説するターンをやってみたい。 問題へのリンク 問題概要 石の山が 2 個あって、それぞれ初期状態では 個積まれている。ここから先手と後手が交互に 残っている石の山から 1 つ選び、その石の個数を とする…

AtCoder AGC 033 C - Removing Coins (青色, 800 点)

これ大好き!!! 問題へのリンク 問題概要 頂点のツリーが与えられる。 初期状態ではすべての頂点に 1 枚ずつコインが乗っている。先手と後手が交互に コインが 1 枚以上乗っている頂点を 1 つ選び、その頂点のコインを取り除き その頂点以外の全頂点につい…

AtCoder AGC 002 E - Candy Piles (赤色, 1400 点)

やった!自力で解けたー!!! メチャクチャ楽しい問題だった。 問題へのリンク 問題概要 キャンディの山が 個あって、それぞれ 個のキャンディが積まれている。先手と後手が交互に キャンディが 1 個以上あるすべての山について、1 個ずつキャンディを取る …

隣の山に石を渡していく Nim (staircase nim)

ふと TL に出してみた。絶対既出だと思ったから流したけど、どこかにあるかな...??? アイディア自体は SRM 309 DIV1 Hard StoneGameStrategist POJ 1704 Georgia and Bob (蟻本の例題) と同じものだったりする。むしろ問題に対してある種の同型変換を施す…

AOJ 3057 First Kiss (RUPC 2019 day2-G)

面白かった 問題へのリンク 問題概要 Nim の「石が 個しかとれないバージョン」を考える。 ただし勝敗の決まり方が、「先に石を取れなくなった方が負け」ではなく「先にいずれかの山の石の個数を 0 にした方が負け」である。 制約 考えたこと 一瞬逆形かと思…

AtCoder World Tour Finals 2019 A - Magic (1000 点)

世界大会で注意力を問う罠枠だったのかな 問題へのリンク 問題概要 個の箱があってそのうちの一つに財宝が入っている。箱を 1 個 1 個開けて行くことで財宝を見つけたい。ただし、財宝が入っている箱を開けようとすると最大 回、財宝が他の箱に瞬間移動して…

全国統一プログラミング王決定戦 エキシビジョン H - 8^kゲーム (500 点)

きれい 問題へのリンク 問題概要 枚のコインがあります。高橋君と青木君は、以下の操作を高橋君から始めて交互に繰り返します。 0 以上の整数 を選び、コインを 枚取り除く。 先に操作を行えなくなった者の負けです。両者が最適に行動するとき、どちらが勝つ…

AtCoder AGC 010 D - Decrementing (橙色, 1000 点)

一目見て惹かれた。すごく面白かった。割と自然な考察の流れで解けた。 問題へのリンク 問題概要 個の正の整数からなる数列 が与えられる。先手と後手が交互に以下を繰り返す。先に操作を行えなくなった方が負けである。双方最善を尽くしたときにどちらが勝…

AtCoder ABC 048 D - An Ordinary Game (ARC 064 D) (青色, 500 点)

気づき系。。。 こういうのを一瞬で思いつける人になりたい。 問題へのリンク 問題概要 長さ の文字列 が与えられる。先手と後手とで交互に 文字列中の文字を一文字選んで消していく、ただし 両端は消せない その文字を消すことで「同じ文字が隣り合っている…

AtCoder ARC 038 D - 有向グラフと数 (試験管赤色)

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

CADDi 2018 D - Harlequin (緑色, 500 点)

一瞬 Nim に見えそうなのは確かにそんな気もするようなしないような... 問題へのリンク 問題概要 一本のりんごの木があり、 色のりんごが実っています。これらのりんごの 種類の色には 1 から までの番号が振られており、i 番の色のりんごは 個あります。 あ…

AOJ 1399 Sixth Sense (ICPC アジア 2018 K) (500 点)

「辞書順最大」という条件さえなければ典型的な Greedy マッチングではあるね。「辞書順最大」になっても頑張れば基本に忠実にできる。ややこしいけど頑張ればできる感じかな。。。 問題へのリンク 問題概要 人対 人の対戦割当を決めたい。敵が 1 回戦、2 回…

AtCoder AGC 026 F - Manju Game (銀色, 2000 点)

ふと考えてみた。区間 DP っぽく にはなるな...なんて思っていたけどそこから落とせなかった...いやこれ何を食べたらこんな二分探索思いつけるようになるの!?!?!?!??? なにかこういう場面で二分探索すると上手く行くよ、というパターン的なものが…

TopCoder SRM 309 DIV1 Hard - StoneGameStrategist (本番 4 人)

staircase nim の流れで 問題へのリンク 問題概要 個の石の山が左から順に一列に並んでいて、各山には 個の石が積まれている。初期状態では を満たしている。今先手と後手が交互に 石が 1 個以上ある好きな山を 1 つ選んで 何個かの石を取り去る ただし とい…