AtCoder Grand Contest 017 - ei1333の日記

80位. 2382->2421(+39).

橙ーー pic.twitter.com/zlCfCaJaHa
— うし (@ei1333) 2017年7月9日

レート遷移だけ見ると実力がついている気がしてうれしい(実際は怪しい).

AGC, 良い時と悪い時の差がはげしい….(AGCは考察がマッチするかどうかだからなぁ

A - Biscuits

agc017.contest.atcoder.jp

解法

難しすぎるため飛ばした.

思考停止をすると, 偶数を何個使うか, 奇数を何個使うかを決め打ちして組み合わせになげればよいことがわかる.

ソース

パスカルの三角形のライブラリが欲しい.

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
 
int main()
{
  int N, A[2] = {}, P;
 
  cin >> N >> P;
  for(int i = 0; i < N; i++) {
    int X;
    cin >> X;
    ++A[X % 2];
  }
 
  int64 mat[55][55] = {{}};
  for(int i = 0; i < 52; i++) {
    for(int j = 0; j <= i; j++) {
      if((j == 0) || (j == i)) {
        mat[i][j] = 1;
      } else {
        mat[i][j] = mat[i - 1][j - 1] + mat[i - 1][j];
      }
    }
  }
 
  int64 ret = 0;
  for(int i = 0; i <= A[0]; i++) {
    for(int j = 0; j <= A[1]; j++) {
      int mod = (i * 2 + j) % 2;
      if(mod == P) {
        ret += mat[A[0]][i] * mat[A[1]][j];
      }
    }
  }
  cout << ret << endl;
}

B - Moderate Differences

agc017.contest.atcoder.jp

解法

難しすぎるため飛ばした.

制約を見ると ${O(N)}$ の雰囲気が漂っているので, その方針で考える.

それぞれの隣接する要素の差は正であるか負であるかのどちらか. これは要素を入れ替えることにより, 最初に正を ${x}$ 回, 次に負を ${(N-x-1)}$ 回とみなしてもよい.

ここで ${x}$ 回正をする操作は ${[Cx, Dx]}$ の範囲の値の加算とみなせる.

また ${(N-x-1)}$ 回の負は ${[D(N-x-1), C(N-x-1)]}$ の範囲のいずれの値の減算とみなせる.

これらをあわせるとえい.

ソース

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
 
int main()
{
  int64 N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
 
  B -= A;
  A -= A;
 
  for(int i = 0; i < N; i++) {
    int64 small1 = C * i;
    int64 large1 = D * i;
    int64 small2 = C * (N - i - 1);
    int64 large2 = D * (N - i - 1);
    if(small1 - large2 <= B && B <= large1 - small2) {
      cout << "YES" << endl;
      return (0);
    }
  }
  cout << "NO" << endl;
}

C - Snuke and Spells

agc017.contest.atcoder.jp

解法

部分点があるし部分点からかなぁって思っていて ${40}$ 分くらい考えたけどわからなかった. 一問も解けない(コンテスト終了). この問題も飛ばす.

本番では部分点を得た.

そのままだと変更の条件が複雑で険しいので, 簡単な形に言い換えたい気持ちになる.

みたいな順番に並んでいるものは OK.

次に

も OK.

これらをぐっと睨むと, 後ろから見て値が変化したところを見たときに ${A_i = i}$ なら OK ということがわかり, これは正しそう.

ここで値 ${i}$ の個数を ${B_i}$ とする.

このような列にするための変更の最小回数は, 後ろから見て ( ${B_i}$ ) と ( ${i}$ より大きい値で ${B_j}$ の最大の個数みたいなの(伝わって)) の max を取りながら走査するとわかる(ソースコード見たほうがわかりやすそう).

満点解について.

要するに最小回数は区間 ${[1, N]}$ で, どの区間 ${(i-B_i, i]}$ にも覆われていない要素の個数である. 変更クエリでは, ある区間を ${1}$ 個縮めて, ある区間を ${1}$ 個伸ばす操作を行えば良くて, これはそれぞれの要素について何個の区間で覆われているかを持っていればできるためはい.

部分点ソース

#include<cstdio>
#include<algorithm>
 
using namespace std;
 
int main()
{
  int N, M, A[200000], B[200000] = {};
 
  scanf("%d %d", &N, &M);
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    --A[i];
    B[A[i]]++;
  }
 
 
  for(int i = 0; i < M; i++) {
    int X, Y;
    scanf("%d %d", &X, &Y);
    --X, --Y;
 
    --B[A[X]];
    A[X] = Y;
    ++B[A[X]];
 
    int val = 0, ret = 0;
    for(int j = N - 1; j >= 0; j--) {
      val = max(val, B[j]) - 1;
      if(val < 0) ++ret;
 
    }
 
    printf("%d\n", ret);
  }
}

