Codeforces Round #462 (Div. 2)
今回は恥ずかしながら0完です.
A - Compatible Pair
両者のランタンから最大になりうる組み合わせをいくつか持ってきて比較, 最大になる
組み合わせに含まれるLittle Tommy側の要素をマスクしてもう一度比較, といった
感じでコンテスト中(とその後)に考えて書いたコードが以下.
#include <bits/stdc++.h> using namespace std; int main(void) { int n, m; cin >> n >> m; vector<int> a, b; for(int i = 0; i < n; i++) { int x; cin >> x; a.push_back(x); } for(int i = 0; i < m; i++) { int x; cin >> x; b.push_back(x); } sort(a.begin(), a.end()); sort(b.begin(), b.end()); long long int l = b[0] * a[0]; long long int r = b[m - 1] * a[n - 1]; long long int s = b[0] * a[n - 1]; long long int u = b[m - 1] * a[0]; if(s < 0 && u < 0) { if(l > r) { long long int ll = b[0] * a[1]; long long int rr = r; cout << max(ll, rr) << endl; } else if(l == r) { cout << l << endl; } else { long long int ll = l; long long int rr = b[m - 1] * a[n - 2]; cout << max(ll, rr) << endl; } } else { if(s > u) { long long int ss = b[0] * a[n - 2]; long long int uu = u; cout << max(ss, uu) << endl; } else if(s == u) { cout << s << endl; } else { long long int ss = s; long long int uu = b[m - 1] * a[1]; cout << max(ss, uu) << endl; } } return 0; }
が, これはWAだった.
Editorialで2 <= n, m <= 50なので全探索でよいと知ってズッコけた.
入力のサイズはよく確認しよう.
以下, Editorial見ながら書いたコード.
Little Tommyのランタンa[i]をマスクした場合のランタンの積の最大値nowを求める.
iを動かした場合の最小のnowが答え.
#include <bits/stdc++.h> using namespace std; int main(void) { int n, m; cin >> n >> m; int a[n], b[m]; for(int i = 0; i < n; i++) { cin >> a[i]; } for(int i = 0; i < m; i++) { cin >> b[i]; } long long res = LLONG_MAX; for(int i = 0; i < n; i++) { long long now = LLONG_MIN; for(int j = 0; j < n; j++) { if(j != i) { for(int k = 0; k < m; k++) { now = max(now, (long long)a[j]*b[k]); } } } res = min(res, now); } cout << res << endl; }
B - A Prosperous Lot
kが2以上なら"8"を出力してkを2減らす.
kが1なら"6"を出力してkを1減らす.
kが0なら終了.
kが36より大きい場合, 答えが10^18より大きくなるので"-1"を出力.
コンテスト中は10^18を18ケタと勘違いし(本当は19ケタ),
"-1"の条件をk > 34としてしまった.
あとkが1の場合の出力を"0"にしていたので入力が1だとWAになった.
問題文のOutputのpositiveが太字になってるの多分これのこと.
// 10^18は19ケタ #include <bits/stdc++.h> using namespace std; int main(void) { int k; cin >> k; if(k > 36) { cout << "-1" << endl; return 0; } while(true) { if(k >= 2) { cout << "8"; k -= 2; } else if(k == 1) { cout << "6"; k -= 1; } else { break; } } cout << endl; return 0; }