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

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

対称戦略

AtCoder AGC 014 D - Black and White Tree (900 点)

最高に好きな問題 問題へのリンク 問題概要 頂点数 のツリー上でゲームを行う。高橋君は残った頂点から 1 つ選んで白く塗る。青木君は残った頂点から 1 つ選んで黒く塗る。 この操作をすべての頂点に色が塗られるまで繰り返したとき、黒く塗られたすべての頂…

GCJ 2019 Qual B - You Can Go Your Own Way

ちょっと考えればできる 問題へのリンク 問題概要 × のグリッドグラフの左上から右下への最短路が 1 つ与えられる。この最短路と辺を共有しない最短路を一つ求めよ (頂点で重なるのは OK) 制約 考えたこと 対角線に沿って反転すれば OK #include <iostream> #include <sstream> </sstream></iostream>…

AtCoder AGC 002 E - Candy Piles (1400 点)

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

AtCoder AGC 010 D - Decrementing (1000 点)

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

CADDi 2018 D - Harlequin (500 点)

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