AtCoder Regular Contest 038 C：茶碗と豆

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つの茶碗に入っている豆の数は最大で10⁹個あるので全ての豆についてGrundy数のXORを取っていると間に合いませんが，同じ数のXORをとると0になるのでmod 2で計算をサボることができます。

Grundy数の計算に O(N²) かかるので計算量は O(N²) です。

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(N²) になってしまうので「index[0], index[1], ..., index[k-1] の最小値が i-C[i] 以上となる最大の k」の計算をセグメント木で実装します。私は平方分割で実装しました。次の記事も参考にしてみてください。Flipping Parenthesesの説明が参考になるかもしれません。

kujira16.hateblo.jp

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(N²) の方法が以下のように書き直せます。

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