Codeforces Round #668 (Div. 2) 出たよ～～～～

約2か月半ぶりのこどふぉ、Div.2に参加しました。結果は2完（A,B）で緑落ちです。超絶自業自得……。Dまでは他の人に教えてもらったのでブログに残そうと思います。
コンテストURL：https://codeforces.com/contest/1405

A. Permutation Forgery

問題概要

～までの整数で、要素の重複なく構成された長さの数列に対応して、以下のの長さの数列を作ります。

が等しく、かつである長さの数列をひとつ出力してください。

考え・反省

が等しくなるためには、ペアになる要素が元の数列と同じである必要があります。たとえばだったら1個目+2個目、2個目+3個目がペアになって長さ2の数列になります。合体後の順番はソートされるので、数列をreverseするだけで通ります。
↑数列を反転させれば通るのに、サンプルを見てものすごく悩んでしまって嘘解法を投げました（懺悔）

B. Array Cancellation

問題概要

となるような、長さの数列が与えられます。この中から一度の操作につき番目と番目の要素を選び、番目の要素にを足し、番目の要素からを引きます。であった場合にはコストがかからず、そうでない場合には1回の操作で1コストかかります。
数列の要素を全てにするために必要な最小のコストを求めてください。

考え・反省

「今まで出てきた正の数の和」を持っておき、もし負の数が出てきたらそこから引いていきます。これを最後まで繰り返すと、数列の和が0になることから、「残った負数の和」と「残った正数の和」は等しいので、その絶対値を出力します。
↑という条件を見逃していて、無限に不可能なパターンについて考えていました。涙。

実装（折りたたんでいます）

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

signed main(){
  int Q;
  cin >> Q;
  for( int q = 0; q < Q; q++ ){
    int N;
    cin >> N;
    vector<int> A(N);
    int plus = 0;
    for( int i = 0; i < N; i++ ){
      cin >> A[i];
      if( A[i] > 0 ){
        plus += A[i];
        A[i] = 0;
      }
      else{
        if( plus+A[i] >= 0 ){
          plus += A[i];
          A[i] = 0;
        }else{
          A[i] += plus;
          plus = 0;
        }
      }
    }
    cout << plus;
    cout << "\n";
  }
}

C. Balanced Bitstring

問題概要

だけで構成された長さの文字列が与えられます。にはの好きな方を選んで置換します。この文字列の中から連続した個（は偶数）を取り出した際、どの部分でもとの個数が等しくなるようにすることはできますか？

考え・反省

modごとに見るということを全く思いつきませんでした（反省）。
で等しくなる部分の文字がすべて同じで、かつ最初の個が条件を満たしていればYES、そうでなければNOです。
たとえばでのとき、最初の個は「」で、1個右にずらした部分から個取ると「」です。最初の個が条件を満たしていてくれれば、抜き出す部分を1個右にずらした際に新しく部分文字列に入った文字（右端）と、左端にあった捨てる文字が等しいことで、1と0の数の均衡を保てます。
もし最初の個の中にが含まれていた場合は未確定にしておいて、途中でかが出てきたら確定させます（そして確定後の文字列が条件を満たすか確認します）。

実装（折りたたんでいます）

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

signed main(){
  int Q;
  cin >> Q;
  for( int q = 0; q < Q; q++ ){
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    bool fg = 1;
    vector<char> num(K, '?');
    int sum = 0;
    int hatena = 0;
    for( int i = 0; i < K; i++ ){
      if( S[i] == '0' ) sum--;
      else if( S[i] == '1' ) sum++;
      else hatena++;
      num[i] = S[i];
    }
    if( abs(sum) > hatena ) fg = 0;

    for( int i = K; i < N; i++ ){
      if( num[i%K] == '0' && S[i] == '1' ) fg = 0;
      else if( num[i%K] == '1' && S[i] == '0' ) fg = 0;
      if( num[i%K] == '?' && num[i%K] != S[i] ){
        num[i%K] = S[i];
        hatena--;
        if( S[i] == '1' ) sum++;
        else sum--;
        if( abs(sum) > hatena ) fg = 0;
      }
    }
    if( fg ) cout << "YES\n";
    else cout << "NO\n";
  }
}

