ferinの競プロ帳

競プロについてのメモ

Codeforces Round #200 (Div. 1) D. Water Tree

問題ページ
Problem - D - Codeforces

概要

頂点1が根のn頂点の木が与えられる。q個のクエリを処理する。
クエリ1 頂点vとvの子孫の頂点の値を1にする
クエリ2 頂点vとvの先祖の頂点の値を0にする
クエリ3 頂点vの値を出力する

解法

部分木に関するクエリなのでオイラーツアーをする。クエリ1,2について管理するセグメントツリーをそれぞれ用意する。セグメントツリーには、そのクエリを行った最後のクエリ番号を記録し、クエリ番号が大きい方の処理が後に行われたとして結果を出力する。
クエリ1の処理には区間更新・区間最大を求められる遅延セグメントツリーをつかう。クエリ2の処理には点更新・区間最大を求められるセグメントツリーを行う。クエリ2の処理がその頂点に対して行われるのはその部分木の頂点に行われたときのため、頂点の部分木の区間のうち最大のクエリ番号を求めればよい。
cin/coutだとTLEするので注意

Educational Codeforces Round 6 E. New Year Tree

問題ページ
Problem - E - Codeforces

概要

n要素の根が1の木が与えられる。m個のクエリを処理しろ。
クエリ1 頂点vの部分木の頂点の色をcに変更する。
クエリ2 頂点vの部分木に含まれる色の種類を求める

解法

部分木に関するクエリを処理するのにオイラーツアーを使う。オイラーツアーによって木を数列に変換し、部分木に当てはまる区間の色を更新する。色は60種類しかないためlong longでbitを使って管理できる。区間更新、区間orができる遅延セグメントツリーを使えばこの処理は可能。
cin/coutだとTLEするので注意

hackerrankのGame Theoryを解いたまとめ

ゲーム系問題があつまっている。
https://www.hackerrank.com/contests/5-days-of-game-theory/challenges

grundy数とかNimとかの勉強によかった。

Game of Stones

2人のプレイヤーがいて各ターンで2,3,5個の石を取り除く行動ができる。行動できなくなったら負け。

遷移先の状態に負けの状態があれば勝ち、全部勝ちなら負けと実装すれば通る。制約的に愚直に実装すれば大丈夫。

Tower Breakers

N個の高さMのタワーがある。二人のプレイヤーはタワーを1個選んで高さXのタワーをX未満のXの約数Yの高さのタワーに変更することができる。行動できなくなったら負け。

高さはすべて等しいため全てのタワーのgrundy数は等しい。よってタワーの数が偶数ならXORを取った結果は0になり、player2の勝ちとなる。また、タワーの高さが1ならplayer1はその時点で行動できないためplayer2の勝ち。

A Chessboard Game

15*15のチェス盤とチェス盤の上にコマが一つある。2人のプレイヤーは順番にこのコマを規則に沿って動かす。動かせなくなったら負け。

Game of Stonesと同様に愚直に実装すれば通る。

Nim Game

よくあるNim

XORをとる

Misere Nim

最後の石を取ったら負けのNim

Nimと同様にXORが0となる状態で相手に渡すのが基本でXORが0のとき負け。山の石の数が1以下のときは山の個数が奇数のとき、つまりXORが1のとき負け。

Nimble Game

squqreがN個あり、squareにはC[i]個のコインが存在している。プレイヤーはsquare-iからsquare-j(j < i)にコインを1枚移すことができる。動かせなくなったら負け。

i番目のsquareにコインが存在するのは、Nimのi枚の石の山に置き換えることができる。コインが偶数枚であればxorは0なので奇数枚のコインがあるsquareのindexのXORを取った結果で判断できる。

Poker Nim

N個の山がある。プレイヤーはいずれか一つの山から「一枚以上消す」「一枚以上加える」のいずれかを行う。加える行動はk回までしか行えない。行動できなかったら負け。

XORが0の状態で加える動作を行ったとしてもXORが0の状態を相手に押し付けることは可能。普通のNimと同様に判定できる。

Tower Breakers, Revisited!

N個のタワーがあり、各タワーの高さはh[i]である。各プレイヤーはどれかタワーを一つ選び高さをその約数の高さに変更することが出来る。行動できなかったら負け。

各塔のgrundy数はそのタワーの高さの素因数の個数になる。

Tower Breakers, Again!

N個のタワーがあり、各タワーの高さはh[i]である。各プレイヤーは高さXのタワーを高さYのタワーZ個に変えることができる。(Y>1, X=Y*Z) 行動できなかったら負け。

n個の独立した状態s[1],s[2],…,s[n]のgrundy数はs[1],s[2],…,s[n]それぞれのgrundy数のXORに一致するという定理を使う。高さ1のタワーをgrundy数0として設定し、grundy数の定義にしたがって計算していく。

Chessboard Game, Again!

15×15の大きさのチェスボードの上にコインがk枚存在する。各プレイヤーはコインを一つ選択し規則にしたがって移動させる。移動させられなかったら負け。

チェスボード上の各マスにgrundy数を割り当てる。もうコインを動かすことができないマスに0を割り当てあとは定義に従って計算する。

Digits Square Board

