【分野別 初中級者が解くべき過去問精選 100 問】を初級者がC++で解く【全探索：全列挙】

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】の2-3. 分野別　初中級者が解くべき過去問精選 100 問を初級者がC++で解いていきます。

全探索：全列挙

1　ITP1_7_B - How Many Ways?

ふつうに全探索するだけ。選んだ数字の合計がxだったらカウント。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int n, x;
  
  while (1) {
    cin >> n >> x;
    if ((n == 0) && (x == 0)) break;
    
    int ans = 0;
    rep(i, 1, n + 1){
      rep(j, i + 1, n + 1) {
        rep(k, j + 1, n + 1) {
          if (i + j + k == x) ans++;
        }
      }
    }
    cout << ans << endl;
  }
}

2　AtCoder Beginner Contest 106 B - 105

全探索で順番に判定していく。1と自身を約数に持つことは明らかなので無視して、約数が6つ見つかればOK。また、奇数なのも前提条件なので、偶数も無視している。

#include <bits/stdc++.h>
using namespace std;

int main(void) {
  int N;
  cin >> N;
  
  int ans = 0;
  for (int i = 1; i <= N; i += 2) {
    int cnt = 0;
    for (int j = 3; j < i; j += 2) {
      if (i % j == 0) {
        cnt++;
      }
    }
    if (cnt == 6) {
      ans++;
    }
  }
  cout << ans;
}

3　AtCoder Beginner Contest 122 B - ATCoder

文字列の先頭から一文字ずつ見ていって、ACGTが連続で出た回数を数える。

#include <bits/stdc++.h>
using namespace std;

int main() {
  string S;
  cin >> S;
  
  int tmp = 0, mx = 0;
  for (auto s:S) {
    if ((s == 'A') | (s == 'C') | (s == 'G') | (s == 'T')) {
      tmp++;
    }
    else {
      mx = max(mx, tmp);
      tmp = 0;
    }
  }
  mx = max(mx, tmp);
  cout << mx;
}

4　パ研杯2019 C - カラオケ

2曲の組み合わせを全探索して得点の最大値を取る。

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define fore(i, n) for(auto &i:n)
#define all(x) x.begin(), x.end()
using namespace std;

int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<long long>> A(N, vector<long long>(M));
  rep(i, 0, N) {
    rep(j, 0, M) {
      cin >> A.at(i).at(j);
    }
  }
  
  long long ans = 0;
  rep (i, 0, M) {
    rep(j, i + 1, M) {
      if (i == j) continue;
      long long tmp = 0;
      rep(k, 0, N) {
        tmp += max(A.at(k).at(i), A.at(k).at(j));
      }
      ans = max(ans, tmp);
    }
  } 
  cout << ans;
}