全探索:for文
全探索しよう！ こういう問題で、ただちに「全探索しよう」と思えるかどうかがすごく大事！ 問題へのリンク 問題概要 長さの等しい文字列 が与えられる。 に対して、次の操作を高々 1 回実行することで、 に一致させられるかどうかを判定せよ。 (操作) の隣…
A 問題としては、少し難しめな感じ。 問題へのリンク 問題概要 1, 2, 3, 4, 5 を並び替えて得られる数列 が与えられる。この数列に対して 「隣接する様子を swap する」 という操作をちょうど 1 回だけ行って、単調増加にできるかどうかを判定せよ。 考えた…
面白かった！ 問題へのリンク 問題概要 英小文字および文字 '?' からなる文字列 が与えられる。 の各 '?' を英小文字に置き換えてできる文字列のうち、次の条件を満たす辞書順最小のものを求めよ。 (条件) 文字列 を連続する部分文字列として含む 制約 考え…
日頃から「まずは全探索！」という意識があれば、この手の問題は全探索でできると気づけるはず！ 問題へのリンク 問題概要 ビーカーに対して、次の 4 種類の操作を好きな順序で好きな回数だけ実行する。 ビーカーに g の水を入れる ビーカーに g の水を入れ…
全探索に慣れよう！ 問題へのリンク 問題概要 同じ文字列を二個連結してできるような文字列を「偶文字列」とよぶ。 与えられた偶文字列 について、末尾の文字を 1 文字以上消して作れる偶文字列のうち、その最大長を答えよ。 制約 考えたこと 全探索しよう！…
この手のものは関数化するのがオススメ！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のうち、2 で割れる回数が最大のものを求めよ（タイがないことが証明できる）。 制約 考えたこと 全探索しよう！ 具体的には、 について、「 を 2 …
計算量の意識が必要になる良問！ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。これを左右に 2 つに分ける（左右ともに 1 個以上はとる）。 左側の要素の総和を 、右側の要素の総和を とするとき、 の最小値を求めよ。 制約 考えたこと もし…
全探索思考に慣れてさえいれば、 の解法ならすぐに思いつく。少し工夫して、 の解法になる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。数列 の部分数列 であって が等差数列である である という条件を満たすものを考える。それらの数列の最大長…
サンプルを見れば上限が分かる系の問題！ 問題へのリンク 問題概要 各桁の値が 1 である数をレプユニット数という。 レプユニット数 3 個の和として考えられる数のうち、 番目に小さい数を求めよ。 制約 考えたこと まず、問題文の条件を満たす数をトリレプ…
探索アプローチでも解けるし、整数論的考察で解くこともできる。 問題へのリンク 問題概要 の倍数であって正の整数であるものをいくつか用意する。 その総和を で割った余りが となることはありうるか？ 制約 考えたこと まず、「いくつかの正の の倍数を足…
多重 for 文の練習問題！ 問題へのリンク 問題概要 二次元平面上に 人の学生と、 個のチェックポイントがある。学生 は座標 にいて、チェックポイント は座標 にいる。 各学生について、その学生からマンハッタン距離が最も近いチェックポイントを求めよ (タ…
ちょっと重たい全探索問題 問題へのリンク 問題概要 の形に配列された二次元文字列 が与えられる。 に対して、次の操作を繰り返すことで に一致させたい。 反時計回りに 90 度回転する (コスト 1) 時計回りに 90 度回転する (コスト 1) 1 マス選んで文字を変…
偶数と奇数に関する理解も問われる問題。 問題へのリンク 問題概要 2 つの整数 が与えられる。 「 を並び替えると等差数列をなす」 という条件をみたすような整数 が何通りあるか求めよ。 制約 解法 (1)：数学的に解く まず、 の大小関係で場合分けして考え…
これも色んな解法がある！ 問題へのリンク 問題概要 英小文字からなる 3 文字以上 100 文字以下の文字列 が与えられる。 はある 1 文字を除いて全て同じ文字で構成されています。その異なる文字があるのは何文字目か？ 制約 解法 (1)：全探索 大抵の問題は、…
for 文のいい練習問題！ 問題へのリンク 問題概要 英小文字と文字 . のみからなる文字列 が与えられる。 を文字 . で分割したときの末尾の文字列を出力してください。 制約 には文字 . が 1 つ以上含まれる 考えたこと まずは、 に含まれる文字 . のうち、最…
基礎的な線形探索の問題！ 問題へのリンク 問題概要 アルファベット文字からなる文字列 が与えられる。次の条件を満たすかどうかを判定せよ。 の先頭の文字は大文字である の先頭以外の文字はすべて小文字である 考えたこと まず、先頭の文字が小文字である…
ペアを全探索する問題！ 問題へのリンク 問題概要 人がいて、人 の名字は 、名前は である。 同姓同名であるような人の組が存在するかを求めよ。 制約 考えたこと 0-indexed で考える。 を満たす であって、 かつ を満たすものが存在するかどうかを求めれば…
集計処理系の良問！ 問題へのリンク 問題概要 英小文字からなる文字列 について、どの英小文字も登場回数が偶数回であるかどうかを判定せよ。 制約 解法 (1)：各文字について登場回数を見ていく まずは愚直な解法を考えよう。文字 = 'a', 'b', ..., 'z' につ…
同じ文字が連続するかどうかを判定するのは、しばしば見かけますね。ラストに注意！ 問題へのリンク 問題概要 "salty" または "sweet" からなる 個の文字列 がこの順に与えられる。 "sweet" が 2 回連続すると、それ以降の文字列を受け入れられなくなる。す…
の制約が小さいので、「区間」を思い切って全部探索しよう！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 を満たすような についての、 の値の最大値を求めよ。 制約 解法 この手の問題で悩んでしまうのはもったいないと言えます！ まずは、コンピ…
for 文の練習！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。 のうち母音字の個数、つまり a，i，u，e，o の個数の総和を求めよ。 解法 文字列 の文字を 1 個ずつ、for 文を使って調べていきましょう。 コード #include <bits/stdc++.h> using namespace std; int</bits/stdc++.h>…
多重 for 文に慣れよう！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 を満たす整数の組 の個数を求めよ。 制約 解法 多重 for 文に慣れましょう！ 数列 の 番目と、数列 の 番目をすべて調べるのは、次のような 2 重の for 文で記…
多重 for 文の全探索に慣れよう！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。次の条件を満たす 3 つ組の整数 が存在するかどうかを判定せよ。 の 文字目は 'I' である の 文字目は 'O' である の 文字目は 'I' である 制約 解法 を満たすような …
一見難しく見えるけど、実は単純な問題！ 問題へのリンク 問題概要 整数 の書かれた 個の宝箱と、整数 の書かれた 個の鍵がある。 宝箱 は整数 が書かれた鍵を使うことで解錠できる。同じ鍵を使って複数の宝箱を解錠してもよい。 解錠できる宝箱の個数の最大…
二重の for 文に慣れよう！ 問題へのリンク 問題概要 長さが の数列 と、長さが の数列 が与えられる。 を満たすような組 (, ) の個数を求めよ。 制約 考えたこと この問題に限らず、2 つの数列からそれぞれ要素 をとってきて、それが条件を満たすかどうかを…
実装問題！ 問題へのリンク 問題概要 のグリッドがあって、各マスは白色または黒色に塗られている。今、「白色のマスを選んで黒色に塗る」という操作を高々 2 回まで実施できる。 操作後に、縦・横・斜めのいずれかに連続して 6 個のマスが黒色になるように…
条件を上手に言い換えて、探索しやすい感じにしよう！ 問題へのリンク 問題概要 をちょうど 2 個ずつ含む数列 が与えられる。 次の条件を満たす の個数を求めよ。 「数列中の、値が であるような 2 つの要素は、ちょうど 1 個の他の要素を挟む」 制約 考えた…
問題文の理解が大変かもしれない。 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。次の条件を満たす 2 角整数 () が存在しるかどうかを判定せよ。 「文字列 を 文字ごとに分割したとき、各分割された文字列の 文字目を連結して得られる文字…
基本的な for 文の問題 問題へのリンク 問題概要 個の文字列が与えられる。各文字列は "Takahashi" か "Aoki" のいずれかである。 "Takahashi" が何個あるかを数えよ。 解法 個の文字列を順に受け取って、"Takahashi" と一致するものを数えれば良い。 #inclu…
二次元配列の基本問題！ ただし、問題文の意味を理解するのが少し大変かもしれない。 問題へのリンク 問題概要 のグリッドがある。グリッドの各文字は最初はすべて '.' である。今、 を満たす整数 をとり、 かつ を満たすマス の文字を '#' へと書き換えた。…