D. Tree Tag

問題概要

AliceとBobは頂点の木グラフ🌲の上で鬼ごっこをします。最初はAliceが頂点、Bobが頂点にいて、Alice→Bobの順番で移動します。一回の移動でAliceは最大、Bobは最大の距離を移動できます（ここでの距離とは頂点間の辺の数を指します）。この移動を回する間に、AliceがBobと同じ座標に辿り着けたらAliceの勝ち、そうでなければBobの勝ちです。鬼ごっこの勝者を出力してください。

考え

回移動できる＝いちいち二人の動作を追ってたら絶対に間に合わないので、何かしらの条件があるはず。移動回数が多い分Aliceが有利な気がする（？！）ので、「どうやったらBobが勝てるか」で少し考えてみます。

• 初期配置で、Aliceとの距離が以上離れてないとダメ（最初の1手でAliceに追いつかれてしまうため）
• 木の直径がある程度大きくないとダメ（Aliceがどの頂点にも1手で移動できる状態になると詰むため）

→「ある程度」がどのくらいか？を考えます。ちょうどグラフの真ん中らへんに立てば、木の直径が以下だとAliceはどこにでも行けてしまうので、それより大きい必要があります。

• 

→これ教えてもらうまで理解できませんでした……。
まず、頂点の数よりも移動可能回数のほうがずっと多いので、Bobは逃げ回るときに「Aliceのいる方向」へ逃げないといけない状況が生じます。その際、Bobの移動可能距離がAliceの「1手で移動可能な範囲」よりも大きければ、つかまってしまうゾーンを「飛び越えて」逃げ回ることができます。逆に、それよりBobの移動距離が小さい場合はどこかでAliceが1手で移動できる範囲に入らざるを得ず、捕まってしまいます。

実装（折りたたんでいます）

#include <bits/stdc++.h>
#define int long long
using namespace std;
using Graph = vector<vector<int>>;

signed main(){
  int Q;
  cin >> Q;
  for( int q = 0; q < Q; q++ ){
    int N, A, B, DA, DB;
    cin >> N >> A >> B >> DA >> DB;
    A--; B--;
    Graph G(N);
    for( int i = 0; i < N-1; i++ ){
      int a, b;
      cin >> a >> b;
      a--; b--;
      G[a].push_back(b);
      G[b].push_back(a);
    }

    //木の直径を求める
    vector<int> dist(N, -1);
    queue<int> que;
    dist.at(A) = 0;
    que.push(A);
    while( !que.empty() ){
      int v = que.front();
      que.pop();
      for( int nv : G.at(v) ){
        if( dist.at(nv) != -1 ) continue; //すでに通っていたらスルー
        dist.at(nv) = dist.at(v)+1;
        que.push(nv);
      }
    }

    int start = 0;
    int k = 0;
    for( int i = 0; i < N; i++ ){
      if( k < dist[i] ){
        k = dist[i];
        start = i;
      }
    }

    vector<int> ponyo(N, -1);
    ponyo.at(start) = 0;
    que.push(start);
    while( !que.empty() ){
      int v = que.front();
      que.pop();
      for( int nv : G.at(v) ){
        if( ponyo.at(nv) != -1 ) continue; //すでに通っていたらスルー
        ponyo.at(nv) = ponyo.at(v)+1;
        que.push(nv);
      }
    }

    int dia = 0;
    for( int i = 0; i < N; i++ ) dia = max(dia, ponyo[i]);
    if( dist[B] <= DA || dia <= 2*DA || DB <= 2*DA ) cout << "Alice\n";
    else cout << "Bob\n";
  }
}

競プロなんもわからん！解散！