【分野別 初中級者が解くべき過去問精選 100 問】を初級者がC++で解く【全探索：工夫して通り数を減らす全列挙】

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

全探索：工夫して通り数を減らす全列挙

5　AtCoder Beginner Contest 095 C - Half and Half

ピザの買い方は以下の3通りしかない。全て計算して最小値をとればよい。

1. ABピザのみを買う。
2. AピザをX枚、BピザをY枚買う。
3. ABピザを買ってAピザかBピザのどちらか(必要数の少ない方)を完成させて、足りない分はそのピザを個別で買う。

と思って提出してACとなったが、あとから気づいた。
・AピザとBピザを少ない方だけ買い、残りをABピザで補う
というパターンを考慮していなかったが、これでもACになったな。うーん。

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

int main() {
  int A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;
  
  int a, b, c, sum_1, sum_2, sum_3;
  a = 0;
  b = 0;
  c = 2 * max(X, Y);
  sum_1 = a * A + b * B + c * C;
  
  a = X;
  b = Y;
  c = 0;
  sum_2 = a * A + b * B + c * C;
  
  c = 2 * min(X, Y);
  a = X - c / 2;
  b = Y - c / 2;
  sum_3 = a * A + b * B + c * C;
  
  cout << min(min(sum_1, sum_2), sum_3);
}

6　三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN

ありえる暗証番号は000~999の1000通りしかないので全探索する。
3桁の数字を仮決めして、Sからその3桁をつくれるか判定していく。

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

int main() {
  int N;
  string S;
  cin >> N >> S;
  
  long long ans = 0;
  for (int i = 0; i < 1000; i++) {
    string t = (boost::format("%03d") % i).str();
    long long si = 0, ti = 0;
    while (si < N && ti < 3) {
      if (S[si] == t[ti]) {
        ti++;
      }
      si++;
    }
    if (ti == 3) {
      ans++;
    }
  }
  cout << ans << endl;
}

7　JOI 2007 本選 3 - 最古の遺跡

何をどう工夫すればいいのか分からなくてかなり悩んだ問題。1時間くらい考えても全く解法を思いつかなかったので、結局ググってこちらから丸パクリさせてもらった。今になってみれば、なぜ思いつかなかったのか意味が分からない。
柱が2本決まれば、残りの候補の座標を求めることができて、そこに柱が存在するかを調べればよい、というだけの話。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
typedef long long ll;
const ll inf = 1LL << 60;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define rrep(i, b, a) for (ll i = b; i >= a; i--)
#define rrpeq(i, a, b) for (ll i = a; i <= b; 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;}

vector<vector<bool>> G(5001, vector<bool>(5001));

bool find(pair<int, int> p) {
  if (p.first > 5000 || p.second > 5000 || p.first < 0 || p.second < 0) {
    return false;
  }
  else {
    return G.at(p.first).at(p.second);
  }
}

int main() {
  int N;
  cin >> N;
  vector<pair<ll, ll>> xys(N);
  
  rep(i, 0, N) {
    int x, y;
    cin >> x >> y;
    pair<int, int> xy;
    xy.first = x;
    xy.second = y;
    xys.at(i) = xy;
    G.at(x).at(y) = true;
  }
  
  ll ans = 0;
  rep(i, 0, N - 1) {
    rep(j, i + 1, N) {
      ll ax, ay, bx, by, dx, dy;
      ax = xys.at(i).first;
      ay = xys.at(i).second;
      bx = xys.at(j).first;
      by = xys.at(j).second;
      dx = bx - ax;
      dy = by - ay;
      
      pair<ll, ll> C, D, E, F;
      C.first = ax + dy;
      C.second = ax - dx;
      
      D.first = ax + dx + dy;
      D.second = ay + dy - dx;
      
      E.first = ax - dy;
      E.second = ay + dx;
      
      F.first = ax + dx - dy;
      F.second = ay + dx + dy;
      
      if ((find(C) && find(D)) || (find(E) && find(F))) {
        chmax(ans, dx * dx + dy * dy);                  
      }
    }
  }
  cout << ans << endl;
}

8　Square869120Contest #6 B - AtCoder Markets

「移動時間が最小となるような入口と出口のマスは、マス 1,2,3,...,100 のどれかであるはず」という直感に基づいて組み合わせを全探索したら奇跡的にACした。証明はできていない。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define repeq(i, a, b) for (ll i = a; i <= b; i++)
#define rrep(i, b, a) for (ll i = b; i >= a; i--)
#define repb(i, n) for (ll 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() {
  ll N;
  cin >> N;
  vector<ll> A(N), B(N);
  set<int> S;
  rep(i, 0, N) {
    cin >> A.at(i) >> B.at(i);
    S.insert(A.at(i));
    S.insert(B.at(i));
  }
  
  ll ans = inf;
  fore(s1, S) {
    fore(s2, S) {
      ll tmp = 0;
      rep(i, 0, N) {
        ll tmp1 = abs(s1 - A.at(i)) + abs(A.at(i) - B.at(i)) + abs(B.at(i) - s2);
        ll tmp2 = abs(s1 - B.at(i)) + abs(B.at(i) - A.at(i)) + abs(A.at(i) - s2);
        tmp += min(tmp1, tmp2);
      }
      ans = min(ans, tmp);
    }
  }
  cout << ans;
}

9　JOI 2008 予選 4 - 星座探し

探したい星座の座標を、ある点からの差分で保持しておいて、愚直に全探索した。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define repeq(i, a, b) for (ll i = a; i <= b; i++)
#define rrep(i, b, a) for (ll i = b; i >= a; i--)
#define repb(i, n) for (ll 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() {
  ll m;
  cin >> m;
  vector<ll> x1(m), y1(m), dif_x(m), dif_y(m);
  rep(i, 0, m) {
    cin >> x1.at(i) >> y1.at(i);
    dif_x.at(i) = x1.at(i) - x1.at(0);
    dif_y.at(i) = y1.at(i) - y1.at(0);
  }
  
  ll n;
  cin >> n;
  vector<ll> x2(n), y2(n);
  set<pair<ll, ll>> S;
  rep(i, 0, n) {
    cin >> x2.at(i) >> y2.at(i);
    pair<ll, ll> P = make_pair(x2.at(i), y2.at(i));
    S.insert(P);
  }
  
  rep(i, 0, n) {
    bool is_break = false;
    rep(j, 0, m) {
      ll tmp_x = x2.at(i) + dif_x.at(j);
      ll tmp_y = y2.at(i) + dif_y.at(j);
      pair<ll, ll> tmp = make_pair(tmp_x, tmp_y);
      if (!S.count(tmp)) {
        is_break = true;
        break;
      }
    }
    if (!is_break) cout << x2.at(i) - x1.at(0) << " " << y2.at(i) - y1.at(0) << endl;
  }
}