全探索
for 文の練習！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。 のうち母音字の個数、つまり a，i，u，e，o の個数の総和を求めよ。 解法 文字列 の文字を 1 個ずつ、for 文を使って調べていきましょう。 コード #include <bits/stdc++.h> using namespace std; int</bits/stdc++.h>…
多重 for 文に慣れよう！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 を満たす整数の組 の個数を求めよ。 制約 解法 多重 for 文に慣れましょう！ 数列 の 番目と、数列 の 番目をすべて調べるのは、次のような 2 重の for 文で記…
for 文の練習！ 問題へのリンク 問題概要 長さ の数列 (すべての要素は互いに相異なる) について、最大値を考えたとき、その左側の総和と、右側の総和をそれぞれ求めよ。 制約 解法 この問題では、数列 の最大値だけではな、 が最大となるような も求める必…
多重 for 文の全探索に慣れよう！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。次の条件を満たす 3 つ組の整数 が存在するかどうかを判定せよ。 の 文字目は 'I' である の 文字目は 'O' である の 文字目は 'I' である 制約 解法 を満たすような …
このような問題を解くためにも、「バケット」を習得しよう！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 こっらの数列の双方に登場する数をすべて昇順で出力せよ。 制約 解法 (1)：1 から 100 までの数を順に調べる 制約を見よう…
一見難しく見えるけど、実は単純な問題！ 問題へのリンク 問題概要 整数 の書かれた 個の宝箱と、整数 の書かれた 個の鍵がある。 宝箱 は整数 が書かれた鍵を使うことで解錠できる。同じ鍵を使って複数の宝箱を解錠してもよい。 解錠できる宝箱の個数の最大…
二重の for 文に慣れよう！ 問題へのリンク 問題概要 長さが の数列 と、長さが の数列 が与えられる。 を満たすような組 (, ) の個数を求めよ。 制約 考えたこと この問題に限らず、2 つの数列からそれぞれ要素 をとってきて、それが条件を満たすかどうかを…
実装問題！ 問題へのリンク 問題概要 のグリッドがあって、各マスは白色または黒色に塗られている。今、「白色のマスを選んで黒色に塗る」という操作を高々 2 回まで実施できる。 操作後に、縦・横・斜めのいずれかに連続して 6 個のマスが黒色になるように…
ビット全探索の典型問題！ 問題へのリンク 問題概要 ポップコーンには 種類の味 がある。 一方、ポップコーンを得る 個の店 がある。各店 でどの味のポップコーンを売っているかを表す文字列 が与えられる。文字 が 'o' であるとき、店 で味 を売っているこ…
条件を上手に言い換えて、探索しやすい感じにしよう！ 問題へのリンク 問題概要 をちょうど 2 個ずつ含む数列 が与えられる。 次の条件を満たす の個数を求めよ。 「数列中の、値が であるような 2 つの要素は、ちょうど 1 個の他の要素を挟む」 制約 考えた…
問題文の理解が大変かもしれない。 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。次の条件を満たす 2 角整数 () が存在しるかどうかを判定せよ。 「文字列 を 文字ごとに分割したとき、各分割された文字列の 文字目を連結して得られる文字…
基本的な for 文の問題 問題へのリンク 問題概要 個の文字列が与えられる。各文字列は "Takahashi" か "Aoki" のいずれかである。 "Takahashi" が何個あるかを数えよ。 解法 個の文字列を順に受け取って、"Takahashi" と一致するものを数えれば良い。 #inclu…
二次元配列の基本問題！ ただし、問題文の意味を理解するのが少し大変かもしれない。 問題へのリンク 問題概要 のグリッドがある。グリッドの各文字は最初はすべて '.' である。今、 を満たす整数 をとり、 かつ を満たすマス の文字を '#' へと書き換えた。…
探索してしまうのが楽だと思われる。 問題へのリンク 問題概要 整数値 が与えられる。 以上の整数のうち、最小のゾロ目の数を答えよ。 制約 考えたこと 基本的には、次の方針がとれそうだ。 の順に探索し、最初に がゾロ目である瞬間を捉えて、 を出力する。…
全探索でやってしまうのが楽だと思われる。 問題へのリンク 問題概要 正の整数 が与えられる。 をともに割り切る整数のうち、 番目に大きいものを求めよ。 制約 をともに割り切る整数のうち、 番目に大きいものが存在する 考えたこと 全探索で解いてしまうの…
ザ・6Q という感じの問題！ 問題へのリンク 問題概要 個の文字列 が与えられる。 これらの文字列から 2 個選んで連結して得られる文字列が回文になることがあり得るかどうかを判定せよ。 解法 この問題は 2 つのパートで成り立っている。 個の文字列から つ…
とても面倒な全探索問題 問題へのリンク 問題概要 サイズが等しいとは限らない 3 つの白黒のグリッド が与えられる。 ある巨大なグリッドに、2 つのグリッド を重ね合わて (黒色部分について OR をとる)、そこから適切に長方形領域を切り出すことで、グリッ…
問題の意味を理解するのが難しいが、理解してしまえばビット全探索で解けることは比較的分かりやすいと思う！ 問題へのリンク 問題概要 本の鍵 があり、それぞれ本物であるか、ダミーであるかのいずれかである。ドア X があり、鍵のうちの 本以上の本物が使…
「線形探索」と「最小値を求める」の組み合わせ技！ 問題へのリンク 問題概要 個のペア値 が与えられる。 を満たすような についての、 の最小値を求めよ。そのような が存在しない場合は "TLE" と出力せよ。 解法 for 文を用いて、各 i について t[i] <= T …
二次元配列を二重 for 文で調べる最低ライン！ 問題へのリンク 問題概要 のグリッドにアルファベット文字が書かれたものが 2 つ () 与えられます。 これらは 1 箇所のみ異なっていることが保証されます。 であるような を答えてください。 制約 解法 (C++) …
これはちょっと整理が大変な問題。時々問題文に登場する 0.5 という数値がなんなのかを知れる問題とも言える。 問題へのリンク 問題概要 個の区間がある。各区間は 4 タイプあり、 タイプ 1：区間 タイプ 2：区間 タイプ 3：区間 タイプ 4：区間 となってい…
古き良き、ABS にも入れた代表的問題。 問題へのリンク 問題概要 10000 円、5000 円、1000 円が合計 枚ある。 このとき、これらの合計金額が 円になることがありうるかどうかを判定し、ありうるならばそれを 1 つ答えよ。 制約 解法 次の記事に解法を書いて…
計算時間の意識が必要になる問題！ 鉄則本の問題なのでメモ程度に。 問題へのリンク 問題概要 赤・青・白の 3 枚のカードがあり、それぞれに 1 以上 以下の整数を書き込む。 3 枚のカードの数の合計を にする書き方は何通りあるか？ 制約 メモ 赤・青・白の…
break を忘れずに！ 問題へのリンク 問題概要 数列 が与えられる。 を満たす最小の を求めよ (存在しなければ -1 を出力せよ)。 解法 for 文を用いて、調べていこう。 条件を満たすような最小の を求めたいので、for 文での探索中に見つかったら、その瞬間に…
「組」を全探索する問題！ 問題へのリンク 問題概要 個の整数 から 3 個選んで、その和を 1000 にすることが可能かどうかを判定せよ。 解法 github.com コード #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> A(N); for (int i = 0; </int></bits/stdc++.h>…
二重 for 文の練習！ 鉄則本の例題なので解法はメモ程度に。 問題へのリンク 問題概要 2 つの数列 と が与えられる。 これらから要素を 1 つずつ選び、和が となるようにすることが可能か判定せよ。 メモ 二重の for 文を使おう！ コード #include <bits/stdc++.h> using na</bits/stdc++.h>…
整数に対する for 文を用いての全探索です！ 問題へのリンク 問題概要 以上 以下の整数のうち、100 の約数であるものは存在するか、判定せよ。 解法 github.com コード #include <bits/stdc++.h> using namespace std; int main() { int A, B; cin >> A >> B; bool res = fa</bits/stdc++.h>…
線形探索法の基本問題！ 鉄則本の問題なので、解法はメモ程度に。 問題へのリンク 問題概要 個の整数 の中に、整数 が含まれるかどうかを判定せよ。 メモ for を使った全探索です！ コード #include <bits/stdc++.h> using namespace std; int main() { // 入力 int N, X; c</bits/stdc++.h>…
とても教育的な問題ですね。 問題へのリンク editorials 問題概要 0 以上 9 以下の整数からなる、 個の整数 が与えられる。 数列 の中に一度以上登場する整数を小さい順に出力せよ。 解法 (1)：値 0, 1, ..., 9 について個別に全探索 1 つめの解法は まず、…
for 文を用いるのが楽だと思う。 問題へのリンク 問題概要 以上 以下の の倍数が存在するならば 1 つ求め、存在しない場合は -1 を出力せよ。 制約 考えたこと for 文を用いるのが最も楽だと思う。 について、 で割り切れるかどうかを判定していき、 割り切…
