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

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

全探索

AtCoder ABC 166 D - I hate Factorization (400 点)

一瞬ヤバそうに見えるけど、落ち着いて考えると、 くらいまで調べればいいという 問題へのリンク 問題概要 正の整数 が与えられるので、 を満たす整数 を一つ求めよ。 制約 考えたこと こういうの、基本的には全探索。でも という制約を見ると、 あたりまで…

よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜

時は 2020 年 5 月 3 日。 ここ最近、AtCoder では、「再帰関数を用いた DFS な全探索」というタイプの問題が激増しています!!! AtCoder ABC 165 C - Many Requirements (昨日のやつ) AtCoder ABC 114 C - 755 AtCoder ABC 119 C - Synthetic Kadomatsu A…

AtCoder ABC 144 C - Walk on Multiplication Table (300 点)

約数列挙!!! 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような正の整数 の組をすべて考えたときの、 の最小値を求めよ。 制約 考えたこと これはまさに約数列挙の問題!!! 以下の記事の「3. 約数列挙」のところで、本質的に同じ問題の…

AtCoder ABC 162 C - Sum of gcd of Tuples (Easy) (300 点)

素直に for 文を回して全部足せば OK!!! なお、3 つの整数の最大公約数の求め方に注意。 問題概要 を満たすすべての整数 の組に対しての、 の総和を求めよ。 制約 考えたこと 素直に 通りの組について、GCD を求めて合計しても間に合う。なお、3 つの整数…

AtCoder ABC 122 B - ATCoder (200 点)

E8君問題集第3問! 問題へのリンク 問題概要 長さ の文字列 が与えられる。 の連続する部分列であって、'A', 'C', 'G', 'T' のみからなる部分の長さの最大値を求めよ。 制約 考えたこと が小さいので、全部調べても間に合う。連続する部分列は 個ある。 それ…

AtCoder ABC 106 B - 105 (200 点)

E8君問題集の第2問 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のうち、約数の個数がちょうど 8 個あるものが何個あるかを求めよ。 制約 考えたこと 単純に 1 から までの整数それぞれについて、 約数をすべて求めて それが 8 個かど…

AOJ Course ITP1_7_B How many ways?

for 文を多重にするタイプの全探索!!! 問題へのリンク 問題概要 整数 が与えられる。 以上 以下の整数の中から重複なしで 3 個選んで、総和が となる組合せが何通りあるか求めよ (順番はなし)。 制約 考えたこと for 文を多重にするタイプの全探索を書く…

AtCoder ARC 061 C - たくさんの数式 (300 点)

AtCoder 版蟻本に bit 全探索の最初の例題として、この問題を挙げていたので。 問題へのリンク 問題概要 "231" といった 1〜9 の数値で構成された、長さ の文字列 が与えられる。文字列の隙間に '+' を挿入する方法は 通りある。そのそれぞれについての計算…

AtCoder ABC 161 F - Division or Substraction (600 点)

めちゃくちゃ面白かった!!! 問題へのリンク 問題概要 整数 が与えられる。以下の条件を満たす 以上 以下の整数 の個数を求めよ。 整数 を用いて、 に対して操作を行っていく が で割り切れるならば を で置き換えて、そうでない場合には を に置き換える…

AtCoder ABC 159 E - Dividing Chocolate (500 点)

制約が縦方向の bit 管理を要求している感満載 問題へのリンク 問題概要 のグリッドがあって各マスに 0 か 1 が書き込まれている。これに対し、縦横にラインでカットして、部分長方形区域に分けたい。どの区域も 1 の個数が 以下になるようにする。 これを実…

AtCoder ABC 157 C - Guess The Number (300 点)

全探索した! 整数を string 型にするのに手こずってしまった。 問題へのリンク 問題概要 以下の条件を満たす整数があれば、それを出力し、存在しなければ -1 を出力せよ。 ちょうど 桁である 左から数えて 桁目は である。() 制約 考えたこと 存在しない場…

AtCoder ARC 007 D - 破れた宿題

一瞬激ヤバに見えるし、コーナーケースの数もえげつないけど、とりあえず最小の初項はすぐにわかると... 問題へのリンク 問題概要 等差数列があった。 等差数列を concat して得られる文字列から、先頭から何文字かと、末尾から何文字かを削除して得られた文…

AOJ 2574 Magical Switches (JAG 模擬地区 2013 J)

枝刈り探索が根本的に計算量改善することを示せることがある!!! 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…

yukicoder No.968 引き算をして門松列(その3)

その 2 と雰囲気は似ているけど、一気に考えづらくなった! 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっている 以下のクエリに 回答…

yukicoder No.967 引き算をして門松列(その2)

ものすごく間違いやすい雰囲気だったので、探索候補を絞ってから力技で全探索した!!! 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっ…

