Codeforces Round #406 (Div. 1)

A がわからなかったので撤退してしまった(悪魔的ね！ごめんなさい).

A. Berzerk

codeforces.com

問題概要

${1}$ から ${n}$ まで番号付けされた ${n(2 \le n \le 7000)}$ 個の object が時計回りに配置されている.

${2}$ 人は, 以下のルールに基づいてゲームをしようとしている.

モンスター ${1}$ 匹が object ${1}$ 以外のどこかにいる.
プレイヤーのそれぞれは ${k_{1}, k_{2}(1 \le k_{1}, k_{2} \le n - 1)}$ 個からなる distinct な集合 ${s_1, s_2}$ を持っている.
それぞれの要素の値は ${1}$ 以上 ${n - 1}$ 以下である.
プレイヤーは交互に, 自分の集合の中から要素 ${x}$ を ${1}$ つ選択し, モンスターを時計回りに ${x}$ 個進める操作をする.
操作後にモンスターが object ${1}$ に存在していればそのプレイヤーの勝ちである.

(先攻のプレイヤー, モンスターの最初の位置) ごとに, プレイヤーが最適に行動したときどちらが勝つか, あるいは引き分けるか判定せよ.

解法

気合いでDPをする.

以下ソースコードと辻褄をあわせるために 0-indexed で考える.

${f(player, idx)}$ := 手番が ${player}$ で現在位置が ${idx}$ のときのゲームの結果を任意のペアについて求めれば良い.

まず自明なアレとして, 現在位置が ${0}$ のときに手番が回ってきたら負けなので ${f(player, 0) = lose}$ である. ここを起点に, 幅優先で他の状態を埋めていく.

ある状態 ${f(x, y)}$ が win であるためには ${f(1-x,y + s_{x,i}) = lose}$ となる ${i}$ が ${1}$ 個以上存在すれば良いのはそれはそう. これを逆に考えて, えいってやると遷移可能(これはソースコードの上のif文).

ある状態 ${f(x, y)}$ が lose であるためには任意の ${i}$ に対して ${f(1-x,y + s_{x,i}) = win}$ となることである. つまり win となるものが ${k_x}$ 個存在していることと等価である. これは, 各状態 ${(x, y)}$ に対して行き先が win となる個数を保持しておけば可能で, この個数が ${k_x}$ となった瞬間に状態に追加すればできる(これはソースコードの下のelse文).

それ以外の状態 ${f(x, y)}$ に対しては loop として良い.

全体の計算量は, 各状態で ${k_x}$ 個の遷移を行うので ${O(n^2)}$ .

ソース

うーん, 非自明なDPだと思っていたけど整理したらそれはそうだったみたいなやつだ.

ループの判定がよくわからなくて無限に悩んでいた.

#include<bits/stdc++.h>

using namespace std;

int N, K[2], S[2][7000];
int deg[2][7000], dp[2][7000];

int main()
{
  scanf("%d", &N);
  for(int i = 0; i < 2; i++) {
    scanf("%d", &K[i]);
    for(int j = 0; j < K[i]; j++) {
      scanf("%d", &S[i][j]);
    }
  }

  queue< tuple< int, int > > que;
  memset(dp, -1, sizeof(dp));
  for(int j = 0; j < 2; j++) {
    que.emplace(j, 0);
    dp[j][0] = 0;
  }
  while(!que.empty()) {
    int player, number;
    tie(player, number) = que.front();
    que.pop();

    if(dp[player][number] == 0) {
      for(int i = 0; i < K[player ^ 1]; i++) {
        int pre = (number - S[player ^ 1][i] + N) % N;
        if(~dp[player ^ 1][pre]) continue;
        dp[player ^ 1][pre] = 1;
        que.emplace(player ^ 1, pre);
      }
    } else {
      for(int i = 0; i < K[player ^ 1]; i++) {
        int pre = (number - S[player ^ 1][i] + N) % N;
        if(~dp[player ^ 1][pre]) continue;
        if(++deg[player ^ 1][pre] == K[player ^ 1]) {
          dp[player ^ 1][pre] = 0;
          que.emplace(player ^ 1, pre);
        }
      }
    }
  }

  for(int i = 0; i < 2; i++) {
    for(int j = 1; j < N; j++) {
      if(dp[i][j] == 0) printf("Lose ");
      else if(dp[i][j] == 1) printf("Win ");
      else printf("Loop ");
    }
    puts("");
  }
}

B. Legacy

codeforces.com

問題概要

${n(1 \le n \le 10^5)}$ 頂点の重み付き辺を持つ有向グラフが, 以下の ${q(1 \le q \le 10^5)}$ 個のクエリからなる形式で与えられる.

頂点 ${v_i}$ から頂点 ${u_i}$ を繋ぐ辺がある.
頂点 ${v_i}$ から区間 ${[l_i, r_i]}$ の全ての頂点 ${u}$ を繋ぐ辺がある.
区間 ${[l_i, r_i]}$ の全ての頂点 ${u}$ から頂点 ${v_i}$ を繋ぐ辺がある.

各重みは ${w_i}$ である.

頂点 ${s(1 \le s \le n)}$ から任意の頂点までの最短コストを求めよ.

解法

クエリを完全二分木で, セグ木っぽく処理する形にする.

f:id:ei1333:20170326163502p:plain

上の図が全てを物語っている. 区間 ${[1, 5]}$ の全ての頂点から頂点 ${7}$ へ重み ${w_i}$ の辺を繋いだ例である. これはタイプ 3 の操作そのものである.

