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

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

全探索

AtCoder ABC 286 C - Rotate and Palindrome (茶色, 300 点)

慣れれば解ける問題だけど、最初は「固定する」という考え方が難しいかもしれない。 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返すことで回文にしたい。 先頭の文字を末尾に移動する (コスト ) 文字を 1 つ…

JOI 二次予選 2023 A - 年齢の差 (難易度 3)

シンプルながらも、学べるポイントがたくさんある問題ですね 問題へのリンク 公式解説へのリンク 問題概要 JOI 市には から までの番号が付けられた 人の住民がいて、住民 () の年齢は 歳です。 JOI 市の住民の年齢 ​ が与えられます。 に対して、住民 と他…

AtCoder ABC 087 C - Candies (ARC 090 C) (灰色, 300 点)

単純な全探索で解ける! 累積和で高速化したり DP したりしても OK 問題へのリンク 問題概要 のマス目があり、上から 行目、左から 列目のマスをマス と表すことにする。マス には ​ 個のアメが置かれている。 あなたははじめ、左上のマス にいる。 右方向ま…

AtCoder ABC 280 C - Extra Character (灰色, 300 点)

この問題、深く考えずに for 文回した人も多いと思う。実際それでも問題なく解ける! 問題へのリンク 問題概要 英小文字のみからなる 2 つの文字列 が与えられる。 は に英小文字を 1 つ挿入して作られたことがわかっている。 挿入された文字は の先頭から何…

AtCoder ABC 249 C - Just K (茶色, 300 点)

ビット全探索もついに茶色 diff ですね! 問題へのリンク 予備知識 ビット全探索の知識があると解きやすいです! drken1215.hatenablog.com 問題概要 英小文字のみからなる 個の文字列 が与えられます。 これらの文字列の中から、いくつかの文字列を選びます…

AtCoder ABC 010 C - 浮気調査 (茶色)

読解がちょっと大変......今の時代の問題文の方がわかりやすいね。 問題へのリンク 問題概要 高橋君は最高速度 で移動することができる。 高橋君は時刻 に地点 を出発し、時刻 に地点 に到達しました。 その過程で 個の地点 , , のいずれかに寄り道した可能…

AtCoder ABC 075 D - Axis-Parallel Rectangle (水色, 400 点)

古き良き全探索問題!! 問題へのリンク 問題概要 二次元平面上に 個の点があります。 番目の点の座標を とします。 この二次元平面上で各辺が X 軸・Y 軸に平行であるような長方形であって、 個の点のうち 個以上の点を内部および周に含むようなものを考え…

競プロ典型 90 問 002 - Encyclopedia of Parentheses(★3)

整合したカッコ列を bit 全探索する問題!!! 問題へのリンク editorial へのリンク 類題とか drken1215.hatenablog.com drken1215.hatenablog.com 問題概要 長さ の「整合したカッコ列」を辞書順にすべて列挙せよ。 整合したカッコ列の意味については、問…

AtCoder ABC 196 C - Doubled (灰色, 300 点)

いわゆる、 まで調べれば十分というタイプの問題だね。最近そのタイプの問題が流行っている気がする! 問題へのリンク 問題概要 十進法表記で偶数桁で、かつ、その前半と後半とが文字列として等しいようなものを「良い整数」と呼ぶことにします。 以上 以下…

AtCoder ABC 193 D - Poker (緑色, 400 点)

発想や考え方はそんなに難しくないんだけど、すごく頭がこんがらがってしまう問題だね... 問題へのリンク 問題概要 が表に書かれたカードが 枚ずつ、計 枚のカードがあります。 これらのカードをランダムにシャッフルして、高橋くんと青木くんにそれぞれ、4 …

AtCoder ABC 193 C - Unexpressed (灰色, 300 点)

むずかしかった!!! でも、約数列挙でありがちな「 まで試せば良い」という考え方がちゃんと理解できているかを問う良問だった!! 問題へのリンク 問題概要 整数 が与えられる。 1 以上 以下の整数のうち、 2 以上の整数 を用いて と表せないものはいくつ…

TopCoder SRM 452 DIV1 Medium - IOIString (本番 19 人)

すごく面白かった! 問題へのリンク editorial スコア: 191.85 / 500.00 問題概要 "I" と "O" のみからなる文字列 が IOI 文字列であるとは、ある正の整数 が存在して = "I" = "O" = "I" が成立することと定義する (1-indexed)。 いま、"I", "O", "?" のみか…

JOI 二次予選 2021 B - パンケーキ (AOJ ????, 難易度 7)

難しかった!!! 予選の問 2 からこういうの出るのびっくり!!! 問題へのリンク 問題概要 "A", "B", "C" からなる文字列 に対して、以下の操作を繰り返すことでソートされた状態 ("A" の前には "B" や "C" がなく、"B" の前には "C" がない状態) にするこ…

JOI 予選 2009 C - 連鎖 (AOJ 0534, 難易度 6)

いろんな実装方法がありそう。でも が間に合うので、すべての書き換え方法について でできるなら十分。 問題へのリンク 問題概要 1 と 2 と 3 のみからなる長さ の数列が与えられる。同じ数値が 4 個以上連続することはない。 この数列のうちの 1 箇所の値を…

AtCoder ABC 186 C - Unlucky 7 (灰色, 300 点)

整数 の各桁の値を取り出す方法さえわかれば!! 問題へのリンク 問題概要 以上 以下の整数のうち、10 進法で表しても 8 進法で表しても 7 を含まないようなものの個数を求めよ。 制約 考えたこと まず、整数 が与えられたときに、それを 10 進法で表したと…

JOI 春合宿 2013 day1-4 JOI Poster (難易度 6)

