日々精進

aikoと旅行とプログラミング

AtCoder Beginner Contest #62

問題はこちらから.

abc062.contest.atcoder.jp

問題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, greater>とかなのだろうか)