タイプ 3 の操作, タイプ 1 の操作の全てはこの操作で実現できる. タイプ 2 については方向が逆なので, 上の図とは反対の形をした完全二分木を用意し同様に辺を張れば良い.

辺の数は各クエリで ${O(\log N)}$ 本なので ${O(Q \log N)}$ . 頂点数はだいたい ${2N}$ 個なので ${O(N)}$ .

このグラフをDijkstraすればよいので全体で ${O(Q \log^2 N)}$ となる.

ソース

はい. B やれば解けてたかも. 実装が険しい.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 INF = 1LL << 58;
typedef pair< int64, int > Pi;

struct edge
{
  int to, cost;
};

struct SegmentTreeGraph
{
  vector< vector< edge > > g;
  int n, sz;

  SegmentTreeGraph(int n) : n(n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    g.resize((2 * sz - 1) * 2);
    for(int k = 0; k < n; k++) {
      g[(k + sz - 1) * 2].push_back((edge) {(k + sz - 1) * 2 + 1, 0});
      g[(k + sz - 1) * 2 + 1].push_back((edge) {(k + sz - 1) * 2, 0});
    }
    for(int k = sz - 2; k >= 0; k--) {
      g[k * 2].push_back((edge) {(2 * k + 1) * 2, 0});
      g[k * 2].push_back((edge) {(2 * k + 2) * 2, 0});
      g[(2 * k + 1) * 2 + 1].push_back((edge) {k * 2 + 1, 0});
      g[(2 * k + 2) * 2 + 1].push_back((edge) {k * 2 + 1, 0});
    }
  }

  void add(int a, int b, int x, int t, int w, int k, int l, int r)
  {
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      if(t == 2) g[(x + sz - 1) * 2].push_back((edge) {k * 2, w});
      else g[k * 2 + 1].push_back((edge) {(x + sz - 1) * 2 + 1, w});
      return;
    }
    add(a, b, x, t, w, 2 * k + 1, l, (l + r) >> 1);
    add(a, b, x, t, w, 2 * k + 2, (l + r) >> 1, r);
  }

  void add(int a, int b, int x, int t, int w)
  {
    add(a, b, x, t, w, 0, 0, sz);
  }

  void dijkstra(int k)
  {
    k += sz - 1;
    k *= 2;
    priority_queue< Pi, vector< Pi >, greater< Pi > > que;
    vector< int64 > v(g.size(), INF);
    v[k] = 0;
    que.emplace(0, k);
    while(!que.empty()) {
      auto p = que.top();
      que.pop();
      if(p.first > v[p.second]) continue;
      for(auto &e : g[p.second]) {
        if(p.first + e.cost >= v[e.to]) continue;
        v[e.to] = p.first + e.cost;
        que.emplace(v[e.to], e.to);
      }
    }

    for(int i = 0; i < n; i++) {
      if(v[(i + sz - 1) * 2] >= INF) printf("-1 ");
      else printf("%lld ", v[(i + sz - 1) * 2]);
    }
    puts("");
  }
};

int main()
{
  int N, Q, S;

  scanf("%d %d %d", &N, &Q, &S);
  SegmentTreeGraph tree(N);
  while(Q--) {
    int t, v, l, r, w;
    scanf("%d", &t);
    if(t == 1) {
      scanf("%d %d %d", &v, &l, &w);
      --v;
      --l;
      r = l + 1;
      t = 2;
    } else {
      scanf("%d %d %d %d", &v, &l, &r, &w);
      --v;
      --l;
    }
    tree.add(l, r, v, t, w);
  }
  tree.dijkstra(--S);
}

C. Till I Collapse

codeforces.com

問題概要

長さ ${n}$ の数列 ${a_i(1 \le a_i \le n)}$ がある.

それぞれの ${k(1 \le k \le n)}$ に対して, 最大 ${k}$ 種類の値が含まれるように配列を順番を変えずに分割したときの最小の長さを求めよ.

解法

セグ木を使って怖いことをやるのが想定解らしいが, †分割統治法†というすごい(語彙力の不足)解法がある.

ある ${k}$ に対して最小の長さを求めることは貪欲で ${O(n)}$ . 尺取りっぽくやる.

あとは, ソースコードのようなことをする.

計算量が闇だが, 答えに現れる値の種類数が ${O(\sqrt N)}$ なのでだいたい ${O(N \sqrt N)}$ らしい(公式のEditorialによると).

ソース

#include<bits/stdc++.h>

using namespace std;

int N, A[100000];
int ans[100001];

int beet(int v)
{
  int sum[100001] = {}, last = 0, ret = 1, uku = 0;
  for(int i = 0; i < N; i++) {
    sum[A[i]]++;
    if(sum[A[i]] == 1) ++uku;
    if(uku > v) {
      while(last < i) --sum[A[last++]];
      ++ret;
      uku = 1;
    }
  }
  return (ret);
}


void rec(int l, int r)
{
  while(l < r && ans[l] == ans[r]) ans[++l] = ans[r];
  if(r - l <= 1) return;
  int mid = (l + r) >> 1;
  ans[mid] = beet(mid);
  rec(l, mid);
  rec(mid, r);
}

int main()
{
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }
  ans[1] = beet(1);
  ans[N] = beet(N);
  rec(1, N);

  for(int i = 1; i <= N; i++) printf("%d ", ans[i]);
  puts("");
}

ei1333の日記

ぺこい

Codeforces Round #406 (Div. 1)

A. Berzerk

問題概要

解法

ソース

B. Legacy

問題概要

解法

ソース

C. Till I Collapse

問題概要

解法

ソース