N×Nマスのボードが与えられる。各マスには1から9の数字がかかれている。各プレイヤーは合成数が一つ以上かかれているボードを選び、垂直・水平に二分割する。行動できなくなったら負け。

各ボードにgrundy数を割り当てる。合成数のみが含まれているかどうかを判定するのに累積和をしないとTLEするので注意。

Powers Game

n要素の数列A、Bが与えられる。手番にi(1<=i<=n)を選択することでプレイヤー1はa[i]、プレイヤー2はb[i]を得られる。最終的な点数の合計が高いほうが勝ち。

a[i]+b[i]が高い方から順に取る。

Powers Game

2^1,2^2,…,2^nの数列の要素を一つ選んでプラスかマイナスをつける。最終的な総和が17の倍数になればplayer2の勝ち。それ以外ならplayer1の勝ち。

2^n, -2^n (mod 17) を計算すると周期8で周期性、対称性がある。nが8の倍数のとき、player1が選んだものに合わせて0 (mod17)となるように取ることで17の倍数にすることができplayer2の勝ちとなる。

Deforestation

根が1、頂点数がNの木が与えられる。各プレイヤーは任意の辺を取り除くことができ、根とつながっていない頂点は取り除かれる。操作できなくなったら負け。

子の部分木のパスの長さが石の数の山のNimに帰着できる。(それぞれの子の部分木の長さを任意の長さに短く出来るためNimの操作と同じ)子の部分木のパスの長さのXORを取ったものを各頂点のgrundy数とすると、根のgrundy数が0ならBob、0以外ならAliceの勝ちになる。

Tower Breakers - The Final Battle

player1は高さHの塔をx個の塔に分割する。(塔iの高さをh[i]とすると H = \sum_{i=0}^{x} h[i] となるように高さを決める) player2はx個のうちk番目(1<=k<=x)の塔を選択する。player2はk^2円を獲得し、player1はH=h[k]として再び手番を行う。playerが最適な行動をしたときplayer2はいくら獲得するか。

(解説を読んだけどDPの遷移がよく理解できていない…)
まず、得られる金額の上界は4*logNになる。player1が高さHの塔を二分割し、player2が2番目の塔を選び4円を獲得するとする。この方法ではlogN回で終了するため、4*logNが上界となる。
dp[x] = (答えがx以下になる最大の塔の高さ) としたDPを考える。4*log_{2}10^18 ≒ 239.1 より、配列の要素数は300程度で問題ない。
DP遷移は dp[x] = \sum_{j=1}^{sqrt(x)} dp[x-j^2] となるのでこれを前計算しておく。与えられたNについて二分探索しインデックスの値が答えとなる。dpの値はlong long intの値も超えるので注意。

nCkの偶奇

nCkの偶奇はlucasの定理から(n&k)==kで判定できるというのをTLで見かけたので調べた。

mathtrain.jp

C(0,0) = 1, C(0,1) = 0, C(1,0) = 1, C(1,1) = 1 となるので n_i = 0 で k_i = 1となるiがあれば偶数、なければ奇数となる。

n k n&k
0 0  0
0 1  0
1 0  0
1 1  1

より (n&k) != kのときのみ n_i = 0 で k_i = 1となるiが存在する。

よって、(n&k) == k であれば nCkは奇数、(n&k) != k であれば nCkは偶数となる。

Croc Champ 2013 - Round 1 E. Copying Data

問題ページ
Problem - E - Codeforces

問題概要

数列a, bが与えられる。次の2種類のクエリを処理する。
1. b[y+q] = a[x+q] ( 0 <= q < k )
2. b[x]を表示する

解法

区間更新の遅延セグメントツリーを使う。遅延更新用の配列に更新する配列aのインデックスとの値の差を記録しておき、評価するときに最下段であれば適切な配列aの値を代入する。

codeforces #261 div2 D. Pashmak and Parmida's problem

問題ページ
Problem - D - Codeforces

概要

数列aが与えられる。f(l,r,x) を l<=k<=r の範囲で a[k] = xとなる要素の個数と定義する。f(1,i,a[i]) < f(j,n,a[j])となる(i, j)の組(1 <= i < j <= n)の個数を求めろ。

解法

まず、f(1, i, a[i])を計算する。それぞれの要素の個数を数える配列を用意して順に計算していけばよいが、a[i]<=10^9より普通にもつことはできない。そこで座圧しておく。f(j, n, a[j])も同様に事前に計算しておき、b[i] = f(1,i,a[i])、c[i] = f(i,n,a[i])と配列でもっておく。
b[i]>c[j]となるような(i,j)の組の個数を求めればいい。BITを用いて今までに出てきた要素別の個数を数えておくとO(nlogn)でこの処理はできる。

codeforces #207 div1 A. Knight Tournament

問題ページ
Problem - A - Codeforces

解法

[l_i, x_i)、(x_i、r_i]の区間でまだ誰にも負けていない兵士がいればその兵士はx_iに負けたとして更新していけばよさそう。すでに負けた、負けていないを管理するのが大変そうだったのでクエリを逆に読んで、管理しなくてもいいようにする。
遅延セグ木を使えば各クエリに対して[l_i, x_i) (x_i, r_i]の区間にx_iを更新するのをO(logN)でできる。結果を出力する前に各頂点に遅延更新をしないと正しい答えにならないので注意。