AtCoder abc396 参加記

AtCoder Beginner Contest 396 - AtCoder

A - Triple Four

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)

int main() {
  int n; cin >> n;
  vector<int> a(n);
  int ok = 0;
  REP(i,n) cin >> a[i];
  REP(i,n-2) ok |= (a[i] == a[i+1] && a[i] == a[i+2]);
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

B - Card Pile

後入先出(LIFO) で管理すればよいので stack でカードの山を管理する

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int q; cin >> q;
  vector<int> d(100);
  REP(i,q) {
    int t; cin >> t;
    if (t == 1) { int x; cin >> x; d.push_back(x); }
    if (t == 2) { cout << d.back() << endl; d.pop_back(); }
  }
  return 0;
}

C - Buy Balls

黒色のボールの個数を固定したときに、白色のボールをどれだけ取るといいかを考える。 価値の大きいボールから順に取るのが最良のため、価値の大きいものから順に取っていく。 白色は黒色の個数以下で、価値が正のものを取れるだけ取ればいい

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;

int main() {
  int n,m; cin >> n >> m;
  vector<int> b(n),w(m);
  REP(i,n) cin >> b[i];
  REP(i,m) cin >> w[i];
  REP(i,n-m) w.push_back(0);
  sort(b.rbegin(),b.rend());
  sort(w.rbegin(),w.rend());

  ll ans = 0, now = 0;
  REP(i,n) {
    now += b[i] + max(0,w[i]);
    ans = max(ans,now);
  }
  cout << ans << endl;
  return 0;
}

D - Minimum XOR Path

N <= 10 と小さいことから、1からNまでのパスを全探索できる

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;
using P = pair<int,ll>;
const ll LINF = numeric_limits<ll>::max();

int main() {
  int n,m; cin >> n >> m;
  vector g(n,vector<P>());
  REP(i,m) {
    int u,v; ll w; cin >> u >> v >> w; u--; v--;
    g[u].emplace_back(v,w);
    g[v].emplace_back(u,w);
  }

  vector<bool> visited(n);
  auto dfs = [&](auto& dfs, int i, ll cur) -> ll {
    if (i == n-1) return cur;

    ll res = LINF;
    for(auto [ni,w]: g[i]) if (!visited[ni]) {
      visited[ni] = true;
      res = min(res,dfs(dfs,ni,cur^w));
      visited[ni] = false;
    }
    return res;
  };

  visited[0] = true;
  cout << dfs(dfs,0,0) << endl;
  return 0;
}

E - Min of Restricted Sum

頂点 Xi, Yi を Zi 値を持つ辺で結ぶグラフとして考える。 スタートする点の値を 0 として、連結成分ごとに BFS で Axi ^ Ayi = Zi に矛盾がないかを調べる。 矛盾がなければ総和が最小となる数を見つける。これは各ビットごとに見ていき、1 の数が半数より多い場合は反転させればよい。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;

int main() {
  int n,m; cin >> n >> m;
  vector g(n,vector<pair<int,int>>());
  REP(i,m) {
    int x,y,z; cin >> x >> y >> z; x--; y--;
    g[x].emplace_back(y,z);
    g[y].emplace_back(x,z);
  }

  vector<ll> ans(n);
  vector<bool> visited(n);
  auto bfs = [&](int start) -> bool {
    queue<int> q;
    vector<int> comp;

    auto push = [&](int v) {
      q.push(v);
      comp.push_back(v);
      visited[v] = true;
    };

    push(start);
    while(q.size()) {
      int from = q.front(); q.pop();
      for (auto [to,z]: g[from]) {
        if (visited[to]) {
          if ((ans[from] ^ ans[to]) != z) return false;
        } else {
          ans[to] = ans[from] ^ z;
          push(to);
        }
      }
    }

    ll t = 0;
    REP(bit,31) {
      int one = 0;
      for (auto v: comp) one += (ans[v] >> bit) & 1;
      if (one > (int)comp.size() - one) t |= (1LL << bit);
    }
    for (auto v: comp) ans[v] ^= t;
    return true;
  };

  REP(i,n) if (!visited[i] && !bfs(i)) { cout << -1 << endl; return 0; }
  for(auto v: ans) cout << v << " ";
  return 0;
}

F - Rotated Inversions

まず BIT で k = 0 のときの転倒数を求めておく。 転倒数に変化が起こるのは、 (a[i] + k) % m == 0 となるときのみなので、差分を計算できないか考える。 (a[i] + k) % m == 0 となるときに寄与する転倒数は、増える分が i, 減る分が n-i-1 なのでこれをイベントとして持っておく。 あとは k = 1 から k = m-1 までに発生するイベントを処理しながら答えを求めていけばよい。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;

int main() {
  int n,m; cin >> n >> m;
  vector<int> a(n);
  REP(i,n) cin >> a[i];

  vector<ll> ans(m);
  fenwick_tree<int> fw(m);
  // k = 0 のときの転倒数を fenwich tree で求める
  REP(i,n) {
    ans[0] += i - fw.sum(0,a[i]+1);
    fw.add(a[i],1);
  }

  vector events(m,vector<ll>());
  REP(i,n) if (a[i] > 0) {
    // m-1 -> m となるとき(時刻t = m-a[i])に転倒数にどれだけ寄与するか
    // 増える転倒数 i
    // 減る転倒数 n-i-1
    events[m-a[i]].push_back(i-(n-i-1));
  }

  ll now = ans[0];
  for (int k = 1; k < m; k++){
    for (auto v : events[k]) now += v;
    ans[k] = now;
  }
  for(auto v: ans) cout << v << endl;
  return 0;
}

雑感

辛い戦いだ...

tic40さんのAtCoder Beginner Contest 396での成績:950位
パフォーマンス:1591相当
レーティング:1247→1286 (+39) :)
#AtCoder #ABC396 https://atcoder.jp/users/tic40/history/share/abc396?lang=ja