Codeforces Round 1055

A. Increase or Smash

最大値以外は種類数に $1$ 回ずつ increase, smash が必要になります.

B. Catching the Krug

D の最適な移動は決まります.K はあるひとつの辺に向かって進んだあと隅に向かって進むことになります.場合分けがしんどいですがサンプルは親切でした.

C. Triple Removal

初期状態に 00 や 11 があれば,削除後にもそのような場所が存在するという状態をキープできます.

$00$ があるとして,$0$ の削除を考えます.ある $3$ つを削除すると詰みになったとすると,もともとは $01010101\cdots$ の $3$ 箇所に $0$ を挿入した状態だったということになって,丁寧に場合分けをすると示せます.

D. Division Versus Addition

大事な数とは,PRPR… と RPRP… でスコアが異なる要素とします(先着した側が有利).大事でない数とは,これらのスコアが一致する要素とします.

大事でない要素は無視してよいことが分かります.そのような要素をひとつとり固定して,お互いに,その要素については相手が選んだ直後に自分も選ぶようにすることで,要素を無視した場合以上の利益を確定できるからです.

大事な要素は $2^k+1$ の形の数で,操作後には大事ではなくなることが分かります.よって,大事な要素については先に選んだ人が $1$ 点を得て終了と見なしてゲームをすればよくなります.

E. Monotone Subsequence

  • $k$ 回目の質問では,レベルが未定義のインデックスをすべて質問する.
  • $N+1$ 個以上のものがかえってきたらそれを出力して終了.
  • 返ってきたインデックスのレベルを $k$ とする.

として,$k=1,2,\ldots,N$ で反復します.最後まで残ったものはレベル $N+1$ とします.途中で長さ $N+1$ の増大列が見つからないとき,レベル $N+1$ のインデックスがひとつ以上あることに注意.

レベル $k\geq 2$ のインデックスは,クエリ $k-1$ で invisible だったということなので,あるレベル $k-1$ の要素が「左上」にあります(インデックスが手前で値が大きい).

レベル $N+1$ の要素から左上にたどることで長さ $N+1$ の減少列が得られます.

F. Triple Attack

まずクエリごとに解くならば,適当な貪欲シミュレーションでよいです.だいたい次のような感じです.

  • $a=L, b=L+1$ から始める.
  • $a=nxt[a]$, $b=nxt[b]$ などとしていく.重なったらずらす.

ただし nxt は,$z$ より多く進む最小インデックスです.

まず,nxt 配列に対して binary lifting table を作っておきます.すると $(i,i+1)$ からスタートしたときに次に重なるのがいつかが求められます.$k$ 回ずつ進んで重なったら $k$ 回よりたくさんずつ進んでも重なっているという単調性から二分探索できます.

$a$ を $k+1$ 回,$b$ を $k$ 回進めて重なるというパターンもあることに注意します.これは,$nxt[a]$ と $b$ を同じ回数進めるとして同じように実装できます.

これで「$(i,i+1)$ から何度か貪欲を進めて $(j,j+1)$ に至る」という部分を計算できたので,今度はこれを $1$ ステップとして binary lifting table を作っておけばよいです.

G. Query Jungle

$1$ である頂点が dfs 順に見て $v_0,v_1,v_2,\ldots$ であるとき,steinter tree はパス $v_i\to v_{i+1}$ をつないだものであるという典型知識を使います.おおよそ次の形になります.

  • 01 列 $a$ がある.
  • $a_i=a_j$ かつ $i<k<j$ に対して $a_k=\neq a_i$ であるときに,$j=nxt[i]$ と定める.
  • $a_i=1$ であるような $i$ に対してスコア $1$ を得る.
  • $a_i=1$ かつ $j=nxt[i]$ としたとき $v_j$ が $v_i$ の subtree にあるとスコア $-1$ を得る.
  • 合計得点を求めるクエリと,$a$ の区間フリップのクエリが来る.

区間フリップが来ても,nxt[] は $O(1)$ 個しか変わらないことに注意すれば,単純な遅延セグメント木で解けます.nxt 変更を無視した場合の区間フリップを遅延セグメント木で処理し,nxt を変更したところだけ作り直すという要領です.

H2. Victorious Coloring (Hard Version)

まだ.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました