Yes/No判定問題
通称 0-1 BFS と呼ばれるアルゴリズムが使える問題ですね。 問題へのリンク 問題概要 のマス目で表現された地図が与えられます。 . は通路、# は壁を表します。s マスから出発して、上下左右への移動を繰り返しながら g マスへと到達したいとします。. マス…
ABS (AtCoder Beginner Selection) の 9 問目に選んだ問題！ 問題へのリンク 問題概要 英子文字からなる長さ の文字列 が与えられます。 をいくつかの連続する文字列に分割して、かつそれらの文字列がすべて "dream", "dreamer", "erase", "eraser" のいずれ…
「決めてから、整合性を確認する」というタイプの問題の典型例ですね！ 問題へのリンク 問題概要 の非負整数を成分とする行列 が与えられる。 すべての について を満たすような非負整数列 と の組が存在するか判定し、存在するなら一つ出力せよ。 制約 考え…
昔はこういうの苦手だったけど、今ならできる！ 問題へのリンク 問題概要 階建ての建物があって、後述するエレベータの建設をなくしては、下への移動は自由にできるが、上への移動は自由にできない。 個のエレベータ建設計画がある。 番目の計画では、 日目…
なんとなくできそうだけどできないみたいな問題だった。そうか、牛ゲーに帰着すれば明快だ... 問題へのリンク 問題概要 頂点数 、辺数 の連結グラフが与えられる。いくつかの辺は無向辺であり、いくつかの辺は有向辺である。 各頂点 に 0 以上の整数値 を割…
こういう個数合わせ系の問題は実は得意かもしれない 問題へのリンク 問題概要 長さ の数列 が与えられる。これに対して の順列 であって、 のどの隣接する二項も同じ数値でないようなものを考える。 そのような順列 のうち、 を満たさない の個数の最小値を…
頑張った 問題へのリンク 問題概要 正の整数のみからなる長さ の数列 が与えられる。各 に対して、以下の問に答えよ。 数列 を左から順に「連続する 個の最小値」をとっていってできる長さ の数列が、 の順列になっているかどうかを判定せよ。 制約 の総和 …
コンテスト後に AC して、解けた気持ちになっていたけど、その解法は嘘だった 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を最大 200000 回まで繰り返すことでソートされた状態にせよ。 のいずれかを選んで と を swap する 不可能である場合…
教育的な約数列挙問題！！ 問題へのリンク 問題概要 2 つの正の整数 が与えられます。 を満たす正の整数 が存在するかどうかを判定せよ。 制約 考えたこと として、 の約数のみを考えれば OK。そして を決めると は と決まる。 となることがあるかどうかを判…
これ難しいと思った！ あと、どうやら (1, 1, 1, 6) を 3 回にする嘘解法が AC になったらしい 問題へのリンク 問題概要 以下の動きのできる駒がある。駒をマス からマス へ移動させるのに必要な手数の最小値を求めよ。 制約 考えたこと まず、スタートとゴ…
TLE が厳しくて話題になってた 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ [tex G] が与えられる。また、正の整数 が与えられる。 以下のいずれかの条件を満たすものが存在するかどうかを判定し、存在するならばそれを出力せよ。 type 1： の…
条件反射でいもす法！！！ 問題へのリンク 問題概要 人がいる。 人目の人は、時刻 から時刻 の間で、毎分 リットルずつお湯を使う。 どの時刻においても、使用されているお湯の合計量が、毎分 リットル以内におさまるかどうかを判定せよ。 制約 考えたこと …
簡単なバグを埋め込んでしまった... 問題へのリンク 問題概要 長さ の "0" と "1" のみからなる 2 つの文字列 が与えられる。 に対して以下の操作を繰り返し行うことで に一致させることができるかどうかを判定し、可能ならば最小回数を求めよ。 中の "01" …
想定解法とちょっと違うやり方したっぽい 問題へのリンク editorial 問題概要 個のマスが横一列に並んでいる ()。 匹のペンギンがマス にいる。 あなたは，次の操作を好きな回数行うことができる。 ペンギンを 1 匹選び、左または右へ向かって滑らせる ペン…
面白かった。でも茶色ってことは流石になさそう......(コンテスト中は、全部の XOR 和が 0 かどうかを判定する、という嘘解法が AC になっていたらしい) 問題へのリンク 問題概要 個の非負整数 が与えられる。これらを円環状に上手に並べることで、 「どの整…
場合分けやコーナーケース回避がエグい問題！ 問題へのリンク 問題概要 .#..#.. のような長さ のマス目が与えられる。"#" は岩を表す。初期状態では、すぬけ君は マス目に、ふぬけ君は マス目にいる ()。 今、「2 人のうちのいずれかを選んで 1 マス右か 2 …
面白かった！ 問題へのリンク 問題概要 頂点数が の木であって、各頂点 から最も遠い頂点への距離がそれぞれ であるような木が存在するかどうかを判定せよ。 制約 考えたこと 面白そう！！！！！！似た見た目の問題としては、次の問題もあった。 drken1215.h…
区間加算操作は、「差分」をとる (いもす法) と、2 点加算になる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。これに対して以下の操作を好きな順序で好きな回数だけ行うことで、数列の値がすべて 0 になるようにすることが可能かどうか、判定せよ…
幾何っぽい問題。確かに数学ゲーではあるのだけど、平行判定は「計算幾何」の知見として習得してしまっても良さそう。 問題へのリンク 問題概要 二次元平面上に 個の点 () が与えられる。 これらのうちの 3 点であって、同一直線上にあるものが存在するかど…
これすごく好き！！！普通に難しい。 問題へのリンク 問題概要 'o' と 'x' のみからなる長さ の文字列 を作りたい。部品として使えるのは以下のものたち ( となっている)。 "ox" が 個 "xo" が 個 "o" が 個 "x" が 個 これらを適切な順序で concat すること…
最初は文字列 を文字列 にできるかを問うつもりだった。てんぷら君のおかげで、 を真っ白にすることで、シンプルな問題になった！ 問題へのリンク 問題概要 マスがあって最初はすべて白く塗られている。ここに "RGB" のスタンプを押していく。スタンプを押す…
めちゃくちゃ面白かった！ 問題へのリンク editorial 問題概要 個のカッコ列 が与えられる。これらを並び替えて連結して 1 個の文字列を作る。 この文字列が「整合のとれたカッコ列」となるようにすることが可能かどうかを判定せよ。 制約 考えたこと 大前提…
これ好き！！！ 問題へのリンク editorial 問題概要 の順列が与えられる。これらの順列のうち、 個を赤く塗り、 個を青く塗る方法であって、次の条件を満たすようにするものは存在するか、判定せよ。 赤い要素同士を swap することを好きな順序で好きな回数…
これ結構好き！ 問題へのリンク 問題概要 それぞれ 枚のコインの入った 枚の袋と、 枚の皿 (初期状態ではすべて空) がある。これらを使ってゲームをする。先手と後手が交互に以下のように手を打つ。 (コインが入った袋が 1 つ以上存在するとき)：コインが入…
kirika さんの「整数論テクニック集」より。 問題へのリンク 問題概要 二次元平面平面上において から の合計 8 方向に移動できる。今、 個のクエリが与えられる。各クエリは座標 が与えられる。原点から出発して、上述の移動を好きな順序で好きな回数だけ繰…
コーナーケースがえぐい！！ 僕は最初、(1, -1), (-1, 3) で Yes を返してしまっていた。 問題へのリンク 問題概要 個の区間 があって、 両端の座標は のいずれか 両端の座標をかき集めたとき、重複がない 区間 と区間 がもし重なっているならば、区間 の長…
単純に bit 全探索で良さそう。 問題へのリンク editorial 問題概要 長さ の 0 と 1 からなる文字列が 個与えられる ()。以下の条件を満たす文字列 が存在するかどうかを判定し、存在するならば具体例を一つ与えよ。 の長さは は '0' と '1' と '*' のみで構…
面白かった！ 問題へのリンク editorial 問題概要 次の問題が ケース分与えられる。 二次元平面上に 個の格子点が与えられる。これらに対し、以下の条件を満たす直線 が存在するかどうかを判定せよ。 どの点に対しても、 との距離が等しい 制約 考えたこと …
最初誤読して、「何度でもスタート地点にワープして戻っても良い」というバージョンの問題を解いていた。 問題へのリンク editorial 問題概要 個の整数 と 2 以上の整数 が与えられる。 頂点からなる以下のような有向グラフであって、頂点 1 を始点として、…
これ楽しい！ 問題へのリンク 問題概要 長さ の英小文字のみからなる文字列 が与えられます。 の文字を入れ替えることによって、次の条件を満たす文字列 を作ることができるかどうかを判定してください (可能ならば具体例を 1 つ挙げてください)。 のどの長…