AtCoder ABC 151 F - Enclose All (最小包含円、600 点)

幾何だ!!!!! そして、こういうので「ギリギリを考える」というのは典型な感じ。 なお、僕は最小包含円のことを知らず、アドホックに解いたけど、ライブラリ貼るだけだったらしい... (その方が計算量も少ない) 他にも、三分探索でも解ける!!! 問題へ…

AtCoder ABC 150 C - Count Order (300 点)

next_permutation の練習になりそう。DFS でも。 問題へのリンク 問題概要 の順列 が与えられます。 が の順列のうち辞書順で何番目か が の順列のうち辞書順で何番目か を求め、それらの差を答えよ。 制約 考えたこと 制約が小さいので、 通りの順列をすべ…

bit 全探索を「再帰関数」で書く 2 つの流儀

0. はじめに bit 全探索は、世の中で「AtCoder 温室育ちだと弱い」と言われるタイプの問題の代表かもしれません。何も考えずに思考停止して全探索すればよいのですが、ちょっと実装が重たい傾向にあって、書き切るのが大変という感じです。difficulty を見て…

AtCoder ABC 146 C - Buy an Integer (300 点)

二分探索の教育的問題ですね! 問題へのリンク 問題概要 正の整数 が与えられる。正の整数 に対して を の桁数とする。このとき を満たす最大の正の整数 を求めよ。 制約 考えたこと わけわからない式だし、二分探索に決まってるやろ!!!という雰囲気があ…

AtCoder ABC 149 C - Next Prime (300 点)

C 問題で整数系のアルゴリズムを確認する問題を出すの良さそうやね。 問題へのリンク 問題概要 2 以上の整数 が与えられる。 以上の最小の素数を求めよ。 制約 素数判定 整数 が素数かどうかを判定するのは、整数論的アルゴリズムで最初くらいに学ぶものです…

AtCoder ABC 147 C - HonestOrUnkind2 (300 点)

とても教育的な問題でしたね!!! ここにまとめました! drken1215.hatenablog.com 以下のような問題です。bit 全探索とよばれているもので、 通りの選択肢をすべて調べ上げる手法を用います。 問題概要 人がいて、それぞれ「正直者」であるか、「不親切な…

bit 全探索

0. はじめに ビット演算については、以下の記事で特集しました。 qiita.com しかし、この中で、bit 全探索に関する説明がだいぶ簡潔すぎたので、ちゃんと書きたいなと思って、この記事書きます!!!ただし、ビット演算に関する知識は前提としているので、そ…

AtCoder ABC 143 D - Triangles (400 点)

教育的ないい問題!!!!! 問題へのリンク 問題概要 本の棒があって、それぞれ の長さをもっている。 このうちの 3 本を選ぶ方法であって、その 3 本で三角形が作れるものは何通あるか? 制約 解法の overview ものすごく色んな解法が考えられる問題だと思…

TopCoder SRM 400 D1E StrongPrimePower

詰めるの大変だった。こういうの 240pt で通せる人ってどうなってるの!? 問題へのリンク 問題概要 2 以上の整数 が与えられる。 が狭義の素数べき (素数 と 2 以上の整数 を用いて と書ける数) であるかどうかを判定し、素数べきの場合には の値を求めよ。…

Educational Codeforces Round 73 E. Game With String (R2400)

面白かったけど場合分けが怖かった 問題へのリンク 問題概要 "...X......XX..X..X.XXX...X..." のような '.' と 'X' からなる長さ の文字列が与えられる。 先手は連続する 個の '.' をすべて 'X' に置き換える 後手は連続する 個の '.' をすべて 'X' に置き…

AtCoder ABC 054 C - One-stroke Path (300 点)

グラフの探索を頑張る問題。現代の AtCoder であまり見ないけど、教育的な全探索問題!!! 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。このグラフ上で頂点 1 から出発するハミルトンパスが何本あるかを数え上げよ。 なおハミルトン…

AtCoder ABC 057 C - Digits in Multiplication (300 点)

整数に関する問題でまずは直面する典型的な事柄を学べる教育的問題!!! 例えば整数 が素数かどうかを判定するのは、実は から まで順に試し割りすればよいという話など。 問題へのリンク 問題概要 正の整数 が与えられる。 を満たす正の整数 の組をすべて…

Codeforces Round #584 - Dasha Code Championship C. Paint the Digits (R1600)

ちょっとややこしかった 問題へのリンク 問題概要 '0' 〜 '9' からなる 文字の文字列があたえられる。各文字を白黒に塗る。 どの黒く塗られた数も、あらゆる白く塗られた数以上である 白く塗られた数を元の文字列の順序で抜き取ったとき、数値は単調非減少で…

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 つの 以上 以下の整数 の組であって、 を満たすもの…