読者です 読者をやめる 読者になる 読者になる

AtCoder Regular Contest 038 C:茶碗と豆

C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoder

100点解法

見るからにNimとかGrundy数っぽい雰囲気を感じるので,ググってみると良質な記事がたくさん見つかります。今回は以下の記事を参考にしました。

pekempey.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の説明が参考になるかもしれません。

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(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

参考にした記事

mayokoex.hatenablog.com

NAISTから自転車で行ける本屋の紹介

私がNAISTの寮に引っ越してからもうすぐで1年になります。私は原付や自動車を持っていないので,移動はほとんど自転車頼りです。本記事では同じような状況の人のためにNAISTから自転車で行くことができる本屋を紹介したいと思います。

私は情報科学研究科の学生なので,プログラミングに関する本(オライリー本など)や数学に関する本の有無に注目することが多いです。最初に結論を言っておくと,そのあたりの本を探すときには ACADEMIAけいはんな店 > ジュンク堂書店奈良店 ≒ 未来屋書店イオン高の原店 >>> それ以外 という順位付けになると思います。

旭屋カルチャースクエア イオン奈良登美ヶ丘店

Google マップ

2月末にグルメシティ北大和店が閉店したことにより,この書店がNAISTから最も近い本屋になりました。文芸書,漫画,ラノベはそれなりに置いていますが,専門書はほとんど置いていないです。

ACADEMIAけいはんな

Google マップ

NAIST近くにある書店の中では,専門書が比較的充実していると思います。種類は多くないですがオライリー本も置いています。最近は「ゼロから作るDeep Learning」が売れているみたいです。数学ガールも置いています。

文芸書は置いてありますが,漫画,ラノベは置いていないので,必要ならば近くにあるTSUTAYA精華台店に行くか,山を降りて旭屋カルチャースクエア イオン奈良登美ヶ丘店に行くことをおすすめします。

TSUTAYA精華台店

Google マップ

ACADEMIAけいはんな店の近くにあります。文芸書,漫画,ラノベの扱いは充実しています。専門書は置いてないです。

WAY書店 TSUTAYA奈良押熊店

Google マップ

専門書は置いていないです。わざわざ行くほどではないと思います。

啓林堂書店 学園前店

Google マップ

文芸書とラノベの取り揃えが比較的充実しているような気がします。理工系の本の取り揃えが非常に少ないです。

ジュンク堂書店 奈良店

Google マップ

2016年の8月に奈良県初のジュンク堂書店としてオープンしました。1フロアしかないこともあり,都会のジュンク堂書店と比べると専門書の扱いが少ないです。

私にとっては余裕を持って自転車で往復できるのはここくらいまでかなと思います。

未来屋書店イオン高の原店

Google マップ

イオンシネマ高の原の下のフロアにある書店です。プログラミング関係の専門書は少しありますが,数学に関する本など,それ以外の理工系の本は見つからなかったです。

関連記事

kujira16.hateblo.jp

kujira16.hateblo.jp

Androidスマートフォンのディスプレイが映らなくなったときの悪あがき

東京への遠征中にスマートフォンASUS Zenfone 2 Laser)のディスプレイが突然映らなくなってしまいました。「USBケーブルを接続するとバイブレーションが動く」「カメラを起動してから画面をタッチするとフォーカスを合わせる音がする」といった状況から,ディスプレイにのみ異常が発生しており,OS周りには異常はなく,タッチスクリーンも生きていると推測しました。

スマートフォン全体が完全に動作しなくなってしまったのであればデータの救出も諦めるしかありませんが,ディスプレイ以外は正常に動作しているようなのですからできる限りのことはやっておきたいものです。この記事では同じような状況に陥ってしまった人のための最後の悪あがきを紹介します。

スマートフォンがMHLに対応しているとき

MHLケーブルはスマートフォンのUSB microBに接続することでディスプレイの表示をHDMIに出力するケーブルです。スマートフォンがMHLに対応しているならば最も確実な方法だと思います。

ELECOM MHL変換ケーブル 3m ブラック MPA-MHLHD30BK

ELECOM MHL変換ケーブル 3m ブラック MPA-MHLHD30BK

この方法の弱点としては低〜中価格帯のスマートフォンはMHLに対応していないものが多いということが挙げられます。私が使用していたASUS Zenfone 2 Laserがまさにこのタイプで,この方法は使えませんでした。

スマートフォンがMHLに対応していないとき

この場合は何とかしてPCに画面を転送することを目標にします。私が使ったのはVysorというChromeアプリで,マルチプラットフォームに対応しています。

chrome.google.com

このアプリを使うためにはAndroidのUSBデバッグを有効にする必要があります。ディスプレイが映らない状況ではUSBデバッグを有効にすることがそもそも難しいのですが,ここではUSB経由でスクリーンショットを転送するという方針を取りました。私の場合は幸運にも,スマートフォンのパスコードの入力さえしてしまえばAndroid File Transferを使うことでUSB経由でスクリーンショットが保存してあるディレクトリを覗くことができました。スクリーンショットで現在の画面の状態を確認することができればUSBデバッグを有効にする画面まで移動することはそれほど難しくありません。あとは前述のアプリを使えばPCに画面を転送することができるだけでなく,PCからスマートフォンを操作できます。