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

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

とりうる状態が連結

CPSCO2019 Session4 E - ox Concatenation (600 点設定)

これすごく好き!!!普通に難しい。 問題へのリンク 問題概要 'o' と 'x' のみからなる長さ の文字列 を作りたい。部品として使えるのは以下のものたち ( となっている)。 "ox" が 個 "xo" が 個 "o" が 個 "x" が 個 これらを適切な順序で concat すること…

AtCoder AGC 015 D - A or...or B Problem (橙色, 900 点)

最初、「これは本当に AGC か!??」となってた 問題へのリンク 問題概要 以上 以下の整数の中からいくつか選んで、OR 和をとってできる値が何通りあるか求めよ。 制約 考えたこと 一見するとこどふぉっぽい見た目の問題だけど、実はすごく AGC っぽい感じ…

CODE FESTIVAL 2016 Final B - Exactly N points (緑色, 300 点)

1, 2, ..., i のうちのいくつか選んで和を取った値は、連続した自然数を作れる 問題へのリンク 問題概要 からいくつか選んでできる総和が となるようにしたい。 選んだ数の最大値が最小となるような場合の数を求めよ。 制約 考えたこと 一般に、 によって作…

AtCoder ARC 104 C - Fair Elevator (黄色, 600 点)

コーナーケースがえぐい!! 僕は最初、(1, -1), (-1, 3) で Yes を返してしまっていた。 問題へのリンク 問題概要 個の区間 があって、 両端の座標は のいずれか 両端の座標をかき集めたとき、重複がない 区間 と区間 がもし重なっているならば、区間 の長…

ACL Contest 1 A - Reachable Towns (水色, 300 点)

えーーー、300 点!? 問題へのリンク 問題概要 二次元平面上に 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは の順列となっている。 各 に対して、点 から 自分よりも x 座標と y 座標がともに大きな点 自分よりも x 座標と y 座標が…

AOJ 3178 Katsusando (HUPC 2020 day3-G)

いわゆる区間分割する系の DP。こういう系は高速化を要求するタイプの問題が多いけど、今回は素直な二乗 DP で OK! 問題へのリンク 問題概要 直線上にカツが 個ある。 個目のカツは位置 にあり、その重さは である。これらのカツを、次のようにしてすべて回…

AtCoder ABC 169 E - Count Median (水色, 500 点)

未証明でも確信持てる系。でも、こういう風に「作れるものは連続している」というのはたまに見るパターン。そういう問題には「とりうる状態が連結」というタグをつけているので是非に!! drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 を次の…

AtCoder ABC 163 D - Sum of Large Numbers (緑色, 400 点)

「作れる数が連続する整数になる」というの、実は結構よくある!! 問題へのリンク 問題概要 個の整数 がある。 これらから 個以上の整数を選んで合計して得られる整数としてありうるものの個数を 1000000007 で割ったあまりを求めよ。 制約 考えたこと まず…

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…