yukicoder No.511 - 落ちゲー 〜手作業のぬくもり〜

Source

ニコニコミュニティ
問題文

問題概要

高さが無限大,幅が $W$ の2次元のグリッドがある.
AさんとBさんが順番に以下の行動を行う.

  1. $i$ 番目の手番のプレイヤーは,$1 \times 1$ ブロックを横に $A_i$ 個,縦に $B_i$ 個集めた $A_i \times B_i$ ブロック塊を好きな場所(グリッドに沿って中途半端じゃない位置)に置く.
  2. その際,幅1の各列について,その列に含まれる $1 \times 1$ ブロックの個数が初めて $H$ 以上となったなら,$i$ 番目の手番のプレイヤーに $1$ 点与える.
  3. 最終的に,多くの得点を得たほうが勝者になる.

今,$N$ 番目の手順まで,$i$ 番目の手順では,$A_i \times B_i$ のブロック塊を $X_i$ 列から $X_i+A_i-1$ 列に重なるように置いたという情報が与えられる.
$N$ 番目の手順が終わった時点で,全ての列には $H$ 個以上の $1 \times 1$ ブロックが置かれていることが保証されている.
どちらが勝ったか求める問題.

解法

セグメントツリーを使いながら愚直にシミュレーションする.
具体的には長さ $W$ の配列を扱えるセグメントツリーを用意し,ブロックを置いたときは,$X_i$ から $X_i+A_i-1$ 番目の要素に $B_i$ を足す.
そして,要素の最大値を調べて $H$ 以上であれば,今のターンの人に $1$ 点を与えて,その要素にマイナス無限大を加えてやれば良い(これは最大値が $H$ 未満になるまで繰り返す).
時間計算量は $O((N+W) \log W)$ 程度.

cLayversion 20170430-1)のコード

C++に変換後のコードはこちら

int A[100000], B[100000], X[100000];
{
  int i, k;
  ll N, W, H;
  segtree<ll> t;
  pair<ll,int> mn;
  ll res[2] = {0LL, 0LL};

  rd(N,W,H,(A,B,X)(N));
  X[0..N-1]--;
  
  t.malloc(W, 1);

  rep(i,N){
    t.add(X[i], X[i]+A[i], -B[i]);
    for(;;){
      mn = t.getMin(X[i], X[i]+A[i]);
      if(mn.first > -H) break;
      k = mn.second;
      res[i%2]++;
      t.add(k,k+1,1d18);
    }
  }

  if(res[0] > res[1]) wt("A");
  if(res[0] < res[1]) wt("B");
  if(res[0]==res[1]) wt("DRAW");
}

Current time: 2017年09月25日11時45分37秒
Last modified: 2017年04月30日01時17分55秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: