はじめに
今回は工夫全列挙問題を5問やっていきます！
精選100問はこちら
5 AtCoder Beginner Contest 095 C - Half and Half
問題はこちらです
問題文↓
A、B、ABの3つのピザがある ABはAとBの半分を合わせたもので、AB2つ買うとA1つとB1つにできる A、B、ABの3つのピザの値段と、欲しいAとBのピザの個数が与えられるので、一番安くなる方法で買ったときの値段を出力せよ
ABに対していくつ買うかを考えると、A、Bそれぞれの買う個数は決まり、
ABの制約が5000以下であることからABの個数でループさせたら良い！
結果として次のコードになる
#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 a, b, c, x, y; cin >> a >> b >> c >> x >> y; // 結果変数. int ans = INT32_MAX; for (int i = 0; i <= max(x, y); i++) { // i個買うABの値段. int priceAB = i * c * 2; // 残りすべてのAとBをそのまま買う値段. int priceA = max(0, x - i) * a; int priceB = max(0, y - i) * b; ans = min(ans, priceAB + priceA + priceB); } // 結果出力. cout << ans << endl; return 0; }
6 三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN
問題はこちらです
問題文↓
ある文字列Sが与えられる Sの中の文字を長さが3になるまで消していく そこで、3文字の長さのSをパスワードにしたい さて、何種類のパスワードが作成できるか ただし、Sの長さは最大300000で大きい
一見Sのa番目・b番目・c番目と取り出したいが、それではO(N³)かかり間に合わない！
そこで、パスワードの長さに注目すると、000～999までの1000通りなので、これがすべて作成できるかを探索していけばいい
これだと、1000×N回の計算量で解くことが出来る！
結果として、以下のようになった
#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; string s; cin >> n >> s; int ans = 0; rep(i, 1000) { // stringstreamで0埋めを実行し文字列化. stringstream ss; ss << setw(3) << setfill('0') << i; string subS = ss.str(); // 数字は作れるか. int scene = 0; rep(j, n) { if (scene == 0 && s[j] == subS[0]) { scene++; } else if (scene == 1 && s[j] == subS[1]) { scene++; } else if (scene == 2 && s[j] == subS[2]) { scene++; } } // 数字は作れるか. if (scene == 3) ans++; } cout << ans << endl; return 0; }
7 JOI 2007 本選 3 - 最古の遺跡
問題はこちらです
問題文↓
遺跡にはいくつかの柱がある 柱を結んで正方形になるかを求め、作成可能な正方形の面積の最大値を求めてください
普通に考えると、O(N⁴)と遅くなる！
このとき、制約は5000以下なので、一般的なコンピュータでも「5000⁴/1e9/3600/24=7.2」なので、約7日間かかる
次に考えると、1つの点がなくても四角形は組み立てられるので、O(N³)に抑えられるが、これでも「5000³/1e9/60=2.08」なので、約2分かかる
更に考えると、作成したい図形は正方形なので頂点が2つあれば、作成することが可能！
よって、O(N²)で「5000²/1e9=0.025」となり、約25msで解くことが可能になる
つまり、ここでの全探索は2つの頂点の組み合わせということになる
結果として、以下のコードになった
#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() { ll n; cin >> n; vector<vector<bool>> M(6000, vector<bool>(6000, false)); vector<pair<ll, ll>> P; rep(i, n) { ll x, y; cin >> x >> y; M[y][x] = true; P.push_back(pair(y, x)); } ll ans = 0; rep(i, n) { rep(j, n - i - 1) { // 2つの点が決まると、正方形を書くことが可能. pair<ll, ll> p1 = P[i], p2 = P[j + i + 1], p3, p4; p3.first = p1.first + (p2.second - p1.second); p3.second = p1.second + (p1.first - p2.first); p4.first = p2.first + (p2.second - p1.second); p4.second = p2.second + (p1.first - p2.first); // マップからはみ出していないのなら. if (p3.first >= 0 && p3.first <= 5500 && p3.second >= 0 && p3.second <= 5500 && p4.first >= 0 && p4.first <= 5500 && p4.second >= 0 && p4.second <= 5500) { // 作成した2つの点の上に柱が存在すれば. if (M[p3.first][p3.second] && M[p4.first][p4.second]) { ans = max(ans, (p2.second - p1.second) * (p2.second - p1.second) + (p1.first - p2.first) * (p1.first - p2.first)); } } } } cout << ans << endl; return 0; }
8 Square869120Contest #6 B - AtCoder Markets
問題はこちらです
問題文↓
数直線があって、人がa_iからb_iまで行きたがっている 全員の行きたい場所までにかかる距離が最小になるように入口と出口をつけてあげてください ただし、a・bは10⁹程度あり、これを全探索するのは不可能です
a・bで全探索できたら簡単にAC取れるけど、そうはいきません
では、入力例1を考えてみます
3 5 7 2 6 8 10
入口を5、出口を7にすると、
客1:(5-5)+(7-5)+(7-7)=2移動しなきゃだめ
客2:(5-2)+(6-2)+(7-6)=8移動しなきゃだめ
客3:(8-5)+(10-8)+(10-7)=8移動しなきゃだめ
足すと18移動することになります
これを、文字的に見て、入口をs、出口をgとすると、|s-a|+|b-a|+|g-b|となる
これを客ごとに分解して考えると、
①|s-a₁|+|s-a₂|+|s-a₃|+...+|s-aₙ|
②|b₁-a₁|+|b₂-a₂|+|b₃-a₃|+...+|bₙ-aₙ|
③|g-b₁|+|g-b₂|+|g-b₃|+...+|g-bₙ|
②の式はs,gによって変わることがないので、簡単に求めることが出来る
しかし、①と③はs,gによって変わるので最適な値を出すのが難しい！
でも実は、①の式の最小値は、sがaの中央値、gがbの中央値になるらしいです
"らしい"ということで思いつかなかったということですね
(けんちょんさんの記事がわかりやすい！)
ていうことで実装は以下のようになりました
#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() { ll n; cin >> n; vector<ll> A(n), B(n); rep(i, n) cin >> A[i] >> B[i]; // ②の式の値を求める. ll ans = 0; rep(i, n) { ans += abs(B[i] - A[i]); } // ①と③の式の値を求める. sort(all(A)); sort(all(B)); ll s = A[(A.size() - 1) / 2]; ll g = B[(B.size() - 1) / 2]; rep(i, n) { ans += abs(s - A[i]); } rep(i, n) { ans += abs(g - B[i]); } cout << ans << endl; return 0; }
難しい、、、
9 JOI 2008 予選 4 - 星座探し
問題はこちらです
問題文↓
現在の星空と、星座に含まれる星の座標が与えられる 星座の座標からxとy座標をいくつ平行移動させれば現在の星空の星座と重ねることができるか ただし、星座は現在の星空に1つしか存在しないとする
時間制限が10secかつn<1000、m<200なので現在の星座の星を全探索すれば良い！
すべての星を探索・星座の星を探索・星が存在するかの探索でO(mn²)でクリアできるので、最大10002*200/1e9=0.2秒=200ms程度でクリアできる
結果として以下のコードになる
#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 m; cin >> m; // 星座の取得. vector<pair<ll, ll>> S(m); rep(i, m) cin >> S[i].first >> S[i].second; // 星空の取得. int n; cin >> n; vector<pair<ll, ll>> P(n); rep(i, n) cin >> P[i].first >> P[i].second; // ソートする. sort(all(S)); sort(all(P)); // 星座の間隔. vector<pair<ll, ll>> M; pair<ll, ll> c = S[0]; rep(i, m - 1) { M.push_back(pair(S[i + 1].first - c.first, S[i + 1].second - c.second)); } // 現在の星空の全探索. rep(i, n) { // 基準の星. pair<ll, ll> s = P[i]; ll hitCount = 0; rep(j, m - 1) { // 星aが存在するか. ll ax = s.first + M[j].first; ll ay = s.second + M[j].second; rep(k, n) { if (P[k].first == ax && P[k].second == ay) { hitCount++; } } // 全部hitだったら. if (hitCount == m - 1) { cout << P[i].first - S[0].first << " " << P[i].second - S[0].second << endl; } } } return 0; }
全探索の典型なので、実装力が求められる問題でした
また、二分探索をしたら星の存在の探索がO(n)→O(log n)となるので、O(mn²)→O(mn log n)になり2ms程度でクリア出来るらしいです！
終わりに
約10分の1終了！
では、また来週！