幾何だ!! ジャッジページへのリンク editorial 問題概要 の長方形の紙上に 個の点がある。これらの点は互いに相異なる。 これらの点から 4 つの点 A, B, C, D を選ぶ (選ぶ順番も考慮する)。そして、点 A を中心として点 B を通る円を O1 とし、点 C を中…

AtCoder ABC 182 C - To 3 (灰色, 300 点)

これ灰色ってマジか!! 問題へのリンク 問題概要 どの桁の値も 0 でないような正の整数 が与えられる。 に含まれるいくつかの数値を除去することで、 が 3 の倍数となるようにしたい。 除去すべき数値の個数の最小値を求めよ (最初から 3 の倍数の場合は 0 …

JOI 本選 2014 A - JOI紋章 (AOJ 0598, 難易度 6)

ちょっと実装大変だった。差分のみ更新していく系の問題。 問題へのリンク editorial 問題概要 のグリッドがあって、各マスには "J"、"O"、"I" が書かれている。 またこれとは別に、2 × 2 の "J", "O", "I" のパターンが与えられる ( 通りありうる)。 今、与…

Codeforces Round #687 (Div. 1) B. XOR-gun (R2000)

こどふぉ特有の、ややギャグ要素ありの楽しい問題。結構好き。 問題へのリンク 問題概要 長さ の正の整数からなる広義単調増加な数列 が与えられる。以下の操作を何度か行うことで、広義単調増加ではない状態にしたい。 数列の隣接する 2 つの要素を選んで、…

AtCoder ARC 108 A - Sum and Product (灰色, 300 点)

教育的な約数列挙問題!! 問題へのリンク 問題概要 2 つの正の整数 が与えられます。 を満たす正の整数 が存在するかどうかを判定せよ。 制約 考えたこと として、 の約数のみを考えれば OK。そして を決めると は と決まる。 となることがあるかどうかを判…

AtCoder ABC 183 C - Travel (灰色, 300 点)

C++ なら next_permutation() を使うことで 通りの全探索ができる! 問題へのリンク 問題概要 個の都市 がある。都市 と都市 とは距離が だけ離れている。 都市 から出発して各都市をちょうど一度ずつ訪問して都市 に戻ってくる方法のうち、その移動距離の総…

AtCoder ARC 002 B - 割り切れる日付 (灰色)

現在の AtCoder ではあまり出なさそうな問題。こういうのは Python 楽だね。 問題へのリンク 問題概要 (西暦) ÷ (月) ÷ (日) が整数となるような日付を「割り切れる日付」と呼ぶ。 日付が "2020/11/14" のようなフォーマットで与えられる。その日付以降の最…

AOJ 2297 Rectangular Stamps (JAG 夏合宿 2011 day2-H) (450 点)

状態空間を上手に削減する系の問題 問題へのリンク editorial 問題概要 種類の長方形形状 () をしたスタンプがある (それぞれ「赤」「緑」「青」の 3 種類がある)。 これらを使って 4 × 4 のグリッド上に所望の模様を作りたい。グリッドからはみ出して押して…

AtCoder ARC 042 D - あまり (黄色)

離散対数の verify に 問題へのリンク 問題概要 4 つの整数 が与えられる。 は素数である。 整数 が の範囲を動くときの、 を で割ったあまりの最小値を求めよ。 制約 は素数 考えたこと まず、 を満たす最小の正の整数 を求める (これを位数と呼ぶ)。これは…

AtCoder ABC 181 C - Collinearity (灰色, 300 点)

幾何っぽい問題。確かに数学ゲーではあるのだけど、平行判定は「計算幾何」の知見として習得してしまっても良さそう。 問題へのリンク 問題概要 二次元平面上に 個の点 () が与えられる。 これらのうちの 3 点であって、同一直線上にあるものが存在するかど…

AtCoder ABC 181 D - Hachi (茶色, 400 点)

整数 を 8 で割ったあまりは、 の下三桁を 8 で割ったあまりに等しい! 問題へのリンク 問題概要 整数 が長さ の文字列として与えられる ( は '1'〜'9' のみで構成される)。 の各文字を並び替えてできる整数の中に、8 の倍数となるものが存在するかどうかを…

AtCoder ARC 107 B - Quadruple (茶色, 400 点)

半分全列挙した! 問題へのリンク 問題概要 正の整数 と整数 が与えられる。以下の条件を満たす正の整数 の組の個数を求めよ。 制約 考えたこと 愚直な方法としては、次のように 4 重ループをする解法が考えられるかもしれない。しかしこれでは の計算量を要…

AISing Programming Contest 2020 C - XYZ Triplets (灰色, 300 点)

ごとに考えるのではなく、集計する考え方をするのがポイント!!! 問題へのリンク 問題概要 正の整数 が与えられる。各 に対して、 は正の整数 を満たすような の組の個数を求めよ。 制約 考えたこと 最初に特定の整数 に対して は正の整数 を満たす の個数…

AtCoder ABC 043 C - いっしょ (ARC 059 C) (茶色, 200 点)

本当にただ全探索するだけ!!! でも意外とこういうのが思いつかれにくいかもしれない。 問題へのリンク 問題概要 (意訳) 長さ の整数列 が与えられる。今、整数 を 1 つ選ぶ。そして整数列をすべて に書き換える。それに要するコストは で与えられる。適切…

AtCoder ABC 042 C - こだわり者いろはちゃん (ARC 058 C) (緑色, 300 点)

記念すべき新体制 AtCoder になってからの初の rated ABC の C 問題!!! 問題のリンク 問題概要 以上の整数のうち、 種類の数値 のいずれも含まない最小のものを求めよ。 制約 考えたこと 真っ先に思い浮かぶ方法は、単純に と順々に試していって「 をいず…