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

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

全探索:for文

AtCoder ABC 307 B - racecar (6Q, 灰色, 200 点)

ザ・6Q という感じの問題! 問題へのリンク 問題概要 個の文字列 が与えられる。 これらの文字列から 2 個選んで連結して得られる文字列が回文になることがあり得るかどうかを判定せよ。 解法 この問題は 2 つのパートで成り立っている。 個の文字列から つ…

AtCoder ABC 307 C - Ideal Sheet (1Q, 水色, 300 点)

とても面倒な全探索問題 問題へのリンク 問題概要 サイズが等しいとは限らない 3 つの白黒のグリッド が与えられる。 ある巨大なグリッドに、2 つのグリッド を重ね合わて (黒色部分について OR をとる)、そこから適切に長方形領域を切り出すことで、グリッ…

AtCoder ABC 112 B - Time Limit Exceeded (7Q, 灰色, 100 点)

「線形探索」と「最小値を求める」の組み合わせ技! 問題へのリンク 問題概要 個のペア値 が与えられる。 を満たすような についての、 の最小値を求めよ。そのような が存在しない場合は "TLE" と出力せよ。 解法 for 文を用いて、各 i について t[i] <= T …

AtCoder ABC 207 C - Many Segments (4Q, 灰色, 300 点)

これはちょっと整理が大変な問題。時々問題文に登場する 0.5 という数値がなんなのかを知れる問題とも言える。 問題へのリンク 問題概要 個の区間がある。各区間は 4 タイプあり、 タイプ 1:区間 タイプ 2:区間 タイプ 3:区間 タイプ 4:区間 となってい…

AtCoder ABC 085 C - Otoshidama (5Q, 茶色, 300 点)

古き良き、ABS にも入れた代表的問題。 問題へのリンク 問題概要 10000 円、5000 円、1000 円が合計 枚ある。 このとき、これらの合計金額が 円になることがありうるかどうかを判定し、ありうるならばそれを 1 つ答えよ。 制約 解法 次の記事に解法を書いて…

鉄則本 A05 - Three Cards (5Q, ★2)

計算時間の意識が必要になる問題! 鉄則本の問題なのでメモ程度に。 問題へのリンク 問題概要 赤・青・白の 3 枚のカードがあり、それぞれに 1 以上 以下の整数を書き込む。 3 枚のカードの数の合計を にする書き方は何通りあるか? 制約 メモ 赤・青・白の…

AtCoder ABC 353 A - Buildings (7Q, 灰色, 100 点)

break を忘れずに! 問題へのリンク 問題概要 数列 が与えられる。 を満たす最小の を求めよ (存在しなければ -1 を出力せよ)。 解法 for 文を用いて、調べていこう。 条件を満たすような最小の を求めたいので、for 文での探索中に見つかったら、その瞬間に…

鉄則本 B03 - Supermarket 1 (6Q, ★2)

「組」を全探索する問題! 問題へのリンク 問題概要 個の整数 から 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>…

鉄則本 A03 - Two Cards (7Q, ★1)

二重 for 文の練習! 鉄則本の例題なので解法はメモ程度に。 問題へのリンク 問題概要 2 つの数列 と が与えられる。 これらから要素を 1 つずつ選び、和が となるようにすることが可能か判定せよ。 メモ 二重の for 文を使おう! コード #include <bits/stdc++.h> using na</bits/stdc++.h>…

鉄則本 B02 - Divisor Check (7Q, ★1)

整数に対する 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>…

鉄則本 A02 - Linear Search (8Q, ★1)

線形探索法の基本問題! 鉄則本の問題なので、解法はメモ程度に。 問題へのリンク 問題概要 個の整数 の中に、整数 が含まれるかどうかを判定せよ。 メモ for を使った全探索です! コード #include <bits/stdc++.h> using namespace std; int main() { // 入力 int N, X; c</bits/stdc++.h>…

AtCoder ABC 220 A - Find Multiple (7Q, 灰色, 100 点)

for 文を用いるのが楽だと思う。 問題へのリンク 問題概要 以上 以下の の倍数が存在するならば 1 つ求め、存在しない場合は -1 を出力せよ。 制約 考えたこと for 文を用いるのが最も楽だと思う。 について、 で割り切れるかどうかを判定していき、 割り切…

AtCoder ABC 165 A - We Love Golf (7Q, 灰色, 100 点)

色んな解法がある! この手の数値的なものに対して「全探索」という解法を選択肢に持てるようにしていこう。 問題へのリンク 問題概要 3 個の正の整数 が与えられる。次の条件を満たす整数が存在するかどうかを判定せよ。 の倍数である 以上 以下である 制約…

AtCoder ABC 327 A - ab (7Q, 灰色, 100 点)

文字列の練習! 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 この文字列 中に、文字 'a' と 'b' が隣接する箇所があるかどうかを判定せよ。 考えたこと for 文を用いて判定していく。添字 i を回していき、 S[i] == 'a' and S[i+…

AtCoder ABC 322 A - First ABC 2 (7Q, 灰色, 100 点)

「連続文字列」を処理する典型問題。 問題へのリンク 問題概要 文字 A, B, C のみからなる長さ の文字列 が与えられる。 文字列 に含まれる連続部分文字列 "ABC" のうち、それが始まる最小の添字を答えよ。"ABC" を含まない場合は -1 を出力せよ。 解法 (1)…