ABC002 + ARC073

ABC002 C問題


C: 直訴 - AtCoder Beginner Contest 002 | AtCoder

これは解き方を知らなければ、四角で三角を囲って周りにできた4つの三角の面積を四角から引くという面倒くさい事をしなければならない問題だがググればすぐにでてくる
解いてる途中は気づかなかったがご丁寧にヒントまで書いてあった

ヒント
3 点 (0,0), (a,b), (c,d) で構成される三角形の面積は、|ad−bc|⁄2 となります。

つまり一つの頂点を (0, 0) までもってきてその差分を他の点からも引けば良い
しかし問題はそこではなくデフォルトの出力フォーマットでは求める出力ができない点にある

#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() {
  double x, y, x2, y2, x3, y3;
  cin >> x >> y >> x2 >> y2 >> x3 >> y3;
 
  cout << fixed << fabs(((x2 - x) * (y3 - y)) - ((x3 - x) * (y2 - y))) / 2 << endl;
}

ABC002 D問題


D: Widespread - AtCoder Regular Contest 075 | AtCoderD: 派閥 - AtCoder Beginner Contest 002 | AtCoder


一見難しそうな問題文ではあるが入力がすごく小さいので全探索でどうにかなる
一人目から順番に派閥に入れるか入れないかの分岐を行い、入れる場合はすでに派閥に入っている人間と知り合いであるかを探索する

#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 n, m, max_s = 0;
vector<vector<int> > kan(13, vector<int>(13));
 
int saiki(int i, vector<int> hi) {
  if(i == n) {
    max_s = max(max_s, (int)hi.size());
    return 0;
  }
  saiki(i + 1, hi);
  rep(j, 0, hi.size()) if(!kan[i][hi[j]]) return 0;
  hi.pb(i);
  saiki(i + 1, hi);
}
 
int main() {
  cin >> n >> m;
  int a, b;
 
  if(m == 0) {
    cout << 1 << endl;
    return 0;
  }
 
  rep(i, 0, m) {
    cin >> a >> b;
    kan[a - 1][b - 1] = 1;
    kan[b - 1][a - 1] = 1;
  }
 
  vector<int> hi;
  saiki(0, hi);
  cout << max_s << endl;
}

ARC075 C問題

C: Sentou - AtCoder Regular Contest 073 | AtCoder

前回スイッチを押した時間(x)とお湯が出た時間(y)を覚えておいて、x + お湯が出続ける時間(t) を次のスイッチを押した時間と比較し、小さければその差が得られる予定だったお湯の量なのでその値を y から引く
その後 y に t をプラスする

#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, t, a, z = 0, ans;
  cin >> n >> t >> a;
  ans = t;
  rep(i, 1, n) {
    cin >> a;
    if(z + t > a) ans -= z + t - a;
    ans += t;
    z = a;
  }
  cout << ans << endl;
}

ARC075 D問題

D: Simple Knapsack - AtCoder Regular Contest 073 | AtCoder

超有名問題なので説明は省略
しかしネット情報を鵜呑みにすると w の上限が10 ^ 9 なので二次元配列が確保できないところにひっかかる
今回の場合は連想配列を用いる事でこの問題を回避できる

#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 n, w, mono[100][2];
map<int, int> memo[100];

int saiki(int i, int cost) {
  if(cost > w) return -10000000;
  if(i == n) return 0;
  if(memo[i].count(cost)) return memo[i][cost];
  return memo[i][cost] = max(saiki(i + 1, cost + mono[i][0]) + mono[i][1], saiki(i + 1, cost));
}

int main() {
  cin >> n >> w;
  rep(i, 0, n) {
    cin >> mono[i][0] >> mono[i][1];
  }

  cout << saiki(0, 0) << endl;
}

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;
}

ARC075

C問題


C: Bugged - AtCoder Regular Contest 075 | AtCoder


10の倍数にならない状態での最大の値を求められているので、10の倍数で無い最小の値を確保しておいて全てを足した際に10の倍数であれば確保してある値を引くだけで答えが出る


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

int main() {
  int n, a, ans = 0, min = 101;
  cin >> n;

  for(int i = 0; i < n; i++) {
    cin >> a;
    ans += a;
    if(min > a && a % 10 != 0) min = a;
  }

  cout << (ans % 10 == 0 ? min > 100 ? 0 : ans - min : ans) << endl;
}

D問題


D: Widespread - AtCoder Regular Contest 075 | AtCoder


全探索だと枝刈りを頑張っても無理だったので爆発回数 A 回で全滅させられる場合、 A ≦ B の条件を満たした B は全滅させることが可能な爆発回数という性質を利用し、二分探索で計算量を削減する

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

ll n, a, b, ans, h[100001];

bool taosu(ll k) {
  ll cost = 0;
  rep(i, 0, n) {
    ll z = h[i] - b * k;
    if(z > 0) {
      cost += ceil((double)z / (double)(a - b));
      if(cost > k) return false;
    }
  }
  return true;
}

int main() {
  cin >> n >> a >> b;
  rep(i, 0, n) cin >> h[i];
  ll left = 0, right = 1000000000, mid, ans;
  while(left <= right) {
    mid = (left + right) / 2;
    taosu(mid) ? ans = mid, right = --mid : left = ++mid;
  }
  cout << ans << endl;
}