088 D - XOR World

入出力

1
2
let A,B = stdin.ReadLine().Split() |> Array.map int64 |> (fun x -> x.[0],x.[1])
solve A B |> stdout.WriteLine

解説

素直な計算ではTLEする

最大で10^12個の項の計算が入るため, 次のようなごく素直な計算はTLEです.

1
let solve (A:int64) B = [|A..B|] |> Array.reduce (fun a b -> a^^^b)

ちなみに手元で計算したベンチマークは次の通りです.

1
2
3
4
5
6
7
8
9
let benchmark i =
  let N = pown 10L i
  let sw = System.Diagnostics.Stopwatch()
  sw.Start()
  let mutable x = 0L
  for i in 0L..N do x <- x^^^i
  sw.Stop()
  printfn "FOR 10^%2d: %A" i (sw.Elapsed)
for i in 0..10 do benchmark i

結果は次の通りです.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
FOR 10^ 0: 00:00:00.0000468
FOR 10^ 1: 00:00:00.0000048
FOR 10^ 2: 00:00:00.0000004
FOR 10^ 3: 00:00:00.0000024
FOR 10^ 4: 00:00:00.0000228
FOR 10^ 5: 00:00:00.0002399
FOR 10^ 6: 00:00:00.0022921
FOR 10^ 7: 00:00:00.0227260
FOR 10^ 8: 00:00:00.2289895
FOR 10^ 9: 00:00:02.3168958
FOR 10^10: 00:00:23.2159475

10^10の時点で既に20秒もかかっています.

実装

公式解説通りの実装は結果から言えば次の通りに書けます.

1
2
3
4
5
6
let solve A B =
  let g x = Array.get [|x;1L;x+1L;0L|] ((x+4L)%4L |> int)
  g (A-1L) ^^^ g B

let A,B = stdin.ReadLine().Split() |> Array.map int64 |> (fun x -> x.[0],x.[1])
solve A B |> stdout.WriteLine

ちなみに(x+4L)%4LはA = 0への対策です. F#では(-1)%4 = -1で配列外参照が起きます. ここでは場合分けではなくmodの部分に手を入れました.

問題はgの実装です. 条件文をいろいろ書いて頑張ってもいいのですが, 以下の実験・具体例での確認を前提に上記のようにすっきり書いた方がよいでしょう.

一気通貫に確認

結論から言うと(私には)見にくくこれでは何とも言えないように思います.

ただ数が少ない場合は単純実装で簡単に確認できるため, まずは単純実装で様子を見ます.

1
2
3
[|0..16|]
|> Array.map (fun i -> sprintf "i = %2d, i%%4 = %d, sum = %2d" i (i%4) ([|0..i|] |> Array.reduce (fun a b -> a^^^b)))
|> Array.iter (printfn "%A")

結果は次の通りです.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
"i =  0, i%4 = 0, sum =  0"
"i =  1, i%4 = 1, sum =  1"
"i =  2, i%4 = 2, sum =  3"
"i =  3, i%4 = 3, sum =  0"
"i =  4, i%4 = 0, sum =  4"
"i =  5, i%4 = 1, sum =  1"
"i =  6, i%4 = 2, sum =  7"
"i =  7, i%4 = 3, sum =  0"
"i =  8, i%4 = 0, sum =  8"
"i =  9, i%4 = 1, sum =  1"
"i = 10, i%4 = 2, sum = 11"
"i = 11, i%4 = 3, sum =  0"
"i = 12, i%4 = 0, sum = 12"
"i = 13, i%4 = 1, sum =  1"
"i = 14, i%4 = 2, sum = 15"
"i = 15, i%4 = 3, sum =  0"
"i = 16, i%4 = 0, sum = 16"

周期性の存在を前提に見れば何とは0と1がポツポツ現われる程度の事情は見えます. プログラムで手を抜いてはいけないようなので具体的に確認します.

具体的に確認

公式解説を前提に次のように具体的に項を2つずつまとめて書いてみます.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
(0)                                                                |> should equal 0
(0^^^1)                                                            |> should equal 1
(0^^^1)^^^(2)                                                      |> should equal 3
(0^^^1)^^^(2^^^3)                                                  |> should equal 0
(0^^^1)^^^(2^^^3)^^^(4)                                            |> should equal 4
(0^^^1)^^^(2^^^3)^^^(4^^^5)                                        |> should equal 1
(0^^^1)^^^(2^^^3)^^^(4^^^5)^^^(6)                                  |> should equal 7
(0^^^1)^^^(2^^^3)^^^(4^^^5)^^^(6^^^7)                              |> should equal 0
(0^^^1)^^^(2^^^3)^^^(4^^^5)^^^(6^^^7)^^^(8)                        |> should equal 8
(0^^^1)^^^(2^^^3)^^^(4^^^5)^^^(6^^^7)^^^(8^^^9)                    |> should equal 1
(0^^^1)^^^(2^^^3)^^^(4^^^5)^^^(6^^^7)^^^(8^^^9)^^^(10)             |> should equal 11
(0^^^1)^^^(2^^^3)^^^(4^^^5)^^^(6^^^7)^^^(8^^^9)^^^(10^^^11)        |> should equal 0
(0^^^1)^^^(2^^^3)^^^(4^^^5)^^^(6^^^7)^^^(8^^^9)^^^(10^^^11)^^^(12) |> should equal 12

周期4を前提に調べましょう.

次の周期です.

次の周期です.

もちろん一気通貫の場合と結果は同じですが, mod 4で何故どんな値が出るかはっきりしました. これをまとめたのが最初の実装です.

ついでに: 数学での実験

念のため書いておくと数学でもこの手の実験・具体例の確認はとても大事です. 具体例を確認した結果をそのまま数学的帰納法で証明に持ち込む単純な場合もあります. もっと言えば面白い具体例, 特に反例ができればそれで論文が書ける場合さえあります. 有名な予想に対して反例を提出して解決して有名になった人もあり, その論文・講演がいまでも語り草になるほどです.

Mr. Counterexampleとして世界的に名を馳せた日本人数学者として永田雅宜がいます. 私の専門だった作用素環でも荒木の場の量子論・量子統計力学からのIII型フォン・ノイマン環の構成や, パワーズによる量子統計力学を媒介にした連続無限個の$\mathrm{III}_{\lambda}$環の構成は特に有名です.