保存されている過去のバージョンの一覧

2017年04月30日01時17分55秒

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)$ 程度．

cLay（version 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: 2024年04月26日00時18分35秒
Last modified: 2017年04月30日01時17分55秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：