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

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

全探索

AtCoder ABC 133 C - Remainder Minimization 2019 (300 点)

高校数学で 「 を整数として は 3 の倍数であることを示せ」 という問題はよくあったと思う。これは「連続する 3 整数には 3 の倍数が含まれる」というのが理由になっている。今回こんな感じのことを考える。 問題へのリンク 問題概要 2 つの整数 があたえら…

AtCoder ABC 051 B - Sum of Three Integers (200 点)

AtCoder 過去問精選10問記事だと「計算量意識するのは 300 点から」って書いてしまっているのだけど、この問題の存在がちょっと心苦しいかも ^^; 問題へのリンク 問題概要 2 つの整数 が与えられます。 3 つの 以上 以下の整数 の組であって、 を満たすもの…

diverta 2019_2 B - Picking Up (300 点)

こういう全探索、意外と思い浮かぶようになるまでが遠いよね。 そして のケースが結構厄介 ^^; 問題へのリンク 問題概要 二次元平面上に 点がある。最初に整数 を自分で決める。そして、 個の点を好きな順序で順に辿っていく。このとき、 最初の点では +1 そ…

AtCoder ABC 128 D - equeue (400 点)

こういう全探索が意外と出てこないという意見はよく聞くよね。 同時に「複数種類の操作を行える問題では、操作の流れを単純化する」という典型思考を試す問題でもある。 問題へのリンク 問題概要 あなたは誕生日プレゼントとして友人から dequeue D を貰いま…

AtCoder ABC 128 C - Switches (300 点)

bit 全探索 問題へのリンク 問題概要 個のスイッチがある。スイッチによって 個の電球が点いたり消えたりする。 電球 は 個のスイッチに繋がっており、スイッチ のうち on になっているスイッチの個数を 2 で割った余りが に等しい時に点灯します。 全ての電…

Chokudai SpeedRun 002 J - GCD β (500 点)

「探索候補は実はそう多くない」という教育的問題!!! 問題へのリンク 問題概要 組の整数ペア がある。各ペアから整数をどちらかを選ぶ。こうして選ばれた 個の整数の最大公約数の最大値を求めよ。 制約 考えたこと 約数と言われて思い浮かべるべきことの…

AtCoder ABC 114 D - 756 (400 点)

editorial は「75」という整数の特徴をフル活用している。 そして 75 という整数の特徴を活用しない DP による方法もあると説いている。 ここでは 75 という整数の特徴も活用せず、DP もしない (といっても DP への改良は容易) 愚直な全探索でも通った。 問…

diverta 2019 D - DivRem Number (500 点)

楽しかった 問題へのリンク 問題概要 正の整数 が与えられる。 以下の条件を満たす正の整数 の個数を求めよ: を で割ったときの商と余りが一致する 制約 考えたこと とりあえず について手元で計算しているうちに、商と余りとが一致した値 として考えられる…

diverta 2019 B - RGB Boxes (200 点)

