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

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

全探索

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 ????, 難易度 8)

難しかった!!! 予選の問 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 問題!!! 問題のリンク 問題概要 以上の整数のうち、 種類の数値 のいずれも含まない最小のものを求めよ。 制約 考えたこと 真っ先に思い浮かぶ方法は、単純に と順々に試していって「 をいず…

AOJ 1618 池のある庭園 (ICPC 国内予選 2017 C) (150 点)

この手の、単純だけど for 文ネストがエグい全探索、案外 AtCoder で見ないかもしれない 問題へのリンク 問題概要 の二次元グリッドが与えられる。各グリッドには 0 以上 9 以下の整数値が書かれている。 グリッド上で、以下の条件を満たす長方形領域を考え…

AtCoder ARC 104 E - Random LIS (赤色, 700 点)

ゲーは確かに面白いかもしれない。 問題へのリンク 問題概要 長さ の整数列 が与えらる。 同じく長さ の整数列 は、 各 について独立に、 を満たす整数の一様分布からランダムに選ばれる。 このとき、 の最長増加部分列の長さの期待値を mod 1000000007 で計…

AOJ 3166 Not Found (HUPC 2020 day1-C)

単純に bit 全探索で良さそう。 問題へのリンク editorial 問題概要 長さ の 0 と 1 からなる文字列が 個与えられる ()。以下の条件を満たす文字列 が存在するかどうかを判定し、存在するならば具体例を一つ与えよ。 の長さは は '0' と '1' と '*' のみで構…

ACL Contest 1 B - Sum is Multiple (青色, 600 点)

中国剰余定理使う問題楽しいよね! 問題へのリンク 問題概要 正の整数 が与えられる。以下の条件を満たす最小の正の整数 を求めよ。 が の倍数である 制約 考えたこと まず、 なので、問題の条件は次と同値になる。 が の倍数である ここで改めて を で置き…

AtCoder ABC 179 C - A x B + C (灰色, 300 点)

でもできる! 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような正の整数 の組の個数を求めよ。 制約 考えたこと こういう整数問題は、実のところ本当に整数論的考察を必要とするパターンは少なくて、大抵は探索ベースの解法が有効になる!!…