はじめに...
こんにちは~
この記事は初心者向けのものとなっております
あの有名な精選100を分野別に解いていきます
今回は全探索:全列挙の4問です
1 ITP1_7_B - How Many Ways?
問題サイトはこちらです!
問題文↓
1 から n までの数の中から、重複無しで3つの数を選びそれらの合計が x となる組み合わせの数を求めるプログラムを作成して下さい。
ループするものの制約が3≦n≦100かつ、数字の重複がない場合なので、普通に全探索すればいいですね
こちらが作成したコードです!
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { // 0 0が来るまでループさせて全探索. while (1) { int n = 1, x = 1; cin >> n >> x; ll ans = 0; if (n == 0 && x == 0) break; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { for (int k = j + 1; k <= n; k++) { if (i + j + k == x) ans++; } } } cout << ans << endl; } return 0; }
入力例の受け取り個数が少し特殊かもですね。。。
2 AtCoder Beginner Contest 106 B - 105
問題サイトはこちらです!
問題文↓
1 以上 N 以下の奇数のうち, 正の約数を ちょうど 8 個持つようなものの個数を求めよ.
制約が1≦n≦200なので、最大200個の数字の約数の個数を求めればいいですね
約数の個数の求め方としては、ある整数nを素因数分解し、
n=p₁ⁿ‐¹×p₂ⁿ‐²×p₃ⁿ‐³・・・×pₐⁿ‐ⁿとすると、
求める約数は(n_1+1)(n_2+1)(n_3+1)・・・(n_n+1)となります
つまり、素因数分解してでてきた数字の指数+1をかけ合わせたものですね
結果としてこのようなコードになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199}; // 約数の個数を調べる関数. void count(int n, int &output) { vector<int> A; for (auto &p : primes) { A.push_back(0); while (n % p == 0) { n /= p; A.back()++; } } for (auto &a : A) { output *= (a + 1); } } int main() { int n; cin >> n; ll ans = 0; // 1-nまでを全探索. rep(i, n) { if ((i + 1) % 2 == 1) { int o = 1; count(i + 1, o); if (o == 8) { ans++; } } } cout << ans << endl; return 0; }
ちなみに、解説だと約数を列挙してました(知りません)
3 AtCoder Beginner Contest 122 B - ATCoder
問題サイトはこちらです!
問題文↓
ある文字列Sが与えられるので、Sの部分文字列のうち、ACGTの文字以外を含まない文字列の最大長を求めてください
制約を見ると、Sの長さは10以下であることがわかるので、最大、1~10までの和で55個の文字列を調べたら終了です
よって以下のようになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; // ACGT以外の文字が含まれていないかどうかを調べる関数. bool isACGT(string s) { bool flag = true; for (int i = 0; i < s.size(); i++) { if (s[i] != 'A' && s[i] != 'C' && s[i] != 'G' && s[i] != 'T') { flag = false; } } return flag; } int main() { string s; cin >> s; int ans = 0; for (int i = 0; i < s.size(); i++) { for (int j = 0; j < s.size() - i + 1; j++) { // 文字列を切り出して全探索. if (isACGT(s.substr(i, j))) { ans = max(ans, (int)s.substr(i, j).size()); } } } cout << ans << endl; return 0; }
そのままやれば大丈夫だと思います!
4 パ研杯2019 C - カラオケ
問題サイトはこちらです!
1,2,...,N と番号づけられている N 人の生徒から成るグループが,「全国統一カラオケコンテスト」に出場することとなりました. このコンテストで歌える曲は,曲 1,曲 2,...,曲 M の M 曲あります. また,番号 i の生徒が曲 j を歌うと,必ず A_i,j 点を取ります. さて,コンテストのルールは,以下のようになります. M 曲の中から 2 つの曲を選ぶ.(それぞれ T_1 と T_2 とする.) それぞれの生徒が,曲 T_1 と曲 T_2の両方を歌う. 各生徒の得点は,その生徒が歌った 2 つの曲の点数のうち高い方となる. グループの得点は,生徒 1,2,...,N の得点の合計となる. そのとき,グループの得点として考えられる最大の値を求めてください.
この問題は、制約が最大100ととても小さいので、全探索で大丈夫そうです
入力例2
3 4 37 29 70 41 85 69 76 50 53 10 95 100
この入力例を考えると、横向きに見るのが、M²、縦向きに見るのがNなので、O(M²N)となり、最大で約10⁶回のループで済みます
よってコードは以下のようになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { int n, m; cin >> n >> m; vector<vector<ll>> A(n, vector<ll>(m)); rep(i, n) { rep(j, m) { cin >> A[i][j]; } } ll ans = 0; // 曲の組み合わせを全探索. rep(i, m) { rep(j, m - i - 1) { ll count = 0; rep(k, n) { count += max(A[k][i], A[k][j + i + 1]); } ans = max(ans, count); } } cout << ans << endl; return 0; }
簡単な(diffが低い)問題で、制約が小さめのときは、必ずでは無いですが、全探索で済みますね
終わりに...
これは、毎週火曜日にやっていこうかなと思います!
では、お疲れ様でした!