これと大体一緒かな。 むしろ合計枚数に関する制約がない分、やや難しくなっているかもしれない。 問題概要 を正の整数とする。 を満たすような 0 以上の整数 の組が何通りあるか求めよ。 制約 考えたこと 愚直に探索しようと思うと int res = 0; for (int r…

Tenka1 2019 C - Stones (300 点)

これをもっと早く 問題へのリンク 問題概要 長さ の白黒列が与えられる。最小個数のマスの白と黒を入れ替えることで、「黒」と「白」とが連続している箇所がないようせによ。 制約 考えたこと つまりは「白白白白黒黒黒黒黒」のように 左 left 個が白 右 N -…

AtCoder ABC 124 C - Coloring Colorfully (300 点)

一見複雑だけど、実質 2 通りしかないというやつ 問題へのリンク 問題概要 長さが の 0-1 列が与えられる。何個かについて 0 と 1 を入れ替えることで、 0 と 1 が交互に並んでいる状態 にしたい。そのようなことが可能な方法のうち、入れ替える数字の個数の…

AtCoder ABC 124 A - Buttons (100 点)

たったこれだけの問題でも、学ぶべきことがすごくあるイメージ!!! 問題へのリンク 問題概要 2 つのボタンがあってそれぞれ大きさが である。 大きさ のボタンを押すとコインが 円もらえて、ボタンの大きさが 1 減って になる。 2 回だけ好きなボタンを押…

AtCoder ABC 114 C - 755 (300 点)

現代の AtCoder では少ない、再帰関数を用いると良い感じに書ける全探索問題。 すごく教育的な問題!!!!! 問題へのリンク 問題概要 10 進法表記で各桁の値が 7 と 5 と 3 のみで、かつ 7, 5, 3 がすべて一度以上は登場するような数を「753 数」と呼ぶこ…

AtCoder AGC 006 A - Prefix and Suffix (200 点)

なのでいくらでも何でもできるという感覚 問題へのリンク 問題概要 すぬけ君は次の条件を満たす文字列に興味があります。 長さ 以上である。 先頭 文字が文字列 に一致する。 末尾 文字が文字列 に一致する。 条件を満たす文字列のうち、最も短いものの長さ…

AOJ 1131 Unit Fraction Partition (ICPC 国内予選 2004 C)

有理数ライブラリ整備とか大げさなことせずに全探索頑張るのが本筋であろうが、ここでは有理数ライブラリの足し算の verify としてやってみた。 問題へのリンク 問題概要 有理数 p/q を n 個以下の 1/r な形の有理数の和として 分母 r の積が a 以下となるよ…

AOJ 3053 Phone Number (RUPC 2019 day2-C)

一瞬詰まった。とりあえず 9! できるなと思ったあと、長さ の文字列を処理するのはどうするんだろ...となっていた。前処理が本質な感じがする。 問題へのリンク 問題概要 "31415926535" のような 1 〜 9 からなる長さ の文字列 が与えられる。 今、 137 456 …

AtCoder ABC 119 D - Lazy Faith (400 点)

二分探索で lower_bound とかきっちり無意識的に使いこなせるようになりたいのんな!!! 問題へのリンク 問題概要 一次元の世界を考える。 A 個の神社と、B 個の寺が並んでいる (各神社と各寺の位置情報が 1 つの整数値で与えられる)。 以下の Q 個のクエリ…

AtCoder ABC 119 C - Synthetic Kadomatsu (300 点)

最近の AtCoder は ABC でも考察重視傾向が強くて、こういうのが見落とされがちかもなのん。。。 でも ABC を競プロ入門コンテンツと見たとき、この種の出題がもっと増えると良さそう!!!!! 大事なことを再認識させてくれる感じ。 問題へのリンク 問題概…

AtCoder ABC 073 D - joisino's travel (400 点)

Floyd-Warshall で前処理してどうのこうのする問題。特に ICPC 系などでよくある! 問題へのリンク 問題概要 頂点 辺の重み付き無向グラフが与えられる。このグラフ上で 個のチェックポイントをなす頂点集合が指定されている。好きなチェックポイントからス…

AtCoder ABC 112 C - Pyramid (300 点)

AtCoder ではとても珍しい、注意して考えることの多い、重めの全探索な問題 問題へのリンク 問題概要 ピラミッドの高さを当てたい。 ピラミッドには 中心座標 (Cx, Cy) と 高さ H が定まっており, 座標 (X, Y) の高度は max(H−|X−CX|−|Y−CY|, 0) である。 ま…

AtCoder ARC 100 D - Equal Cut (600 点)

かなり悩んだ 問題へのリンク 問題概要 (ARC 100 D / ABC 102 D) 長さ の整数列 を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を とするとき、 の最小値を求めよ。 制約 考えたこと こういうの、 連続する区間が 4 個だ…

AtCoder ABC 104 C - All Green (300 点)

すごく教育的な「bit 全探索 + Greedy」なん!!! 問題へのリンク 問題概要 100 点問題, 200 点問題, 300 点問題, ..., 100× 点問題がそれぞれ 問ずつある。 今、精進して合計で 点以上獲得したい。ただし、100× 点問題を 問すべて解いた場合にはボーナスと…

AOJ 2613 Unordered Operators

構文解析練習第三弾。AOJ-ICPC 350 点。 問題へのリンク 問題概要 (5-3*4)*(0-2+1) のような以下の BNF で定義される計算式が与えられる: <expr> ::= ( <expr> ) | <number> | <expr> <op> <expr> <op> ::= + | - | * ただし、通常の演算の優先順位は「*」 -> 「+」「-」であるが、今回はどのように優</op></expr></op></expr></number></expr></expr>…

AOJ 2401 恒等式

せっかく構文解析の練習を少ししたので 問題へのリンク 問題概要 -(a+b)=(-a*-b) (a->b)=(-a+b) ((a*T)+b)=(-c+(a*-b)) のような式たちが恒等式かどうかを判定せよ。すなわち、a や b や c に true と false をどのように当てはめても結果が一致するかどうか…

AtCoder ABC 099 D - Good Grid (400 点)

「前処理」を学べる問題なんな。 問題へのリンク 問題概要 (ABC 099 D) 色が全部で 色ある。 × の盤面がそれぞれ 色のいずれかに塗られている。今この盤面の色を塗り替えて マス () について % 3 の値によって色を類別された状態 (その値が同じマスは同じ色…

AOJ 2427 ほそながいところ

「全探索でもここまで難しいやつもある」という例としてよく挙げられる問題。 ここのページに僕なりの 全探索 重み付き Union-Find 木を使いながら判定 をした解法を記した。

TopCoder SRM 735 D1M QuadraticIdentity

ちょうど中国剰余定理シリーズやっていたので、ピンポイントだったん。 SRM 735 DIV1 Medium QuadraticIdentity 問題概要 整数 が与えられる。 (mod. ) を満たすような < ) をすべて求め、そのサイズが 500 より大きい場合には 500 以下になるまで以下の操作…

AtCoder ARC 099 D - Snuke Numbers (500 点)

完全に冷静さを欠いたし、ハマったん。。。 ARC 099 D - Snuke Numbers 問題概要 (ARC 099 D / ABC 101 D) 正の整数 N に対してその 10 進法での桁の和を f(N) で表す。今、正の整数 N がすぬけ数であるとは、任意の N より大きい正の整数 M に対して f(N) /…

AtCoder AGC 025 A - Digits Sum (200 点)

普通の 200 点でよかった。 AGC 025 A Digits Sum 問題概要 高橋君は 2 つの正の整数 A と B を持っています。 それらの和が N であると分かっているとき、 A の各位の和と B の各位の和の合計として考えられる最小の値を求めよ。 制約 2 <= N <= 105 解法 …