ARC 074

C問題


C: Chocolate Bar - AtCoder Regular Contest 074 | AtCoder


H か W が3で割って余りが出ないのであれば、その軸を横にして縦に等間隔で割れるので 0
それ以外の場合でまず縦と横、両方に割った方が良い場合は単純に全探索してしまうと O(n^2) で TLE になってしまうので工夫が必要
今回のようにピースの3つの差をなるべく縮めたい前提だと、2つのピースのみに影響を与える辺の位置は常に同じ値(x / 2)を保つので、残りの断面について探索するだけで答えが出るので H と W を入れ替えた分も合わせ O(2n) で解ける
全て同じ方向に割ったほうが良い場合は余りが一列(それ以上の場合は縦と横に割ったほうが良い)なので H と W の小さい方が答えとなる

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
 
__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}
 
ll k(ll h, ll w) {
  ll mini = min(h, w);
  for(ll i = 0; i < h; i++) {
    ll a = max(i * w, (h - i) * (w / 2 + (w % 2 ? 1 : 0))) - min(i * w, (h - i) * (w / 2));
    mini = min(mini, a);
  }
  return mini;
}
 
int main() {
  ll h, w;
  cin >> h >> w;
 
  if(h % 3 == 0 || w % 3 == 0) {
    cout << 0 << endl;
    return 0;
  }
 
  cout << min(k(h, w), k(w, h)) << endl;
}

D問題


D: 3N Numbers - AtCoder Regular Contest 074 | AtCoder


どうしても分からず解説を見てしまったが PriorityQueue(以下 PQ) の存在をあまり認知していなかったので見て正解だった
この問題はN個の要素を削除するという問題だがようするに真ん中のN個をどちらがどこまで取るかという問題であった
ロジック自体はかなり簡単で、PQ を利用して左から N + 1個を確保したことにして最小値を省く、次にN + 2個を...という処理を行う
愚直にやれば当然 TLE だが PQ 利用することで少ない計算量で最小値を省ける
これを逆側から、今度は最大値を取るようにすれば真ん中 N + 1 個分の境界線に左側の最大値、右側の最小値が出てくるので 左 - 右 で最も数字の大きいものが答えとなる

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

typedef long long ll;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  ll n, m, lv = 0, rv = 0, a[100001], ans[100001] = {};
  priority_queue <ll, vector<ll>, greater<ll> > pq1;
  priority_queue <ll> pq2;
  cin >> n;

  rep(i, 0, n) cin >> m, lv += m, pq1.push(m);
  rep(i, 0, n) cin >> a[i];
  rep(i, 0, n) cin >> m, rv += m, pq2.push(m);

  rep(i, 0, n) {
    ans[i] = lv;
    lv += a[i];
    pq1.push(a[i]);
    lv -= pq1.top();
    pq1.pop();
  }

  ans[n] = lv - rv;

  dep(i, n - 1, 0) {
    rv += a[i];
    pq2.push(a[i]);
    rv -= pq2.top();
    pq2.pop();
    ans[i] -= rv;
  }

  ll ma = -100000000000000;
  rep(i, 0, n + 1) {
    ma = max(ma, ans[i]);
  }
  cout << ma << endl;
}