AtCoder Beginner Contest #62
問題はこちらから.
問題A: Grouping
#include <iostream> using namespace std; int main() { int x, y; int groups[] = {0, 1, 2, 1, 3, 1, 3, 1, 1, 3, 1, 3, 1}; cin >> x >> y; cout << (groups[x] == groups[y]?"Yes":"No") << endl; }
問題B: Picture Frame
#include <iostream> using namespace std; int main() { int h, w; cin >> h >> w; for(int j = 0 ; j < w + 2 ; j++) cout << "#"; cout << "\n"; for(int i = 0 ; i < h ; i++){ string s; cin >> s; cout << "#" << s << "#" << endl; } for(int j = 0 ; j < w + 2 ; j++) cout << "#"; cout << "\n"; }
問題C: Chocolate Bar
4種類分け方があるので, それを全部試す.
#include <iostream> using namespace std; #define int long long signed main() { int h, w; long long ans = 1e11; cin >> h >> w; for(int h1 = 1 ; h1 <= h ; h1++){ int area1 = h1 * w; int h2 = (h - h1)/2; int area2 = h2 * w; int area3 = (h-h1-h2) * w; int _min = min(area1, min(area2, area3)); int _max = max(area1, max(area2, area3)); ans = min(ans, _max - _min); int w2 = w/2; area2 = (h - h1) * w2; area3 = (h - h1) * (w - w2); _min = min(area1, min(area2, area3)); _max = max(area1, max(area2, area3)); ans = min(ans, _max - _min); } swap(w, h); for(int h1 = 1 ; h1 <= h ; h1++){ int area1 = h1 * w; int h2 = (h - h1)/2; int area2 = h2 * w; int area3 = (h-h1-h2) * w; int _min = min(area1, min(area2, area3)); int _max = max(area1, max(area2, area3)); ans = min(ans, _max - _min); int w2 = w/2; area2 = (h - h1) * w2; area3 = (h - h1) * (w - w2); _min = min(area1, min(area2, area3)); _max = max(area1, max(area2, area3)); ans = min(ans, _max - _min); } cout << ans << endl; }
問題D: 3N Numbers
どうやったらいいかわからず解説見ながら解いた(それでも最初わからないのでダメ)
#include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) using namespace std; typedef long long ll; signed main(){ int n; int data[300001]; ll s1[300001] = {0}; ll s2[300001] = {0}; scanf("%d", &n); REP(i, 1, 3 * n + 1) scanf("%d", data+i); priority_queue<int> q; REP(i, 1, n+1){ q.push(-data[i]); s1[n]+= data[i]; } REP(i, n+1, 2 * n + 1){ s1[i] = s1[i-1]; q.push(-data[i]); s1[i] += data[i]; int _min = q.top(); s1[i] += _min; q.pop(); } priority_queue<int> q2; for(int i = 3 * n ; i > 2 * n ; i--){ q2.push(data[i]); s2[2*n+1] += data[i]; } for(int i = 2 * n ; i > n ; i--){ s2[i] = s2[i+1]; q2.push(data[i]); s2[i] += data[i]; int _max = q2.top(); s2[i] -= _max; q2.pop(); } ll _max = numeric_limits<ll>::min(); REP(i, n, 2*n+1){ _max = max(_max, s1[i] - s2[i+1]); } printf("%lld\n", _max); }
最後のmaxを取るところ, 添字ずれるのに気づいておらず, ずっとmax(ans, s1[i]-s2[i])で計算していて悩んだ. max(ans, s1[i] - s1[i + 1])ですね.
ところでpriority_queueって最小ヒープどうやるんだろう. いまのところ負にすることで対応しているが…(std::priority_queue<int, vector