満点ソース

#include <bits/stdc++.h>
 
using namespace std;
 
int cover[500005];
const int SHIFT = 200005;
 
void add(int k, int x)
{
  cover[k + SHIFT] += x;
}
 
int query(int k)
{
  return (cover[k + SHIFT]);
}
 
int main()
{
  int N, M, A[200000], B[200000] = {};
  scanf("%d %d", &N, &M);
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    --A[i];
    B[A[i]]++;
  }
 
  for(int j = 0; j < N; j++) {
    --B[j];
    int sz = j - B[j];
    add(sz, 1);
    add(j + 1, -1);
  }
  for(int j = 1; j < 500005; j++) {
    cover[j] += cover[j - 1];
  }
  int ret = 0;
  for(int j = 0; j < N; j++) {
    if(query(j) <= 0) ++ret;
  }
  
  for(int i = 0; i < M; i++) {
    int X, Y;
    scanf("%d %d", &X, &Y);
    --X, --Y;
    add(A[X] - B[A[X]], -1);
    if(A[X] - B[A[X]] >= 0 && query(A[X] - B[A[X]]) == 0) {
      ++ret;
    }
    --B[A[X]];
    A[X] = Y;
    ++B[A[X]];
    add(A[X] - B[A[X]], 1);
    if(A[X] - B[A[X]] >= 0 && query(A[X] - B[A[X]]) == 1) {
      --ret;
    }
 
    printf("%d\n", ret);
  }
}

D - Game on Tree

agc017.contest.atcoder.jp

解法

わからない問題が 3 問続いてついに 4 問目まで来てしまった. 悲しいね.

3 分で解けてる人がいるので絶対知識ゲーだと信じて読むけど, 僕の知識辞書にはなかった(ア

ぱっと見は grundy数で, すごく考えると上手く行きそうなことがわかる(これ難しくないですか

まず子頂点のみの場合は負けなので grundy 数は 0. 子頂点がある場合は, (それぞれの子頂点のgrundy数+1) の XOR をとったものとなることがわかる.

grundy数の定義より子頂点のgrundy数を ${x}$ とすると子頂点の部分木の辺を切ることで ${0}$ から ${x-1}$ に遷移できる. 元の頂点から見ると ${0}$ から ${x}$ のいずれにも遷移ができることがわかるので, ${x+1}$ となる.

ソース

これ出す時すごく緊張した. この辺で残り 40 分とかなのキツイ.

#include <bits/stdc++.h>
 
using namespace std;
 
vector< int > g[100000];
 
int dfs(int idx, int pre = -1)
{
  int ret = 0;
  for(auto &to : g[idx]) {
    if(to == pre) continue;
    ret ^= dfs(to, idx) + 1;
  }
  return (ret);
}
 
int main()
{
  int N;
  cin >> N;
  for(int i = 1; i < N; i++) {
    int X, Y;
    cin >> X >> Y;
    --X, --Y;
    g[X].push_back(Y);
    g[Y].push_back(X);
  }
  if(dfs(0, -1)) cout << "Alice" << endl;
  else cout << "Bob" << endl;
}