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

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

とりうる状態が連結

AtCoder AGC 015 A - A+...+B Problem (200 点)

確かに 200 点かもしれないけど、AGC-A は時々こういう注意力系が出るね。 問題へのリンク 問題概要 個の整数であって、最小が 、最大が であるようなものについて、その総和として考えられる値が何通りあるかを求めよ。 制約 考えたこと この手の問題で重要…

AtCoder AGC 017 B - Moderate Differences (400 点)

むむむ 問題へのリンク 問題概要 長さ の整数列 であって、 が 以上 以下の整数 となるものが存在するかどうかを判定せよ。 制約 考えたこと とりあえず , としてよい。 さて、 からスタートして、 ターン目にどんなのを作れるかを考察してみる。 1 ターン目…

AtCoder AGC 033 C - Removing Coins (800 点)

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

AtCoder AGC 033 B - LRUD Game (600 点)

嘘貪欲は一瞬脳裏によぎり、それを振り払って問題を解いてた。発想はこれの「後ろから解く」のに似ている。 drken1215.hatenablog.com 問題へのリンク 問題概要 × のグリッドのあるマスにロボットが置かれている。先手と後手はそれぞれ長さ の自分の文字列 …

エクサウィザーズ 2019 C - Snuke the Wizard (500 点)

頭の整理が大変!!! 問題へのリンク 問題概要 左から右に向かって 1 から N の番号がついた N 個のマスがあります。 各マスには文字が書かれており、マス i には文字 si が書かれています。また、各マスにははじめ 1 体のゴーレムがいます。 すぬけ君は Q …

AISing Programming Contest 2019 D - Nearest Card Game (500 点)

ができた。本番中に解き切りたかった 問題へのリンク 問題概要 個の整数 がある。整数 を 1 つ固定したとき、先手と後手は以下のようにしてゲームを進める: 先手は現在残っている整数のうち、最大のものを取って足す 後手は現在残っている整数のうち、 に最…

AtCoder AGC 029 D - Grid game (800 点)

これは。。。C より先に確実にこれをとったのはよかった 問題へのリンク 問題概要 (意訳) H × W の二次元グリッドがあって、各マスは通路か壁である。壁は N 個ある。最初は (1, 1) に駒がある。 毎ターン (x, y) にある駒は (x + 1, y) に進める、ここで (x…