C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoder
100点解法
見るからにNimとかGrundy数っぽい雰囲気を感じるので，ググってみると良質な記事がたくさん見つかります。今回は以下の記事を参考にしました。
http://pekempey.hatenablog.com/entry/2016/01/16/190208pekempey.hatenablog.com
最初に，左からi番目の茶碗に豆が1つだけ入っている場合を考えましょう。この場合のGrundy数を grundy[i] という変数に入れておくことにします。i=0 なら動かせる豆が存在しないので負けとなるわけですが，Grundy数の定義より，負けの状態のGrundy数は0なので grundy[0]=0 です。i≠0の場合は豆を i-C[i] 〜 i-1 のどこかに移動させる状態遷移があるので，Grundy数の定義より，grundy[i] は grundy[i-C[i]], grundy[i-C[i]+1], ..., grundy[i-2], grundy[i-1] に含まれない最小の非負整数です。これで，左からi番目の茶碗に豆が1つだけ入っている場合のGrundy数が計算できました。
続いて豆が複数ある場合のGrundy数を計算します。これはGrundy数の魔法により，全ての豆のそれぞれの grundy[i] のXORを取ったものが答えとなります。1つの茶碗に入っている豆の数は最大で109個あるので全ての豆についてGrundy数のXORを取っていると間に合いませんが，同じ数のXORをとると0になるのでmod 2で計算をサボることができます。
Grundy数の計算に O(N2) かかるので計算量は O(N2) です。
104点解法
「grundy[i-C[i]], grundy[i-C[i]+1], ..., grundy[i-2], grundy[i-1] に含まれない最小の非負整数」を計算するところを O(log N) くらいにできれば全体で O(N log N) になるので，この部分の計算を高速化しましょう。
セグメント木の要素にgrundy[i]の値をそのまま持たせて「grundy[i-C[i]], grundy[i-C[i]+1], ..., grundy[i-2], grundy[i-1] に含まれない最小の非負整数」を計算できれば簡単なのですが，残念ながらこれはできそうにありません。
唐突ですが grundy[i] を計算する際に，次のように定義される配列 index を使ってみることを考えましょう。
index[k]：grundy[j]=k となる最大の j (0 <= j < i)
この配列の重要な性質は以下の2つです。
- 「grundy[i]>=k」 ⇔ 「index[0], index[1], ..., index[k-1] の値が i-C[i] 〜 i-1 の範囲にある」
- 「index[0], index[1], ..., index[k-1] の値が i-C[i] 〜 i-1 の範囲にある」 ⇔ 「index[0], index[1], ..., index[k-1] の最小値が i-C[i] 以上である」
よって grundy[i]>=k となる最大の k を求めるためには index[0], index[1], ..., index[k-1] の最小値が i-C[i] 以上となる最大の k を求めれば良いことが分かります。これをナイーブに実装すると次のようになります。
grundy := make([]int, N) grundy[0] = 0 index := make([]int, N) index[0] = 0 for i := 1; i < N; i++ { index[i] = -1 } for i := 1; i < N; i++ { for k := 0; k < N; k++ { if i - C[i] <= index[k] { // do nothing } else { grundy[i] = k break } } index[grundy[i]] = i }
これでは O(N2) になってしまうので「index[0], index[1], ..., index[k-1] の最小値が i-C[i] 以上となる最大の k」の計算をセグメント木で実装します。私は平方分割で実装しました。次の記事も参考にしてみてください。Flipping Parenthesesの説明が参考になるかもしれません。
func intMin(a, b int) int { if a < b { return a } return b } const ( sqrtN = 512 INF = 1000000000 ) type SqrtDecomposition struct { N int K int data []int blockMin []int } func NewSqrtDecomposition(n, initialValue int) *SqrtDecomposition { k := (n + sqrtN - 1) / sqrtN sq := &SqrtDecomposition{ N: n, K: k, data: make([]int, k*sqrtN), blockMin: make([]int, k), } for i := 0; i < len(sq.data); i++ { sq.data[i] = initialValue } for i := 0; i < len(sq.blockMin); i++ { sq.blockMin[i] = initialValue } return sq } // data[x]=y func (sq *SqrtDecomposition) Update(x, y int) { k := x / sqrtN sq.data[x] = y minval := INF for i := k * sqrtN; i < (k+1)*sqrtN; i++ { minval = intMin(minval, sq.data[i]) } sq.blockMin[k] = minval } // min [0, k) >= x となる最大のkを返す func (sq *SqrtDecomposition) Find(x int) int { for k := 0; k < sq.K; k++ { if sq.blockMin[k] < x { for i := k * sqrtN; i < (k+1)*sqrtN; i++ { if sq.data[i] < x { return i } } } } return -1 }
これを使うと先ほどのナイーブな O(N2) の方法が以下のように書き直せます。
grundy := make([]int, N) grundy[0] = 0 sq := NewSqrtDecomposition(N, -1) sq.Update(0, 0) for i := 1; i < N; i++ { grundy[i] = sq.Find(i - C[i]) sq.Update(grundy[i], i) }
セグメント木を使えば計算量は O(N log N) です。今回は平方分割なので O(N√N) です。
Submission #1186675 - AtCoder Regular Contest 038 | AtCoder
