Square869120Contest #3 解説E869120, square1001による有志コンテスト

コンテストの概要

問題数…8問（第1回～3回目まで、全てそう）

制限時間…3時間（第2回と同じ）

Writer…E869120,square1001（これは第1回から変わらないメンバー）

rated…なし

というわけで、Square869120Contest #3はお楽しみいただけたでしょうか。お楽しみ出来たら幸いです。

問題（Overview）

A問題カレンダー

B問題石落としゲーム

C問題XORパズル

D問題お土産購入計画2

E問題円と三角形

F問題寿司

G問題フィボナッチ数の総和

H問題爆弾ゲーム

今回は、この8問について解説をしていきます。

A問題 Calendarsquare869120Contest #3 解説

問題概要

𝑛 × 7のマス目からなるカレンダーがあり, 上から 𝑖 行目, 左から 𝑗 列目のマスには整数 7𝑖 + 𝑗 − 7が書かれている

この中から3×3のマス目を選び, この合計を11で割った余りがちょうど 𝑘 になるようなマス目の選び方は何通りあるか？

問題概要

𝑛 = 7, 𝑘 = 7のとき

Sun. Mon. Tue. Wed. Thu. Fri. Sat.

1 2 3 4 5 6 7

8 9 10 11 12 13 14

15 16 17 18 19 20 21

22 23 24 25 26 27 28

29 30 31 32 33 34 35

36 37 38 39 40 41 42

43 44 45 46 47 48 49

問題概要

𝑛 = 7, 𝑘 = 7のとき

5+6+7+12+13+14+19+20+21=117 (11で割った余りは7)

Sun. Mon. Tue. Wed. Thu. Fri. Sat.

1 2 3 4 5 6 7

8 9 10 11 12 13 14

15 16 17 18 19 20 21

22 23 24 25 26 27 28

29 30 31 32 33 34 35

36 37 38 39 40 41 42

43 44 45 46 47 48 49

問題概要

𝑛 = 7, 𝑘 = 7のとき

16+17+18+23+24+25+30+31+32=216 (11で割った余りは7)

Sun. Mon. Tue. Wed. Thu. Fri. Sat.

1 2 3 4 5 6 7

8 9 10 11 12 13 14

15 16 17 18 19 20 21

22 23 24 25 26 27 28

29 30 31 32 33 34 35

36 37 38 39 40 41 42

43 44 45 46 47 48 49

基本的な考え方

カレンダーの性質上, 選んだ3×3の真ん中のマス目に書かれている整数を 𝑥 とすると, 3×3のところに書かれている整数の和は 9𝑥 となる

これを11で割った余りが 𝑘 であるから, 9𝑥 ≡ 𝑘 𝑚𝑜𝑑 11 を解くと, すべての 𝑘 に対して解が存在し, 𝑥 ≡ 5𝑘 (𝑚𝑜𝑑 11)が解である。

基本的な考え方

3×3のマスの真ん中のマスは, N×7のカレンダーの端ではない (これ以外のマスはすべて真ん中としてあり得る)

よって, 𝑥 = 7𝑖 + 𝑗 − 7 (2 ≤ 𝑖 ≤ 𝑛 − 1, 2 ≤ 𝑗 ≤ 6)で表される。

これは, 𝑥 = 7𝑖 + 𝑗 + 9 (0 ≤ 𝑖 ≤ 𝑛 − 3, 0 ≤ 𝑗 ≤ 4)と変形できる。

よって, この問題の答えは 7𝑖 + 𝑗 + 9 ≡ 5𝑘 𝑚𝑜𝑑 11 を 0 ≤ 𝑖 ≤ 𝑛 − 3, 0 ≤ 𝑗 ≤ 4の範囲で満たす整数の組 (𝑖, 𝑗)の個数である。

部分点解法 (150点)

この小課題は, 1 ≤ 𝑛 ≤ 100を満たす

前ページで説明した範囲を満たす (条件は満たさなくてもよい) 整数の組 𝑖, 𝑗 は,

最大で 5(𝑛 − 2)個

これを全探索することができる

計算量は 𝑂(𝑛)時間

満点解法 (250点)

ここでは, 入力例4 (𝑛 = 100, 𝑘 = 8 の例)について考える

𝑗 = 0のとき

7𝑖 + 9 ≡ 5𝑘 ≡ 40 𝑚𝑜𝑑 11 ⇒ 7𝑖 ≡ 9 𝑚𝑜𝑑 11 (0 ≤ 𝑖 ≤ 𝑛 − 3)となるような 𝑖 を考える

そのとき, 𝑖 = {6, 17, 28, 39, 50, 61, 72, 83, 94}が条件を満たす

𝑗 = 1のとき

7𝑖 + 10 ≡ 5𝑘 ≡ 40 𝑚𝑜𝑑 11 ⇒ 7𝑖 ≡ 8 𝑚𝑜𝑑 11 (0 ≤ 𝑖 ≤ 𝑛 − 3)となるような 𝑖 を考える

そのとき, 𝑖 = {9, 20, 31, 42, 53, 64, 75, 86, 97}が条件を満たす

𝑖 の値に規則性がある？

満点解法 (250点)

𝑗 を固定したとき, 𝑖 は 11𝑞 + 𝑟 (𝑟 は定数) の形で表される

⇒ 0 ≤ 𝑖 ≤ 10の範囲で解は1つだけ存在する (これが 𝑟の値)

これを求めれば, 𝑞 が 0 ≤ 𝑖 ≤ 𝑛 − 3の範囲でいくつ存在するかが分かる

また, 個数は次のようになる

𝑛 − 3 𝑚𝑜𝑑 11 < 𝑟のとき：𝑛−3

11個

𝑛 − 3 𝑚𝑜𝑑 11 ≥ 𝑟のとき：𝑛−3

11+ 1個

これにより, 1つの 𝑗 に対して 𝑂(1)回の計算で求まる

これを 0 ≤ 𝑗 ≤ 4に対してやればよいので, 全体の計算量は 𝑂(1)時間

結果

A問題（カレンダー）のAC者数は⇒⇒⇒

250点者…106人

150点者…57人

First AC…6分11秒

First AC者…uwi

B問題：Falling Stone GameSquare869120Contest #3 解説

問題概要

H*Wのボードがあります。

その中には’1’～’9’の数字の書かれたブロックがあります。

最初、隣り合うマス同士は同じ数字ではないです。

あなたは、1つのブロックを消すことができます。

ブロックは、消された部分を補充するように上から落ちてきます。

問題概要

1 2 4 3

2 1 4 2

1 4 2 3

4 3 1 4

1 2 4

2 1 4 3

1 4 2 2

4 3 1 4

例えば、赤色で示されたマスを消すとき、以下のようにブロックが落ちてきます。

問題概要

また、横にK個以上同じ数字が続いた場合、その数字は消えます。

消えたマスについては、上から補充されるように落ちてきます。

1 2 4

2 1 4 3

1 4 2 2

4 3 1 4

1 2

2 1 4

1 4 4 3

4 3 1 4

問題概要

また、上から落ちてきた後に同じ数字が横にK個以上連続して並ぶセルが存在するとき、連鎖的に消えていきます。

1 2

2 1 4

1 4 4 3

4 3 1 4

1

2 2

1 1 4 3

4 3 1 4

問題概要

さらに消せるところがある場合、3回目以降でも消えることがあります。

1

2 2

1 1 4 3

4 3 1 4

1 4 3

4 3 1 4

問題概要

スコアは、以下のように計算されます。

𝑖回目の消滅で消えた数字の値の総計を𝑝𝑖とするとき、

スコアはσ𝑖=0𝑟−12𝑖 ∗ 𝑝𝑖となります。

ただし、最初の消滅を0回目とし、rは消滅の回数とします。

例えば、前の例の場合、

20 ∗ 2 + 2 + 21 ∗ 4 + 4 + 22 ∗ 2 + 2 + 1 + 1 = 4 + 16 + 24 = 44

よって、場所(2,3)を消したときのスコアは44になります。

問題概要

さて、求めるのは、

最適に消したときスコアいくつ得られるか です。

さあ、求めてみましょう！

満点解法

まず、セルの数はH*W個あるので、それぞれのブロックを消したとき何点得られるか、というのをシミュレーションすることを考えましょう。

まず、1回の消滅について考えます。

まず、消滅を調べるのに計算量HWくらいかかります。⇒次ページへ

次に、消すのに計算量HWくらいかかります。⇒次ページへ

消滅を調べる方法

全ての区間についてHW個すべて愚直に探索すると、計算量HWKかかります。

しかし、K≧4のとき、最初の状態でどこも横に隣り合う2つは同じ数字ではないことがすでに制約から分かっているので、0通りとなります。

よって、探索が必要なのはK≦3の場合のみで、消滅を調べるのにはH*W*定数時間しかかからないことがわかります。

1 3 3 3 2 2 4 1

落とす方法

落とすのは、愚直に1マスずつ落とすと、各列につき最大で計算量𝑊2くらいかかります。

しかし、各列にある要素（空白の部分は含まない）の1番目を1番下、2番目を2番目に下、3番目を3番目に下・・・というふうにすれば、各列につきO(W)で処理できます。

1 2 2 11番目 2番目 3番目 4番目

1 2 2 1

落とす方法

これは、C++だとVectorとかを使うとできます。

Vectorは、要素を入れるときに列の末尾に要素を追加するので、（push_back）これを使うとできます。

ちなみに、このVectorは、幾何的なベクトルではないです。ご注意ください。

𝒂 = 𝒙 + 𝒚 + 𝒛

計算量の解析

まず、連鎖回数が最大で𝑙𝑜𝑔21,000,000,000 = 30回くらい⇒H回くらいという見積もりが立てられる

次に、一回の消滅につき消滅処理がO(HW)、落下処理がO(HW)

消す候補となる箇所はHW個

⇒計算量はHW*H*(HW+HW)=𝑂(𝐻3𝑊2) H=30,W=30のときおよそ2,400万回⇒普通に間に合います。

まとめ

単純に言えば、この問題は実装問題です。

スライドを書いたE869120でもこの問題の実装に50行くらいかかりました。

ちなみに、小課題1は、バグらせた人が部分点を得るために設定されました。

ちなみに、このゲームは私が考案したものですが、CODEVS for STUDENT のゲームに少し似ていると思います。

みなさん、解けたでしょうか？

結果

B問題（石落としゲーム）のAC者数は⇒⇒⇒

300点者…47人

120点者…5人

First AC…15分13秒

First AC者…uwi

おしまい

1 2 3 4 5 1 2

3 4 5 1 2 3 4

5 1 2 3 4 5 1

2 3 4 5 1 2 3

4 5 1 2 3 4 5

1 2 3 4 5 1 2

3 4 5 1 2 3 4

7*7,K=2のとき

・その場合、どこを押してもブロック1個も消滅しません。

・残念ながら、このパズルに当たってしまった受験者は、落ちてしまいます。

・もしそのようなケースがあった場合、’0’と出力するようになっているはずです。

C問題：Solving XOR PuzzlesSquare869120Contest 解説

問題概要

長さNの数列{𝑎1, 𝑎2, 𝑎3, … , 𝑎𝑛}が与えられます。

その数列からいくつか値を取り、それを自由に並べ替えることで数列bを作ります。

𝑏1𝑋𝑂𝑅 𝑏2𝑋𝑂𝑅 𝑏3𝑋𝑂𝑅…𝑋𝑂𝑅 𝑏𝑚=kとなるような数列bの作り方の総数を1,000,000,007で割った余りを求めてください。

ただし、数列bとしてありうる総数は（XORした値がkとは限らない）、σ𝑘=1𝑛 𝑛𝐶𝑘 ∗ 𝑘!であることは自明です。

入力例

N=3,k=1,a={1,2,3}のとき

①b={1}⇒1 = 1

②b={2,3}⇒2 XOR 3 = 1

③b={3,2}⇒3 XOR 2 = 1

の3つの作り方があります。

小課題の確認

小課題1（50点）・・・1≦N≦4

⇒全探索でも通る（絶対）

小課題2（170点）・・・1≦N≦20

⇒𝑂(2𝑛)くらいなら通る

小課題3（180点）・・・1≦N≦100

⇒𝑂(𝑛3)か定数の少ない𝑂(𝑛4)くらいなら許される

まず、XORとは？

XORは、ビット演算に関係する演算子です。

C++では、以下のように打てば a XOR bの値がわかります。

a ^ b

まず、XORとは？

例えば、aを2進数で表した値、bを2進数で表した値が以下のようなとき、

XORは10011を10進数で表した値なので19となります。

単純に言えば、0と1がある位は1になり、それ以外の位は0になるという仕組みになっています。

a 1 0 1 0 1

b 0 0 1 1 0

XOR 1 0 0 1 1

小課題1（50点）

1≦N≦4です。

XORがkとは限らない、全ての数列bの作り方は以下の通り数あります。

4*1+6*2+4*6+1*24=4+12+24+24=64通り

よって、全て列挙して探索するのみで通ります。

単なる数え上げです。

考察1

XORの性質を使って、さらに行けるか考えましょう。

さて、𝑎1𝑋𝑂𝑅 𝑎2というものについて考えましょう。

よく考えてみると、𝑎1𝑋𝑂𝑅𝑎2=𝑎2𝑋𝑂𝑅 𝑎1が常に成り立ちます。

⇒この性質が成り立つ理由は次ページへ

考察1

まず、aの2進数での各位を𝑐0, 𝑐1, 𝑐2,・・・とします。

また、bの2進数での各位を𝑑0, 𝑑1, 𝑑2・・・とします。

そうすると、

a XOR bの2進数での各位は、(𝑐𝑖 + 𝑑𝑖)となり、

b XOR aの2進数での各位は、(𝑑𝑖 + 𝑐𝑖)となります。

その2つの値は常に同じなので、𝑎 𝑋𝑂𝑅 𝑏 = 𝑏 𝑋𝑂𝑅 𝑎がいえます。

考察1

そこで、3つ以上のXORについて考えます。

これは、再帰的に以下のことが分かります。

𝑎 𝑋𝑂𝑅 𝑏 𝑋𝑂𝑅 𝑐 = 𝑎 𝑋𝑂𝑅 𝑐 𝑋𝑂𝑅 𝑏 = 𝑏 𝑋𝑂𝑅 𝑎 𝑋𝑂𝑅 𝑐 = 𝑏 𝑋𝑂𝑅 𝑐 𝑋𝑂𝑅 𝑎 =𝑐 𝑋𝑂𝑅 𝑎 𝑋𝑂𝑅 𝑏 = 𝑐 𝑋𝑂𝑅 𝑏 𝑋𝑂𝑅 𝑎

また、4つ以上においてもすべての順列でXOR値が同じという事が言えます。

よって、XORする数列の長さがpであり、𝑏1𝑋𝑂𝑅 𝑏2𝑋𝑂𝑅…𝑏𝑝 = 𝑘を満たしていれば、通り数に𝑝!通りが足されることが分かります。

小課題2（220点）

そうすると、あとは数列aから何を取り出すかということになります。

取り出し方は、それを取り出すか取り出さないかということになるので、2𝑛通りあります。

また、各取り出し方につき1通りのXOR値を求めるのにO(n)かかるので、全体の計算量は

𝑂(2𝑛 ∗ 𝑛) となります。n=20のとき、約2000万となり、間に合います。

考察2

小課題3の制約は、n≦100です。

しかし、数列の長さが同じであれば、掛ける数（階乗）も同じなので、数列の長さごとに数え上げしていくという方法もできます。

また、順序が関係ないので、動的計画法で解けそうです。

記録しておかなければならないのは、現在どこまで見たか、現在のXOR値、さっき言った現在の数列の長さの3つです。

⇒3次元動的計画法で解けます！

小課題3（400点）

まず、dp[現在の位置][XOR値][現在の数列の長さ]の配列を用意します。

だいたいdp[100][256][100]くらいになります。

また、この状態からの選択肢は

①この数字を取る

②この数字を取らない

の2つです。⇒定数時間でできます。

答えは、σ𝒊=𝟏𝒏 (𝒅𝒑 𝒏 𝒌 𝒊 ∗ 𝒊!)ということになります。

小課題3（400点）

計算量の解析をします。

まず、最大の数列の値=256ですが、これをWとします。

また、3次元配列の1個目の値の最大値がn、3個目も同じくnとなるので、計算量は以下のようになります。

また、1つの状態での処理は定数時間でできるので、O(1)です。

𝒏 ∗ 𝒏 ∗𝑾 = 𝑶(𝒏𝟐𝑾)となり、間に合います。

ちなみに、Writer解は50msくらいです。

結果

C問題（XORパズル）のAC者数は⇒⇒⇒

400点者…55人

220点者…18人

50点者…5人

First AC…12分19秒

First AC者…nuip

おしまい

101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101101101001111001110101100101011110110000100010010001010011110011001100101001001000100010111100101001010101

XOR

D問題 Souvenirssquare869120Contest #3 解説

問題概要

H×Wのマス目があり, いくつかのマスにはお土産がある

E869120, square1001の2人で協力してお土産をたくさんゲットしよう！

ただし, 2人は左上から右下まで最短経路で移動しなければならない

制約

1 ≤ 𝐻,𝑊 ≤ 200

問題概要

例えば, 入力例1の場合次のように移動すればOK

小課題1の解法 (50点)

𝐻 = 2のとき, E869120が1行目, square1001が2行目をすべて通れば, 2人ですべてのマスを通ることができる

イメージとしてはこのような感じ

小課題1の解法 (50点)

これと, 𝑎𝑖,𝑗 ≥ 0より, すべてのマスを通った時が最大となる

よって, 答えは σ𝑎𝑖,𝑗 となる

計算量は 𝑂(𝑊)

小課題2の解法 (80点)

この小課題は, 𝐻 = 3を満たす

このとき, E869120の進み方は, 2回下に進み, 𝑊 − 1回右に進むことより, 𝑊+12

通りの進み方がある

square1001の進み方も同じく 𝑊+12通りあるので, 合計で通り数は 𝑊+1

2

2=

1

4𝑊2 +𝑊 2 通りある

小課題2の解法 (80点)

各進み方に対し, お土産を何個買うことができるかを 𝑂(𝑊)で求めることができる

⇒全体の計算量は 𝑂 𝑊5

累積和を使えば 𝑂(1)で求めることができる

⇒全体の計算量は 𝑂 𝑊4

𝑊 = 200を代入すると, 計算量は 1.6 × 109 となり, 間に合わない

小課題2の解法 (80点)

実は, この問題に対して, 以下のことが成立する

𝐻 ≥ 2かつ𝑊 ≥ 2のとき,最適解のうち1つは, 必ずスタートとゴール以外で出会わない

理由は考えたらわかると思うので, ここでは飛ばします。

小課題2の解法 (80点)

このことより, E869120は最初に下に進み, 最後に右に進み, また, square1001は最初に右に進み, 最後に下に進むことで最適解が得られることがわかる。

これより, E869120, square1001のそれぞれの動き方は 𝑊−11

= 𝑊 − 1通りであ

り, 合計の動き方でも 𝑊 − 1 2 = 𝑂(𝑊2)通りに絞れることがわかった。

この方法だと, 普通に計算しても 𝑂 𝑊3 しかかからないので, 計算量は𝑊 = 200でも 8 × 106 であり, 時間に間に合う

小課題3の解法 (120点)

この小課題は, 𝐻 ≤ 7,𝑊 ≤ 7を満たす

1人の動き方は 𝐻+𝑊−2𝐻−1

だから, 2人の動き方は 𝐻+𝑊−2𝐻−1

2

𝐻 = 𝑊 = 7のときでも, 853776通り

⇒全探索で間に合いそう？

小課題3の解法 (120点)

これは, 深さ優先探索 (DFS) という方法を使えば探索することができる。

※わからない人は蟻本などの本を使って調べてみましょう！

また, 1個の状態につき最大でも4つにしか遷移しないので, 計算量は853776×4=3400000くらい

よって, 𝐻 ≤ 7,𝑊 ≤ 7のとき現実的な時間で解くことができる

小課題4の解法 (150点)

この小課題は, 𝐻 ≤ 30,𝑊 ≤ 30を満たす

小課題3を解く方法だと, 𝐻 = 30,𝑊 = 30のとき 9.04 × 1032 通りくらい状態があるので, 現実的な時間で解くことができない

小課題4の解法 (150点)

これを解決するために, 「動的計画法 (DP)」というテクニックを使います。

※これが分からない人は蟻本などを見てマスターしましょう。

小課題4の解法 (150点)

先ほど説明したように, 「動的計画法」を使って解く

まず, DFSで実装する際に, 𝑑𝑓𝑠(𝑒𝑥, 𝑒𝑦, 𝑠𝑥, 𝑠𝑦)を呼び出すことにする。これは,

E869120が座標 (𝑒𝑥, 𝑒𝑦)に, square1001が座標 (𝑠𝑥, 𝑠𝑦)にいるときに, お土産が何個もらえるかを返す関数とする

そのとき, 今までに通った道順にかかわらず, 𝑑𝑓𝑠(𝑒𝑥, 𝑒𝑦, 𝑠𝑥, 𝑠𝑦)の値は(𝑒𝑥, 𝑒𝑦, 𝑠𝑥, 𝑠𝑦)が変わらなければリターン値も変わらない

小課題4の解法 (150点)

再帰関数を書く際に, 同じ (𝑒𝑥, 𝑒𝑦, 𝑠𝑥, 𝑠𝑦)が何度も呼び出されている

一度通ったらこの値をメモしてもう一度通ったときにこの値を返せば, 計算量は減る！ (メモ化再帰)

メモは, 𝑑𝑝 𝑒𝑥 𝑒𝑦 𝑠𝑥 [𝑠𝑦]でうまくやるといけそう

結果として, 探索する状態数は 𝐻2𝑊2 個である

計算量は 𝑂 𝐻2𝑊2

𝐻 = 30,𝑊 = 30を代入しても, 計算量は 8.1 × 105 回程度となり, 定数が大きくても通る可能性が高い

満点解法 (600点)

𝑑𝑝 𝑒𝑥 𝑒𝑦 𝑠𝑥 [𝑠𝑦]と記録すると, 𝐻 = 200,𝑊 = 200のとき AC できない

どのように工夫すればよいか？

実は, 𝑒𝑥 + 𝑒𝑦 = 𝑠𝑥 + 𝑠𝑦であるから, 無駄に配列を作らずに, 𝑑𝑝 𝑒𝑥 𝑠𝑥 [𝑒𝑥 + 𝑒𝑦]とやればよさそう

満点解法 (600点)

よって, 探索する状態数は 𝑂 𝐻𝑊 𝐻 +𝑊 とわかる

𝐻 = 200,𝑊 = 200なので, 計算量が 1.6 × 107 となる

⇒定数が大きくなければ, ACする可能性が高い

これで, この問題の解説は終わりです。

結果

D問題（お土産購入計画2）のAC者数は⇒⇒⇒

600点者…37人

400点者…6人

250点者…2人

130点者…1人

50点者…12人

First AC…18分10秒

First AC者…kyuridenamida

E問題：円と三角形Square869120Contest #3 解説

問題概要

半径が1の円があります。

その中にN個の点があり、円周上をN等分しています。

それらの点を使って三角形を作ります。

その時、面積順にソートしてK番目に来る三角形の面積を求めてください。

ただし、絶対誤差または相対誤差は10−9まで許される。

問題概要

例えば、N=6,K=9のとき、

面積 通り数

0.433012… 6個

0.866025… 12個

1.299038… 2個

ということになり、9番目の面積は0.866025…となります。

この面積になる三角形として、頂点番号(1,3,4)から成り立つ三角形などが挙げられます。

問題概要

小課題1（160点）

⇒N≦100を満たす。

小課題2（240点）

⇒N≦1,000を満たす。

小課題3（450点）

⇒N≦60,000を満たす。

小課題1（160点）

まずは、作れる三角形の通り数について考えてみましょう。

これは、N個の点から3つを選ぶので、NC3=N*(N-1)*(N-2)/6となります。

⇒N=100のとき、161,700通り

よって、これを全探索すると間に合うはずです。

※N=1,000の場合、約1.6億通りあります。

小課題1（160点）

また、各三角形の面積は以下のように求められます。

①点iの座標⇒x座標=sin(360.0*i/n), y座標=cos(360.0*i/n)

②点a(ax,ay), 点b(bx,by)の距離⇒sqrt((bx-ax)*(bx-ax)+(by-ay)*(by-ay))

③3辺の長さがa,b,cの三角形の面積

⇒(a+b+c)/2=pとするとき

⇒sqrt(p*(p-a)*(p-b)*(p-c)) = 面積S

ヘロンの公式

小課題1（160点）

例えば下図の三角形の面積は、以下のような式によって約1.21と求められます。

点1の座標⇒(0.0,1.0)

点4の座標⇒(0.7,-0.7)

点7の座標⇒(-1.0,0.0)

(a+b+c)/2 = (1.84+1.41+1.84)/2 ≒ 2.55p*(p-a)*(p-b)*(p-c)

⇒2.55*0.71*1.14*0.71 ≒ 1.465

dist(1,4)⇒sqrt((0.7-0.0)^2 + (1.0+0.7)^2) = sqrt(3.38) ≒ 1.84 ⇒ aとするdist(1,7)⇒sqrt((0.0+1.0)^2+ (1.0-0.0)^2) = sqrt(2.00) ≒ 1.41 ⇒ bとするdist(4,7)⇒sqrt((0.7+1.0)^2+ (0.0+0.7)^2) = sqrt(3.38) ≒ 1.84 ⇒ cとする

面積は、sqrt(1.465) ≒ 1.210

小課題1（160点）

このアルゴリズムでは、O(N^3)計算にかかります。

⇒小課題1だと通ります（N≦100）

⇒小課題2だと、1000*1000*1000=10億になるので、制限時間4秒には間に合いません。つまり、より効率的な解法を考える必要があります。

なお、一回sqrtを計算するのにlog(n)時間かかるので、実際はもう少し時間がかかります。（大体20倍くらいと見ていいです）

小課題2（400点）

実際には、もっと効率的な解法というのは存在します。

いろいろと考察をしてみましょう。

①そうすると、n^3通り全列挙した時に（順番問わず）、できる三角形の数は、ここで数えられた数÷6であることがわかります。

例えば左図の場合、(1,4,7)、(1,7,4)、(4,1,7)、(4,7,1)、(7,1,4)、(7,4,1)の6つの三角形が同じとして数えられます。

小課題2（400点）

②また、面積は回転させても同じになります。

例えば、左図の三角形を回転させて、各頂点番号が(2,5,8)や(3,6,1)などになるようにしても、面積は変わりません。

⇒①、②より、頂点のうち1つが頂点番号1になるように三角形の配置を全探索して、面積順にソートしてみるとできそうです。

例えば、右図の場合頂点番号のうち1つ目が1であるという条件は満たします。

小課題2（400点）

例えば、頂点数が4の場合、頂点番号1を使うのは以下の3通りです。

また、それぞれのパターンに回転が数えられるので、各パターンは4通りあるということがわかります。

例えば、頂点番号(1,2,3)のパターンは、他に(2,3,4),(3,4,1),(4,1,2)があります。

それで、全ての4*3*2=24通りが全列挙できたはずです。

ちなみに、順番を問わないとしたら3*2=6通りになります。

小課題2（400点）

また、ダブリは6個あるが、回転でパターンが1/n個に削減されるので、単純に言えば K*6/n番目（小数点以下切り上げ）に来るものの面積が答えになります。

例えば、このパターンの場合、（K=3）：K*6/n=4.5となり、切り上げて5です。

この場合、面積順にソートして5番目なので、丸で囲まれた図形の面積を出力させればいいだけです。

ただし、この図は全て面積が同じですが、ソートされているとみなします。

小課題2（400点）

今回は、頂点番号1を含む場合全てを全列挙して、ある数をかけた番目の面積を出力させるという方法でやりました。

計算量は、頂点1の他に2つ頂点があるので、O(N^2)となります。

sinやcos、sqrt等を計算するのにO(log n)かかるので、全体としての計算量はO(n^2 log n)となります。

そうすると、N=1,000のとき計算量は約2000万となり間に合いますが、

N=60,000のときは計算速度の早いAtcoderでも間に合いません。

小課題3（850点）

小課題3を実装する前に、考察をします。

小課題2を実装する際に、N^2通りを全列挙しました。そして、ある数（6/nとか）で掛けました。

そのとき、面積がp以下である三角形の個数を求めることを考えます。

それができれば、あとはpについて二分探索をして、ちょうどK個となるところを目指していくだけです。

小課題3（850点）

面積がp以下である三角形の個数についてです。

まず、1つ目の頂点は頂点1として、2つ目の頂点を全探索(N個)することを考えます。

そうすると、3個目の点が2つの頂点で構成される線分の右側に来るとき、3つ目の頂点を時計回りに移動させると面積は凸型のグラフを描きます。

左側についても同じです。

⇒これに関する考察は次ページ以降へ

小課題3（850点）

グラフが凸関数を描くのであれば、どの範囲が条件を満たすか、左端と右端は二分探索で求められるので、log(n)時間で処理できます。

これは、3つ目の頂点として考えられ、そのうち面積がp以下になるものをlog(n)

時間で計算できることを意味します。

つまり、面積がp以下になる、頂点番号1を含む三角形の個数は、O(n log(n))で求められることがわかります。

⇒間に合いそう！？

小課題3（850点）

そこで、計算量の解析をします。

まず、面積がp以下である三角形の個数を求めるのにO(n log(n))

次に、上記のものを求める回数はlog(n)回くらい

次に、sqrtなどを求めるのにかかる時間はlog(n)くらい

よって、O(n log(n)*log(n)*log(n)) = O(n log^3(n))となります。

n=60,000のとき、約2.5億くらいになるので、定数がきついです。

⇒もう少し定数を軽くする方法は存在します。

小課題3（850点）

計算をする際に、よく「sin」や「cos」という関数を使います。

実際、sinやcosを計算する角度は、2*n種類しか存在しません。

⇒前処理として記録します！

そうすると、二分探索（中側）の中でのsin,cosの利用がなくなったので、かなり定数が軽くなったと思われます。

それで自分が実装してみると、約1,200msecで通りました。制限時間は4秒なので、たぶん通ります。

結果

E問題（円と三角形）のAC者数は⇒⇒⇒

850点者…6人

400点者…4人

160点者…7人

First AC…56分28秒

First AC者…uwi

おしまい

これは、三角形の具体例を示した図です。

F問題寿司square869120Contest #3 解説

問題概要

整数 𝑁,𝑄 が与えられる。長さ 𝑁 の数列 𝑐 の初期値はすべて 0である。

次のようなクエリを 𝑄回処理する

𝑖個目のクエリについて, 次のようになる

𝑐1, 𝑐2, 𝑐3, … , 𝑐𝑎𝑖 の中で最小の値 (複数あれば最も左にあるもの) に1を加算する

これを 𝑏𝑖 回繰り返す

最終的な 𝑐1, 𝑐2, 𝑐3, … , 𝑐𝑁 の値を求めなければならない

問題概要

制約

𝑁 ≤ 100000

𝑄 ≤ 100000

問題概要

例えば, 𝑁 = 6, 𝑄 = 3のとき

𝒄𝟏 𝒄𝟐 𝒄𝟑 𝒄𝟒 𝒄𝟓 𝒄𝟔

0 0 0 0 0 0

問題概要

例えば, 𝑁 = 6, 𝑄 = 3のとき

クエリ1：𝑎1 = 4, 𝑏1 = 14

𝒄𝟏 𝒄𝟐 𝒄𝟑 𝒄𝟒 𝒄𝟓 𝒄𝟔

4 4 3 3 0 0

問題概要

例えば, 𝑁 = 6, 𝑄 = 3のとき

クエリ2：𝑎2 = 3, 𝑏2 = 5のとき

𝒄𝟏 𝒄𝟐 𝒄𝟑 𝒄𝟒 𝒄𝟓 𝒄𝟔

6 5 5 3 0 0

問題概要

例えば, 𝑁 = 6, 𝑄 = 3のとき

クエリ3：𝑎3 = 6, 𝑏2 = 4のとき

𝒄𝟏 𝒄𝟐 𝒄𝟑 𝒄𝟒 𝒄𝟓 𝒄𝟔

6 5 5 3 2 2

小課題1の解法 (60点)

小課題1の制約は, 𝑁 ≤ 100, 𝑄 ≤ 100, 𝑏𝑖 = 1

実際に問題文の通りにやると, 1つのクエリにつき計算量は 𝑂(𝑏𝑖𝑁)であるから, 全体の計算量は 𝑂 σ𝑏𝑖 × 𝑁

この計算量だと, 小課題1には通ることが確かめられる

小課題2の解法 (400点)

小課題2の制約は, 𝑁 ≤ 100, 𝑄 ≤ 100, 𝑏𝑖 ≤ 1012

⇒小課題1の解法では, 𝑏𝑖 が大きいため通らない

ここで, どのような方法を使えばよいのか？

1つのクエリに対する 𝑏𝑖 回の処理をまとめてやることを考える

小課題2の解法 (400点)

まず, どの状態に対しても, 数列 𝑐 が広義単調減少であることが証明できる (ここでは証明はカットします)

これより, 「𝑐𝑥 またはそれより左の値を変化させるために最低でもどのくらいの𝑏𝑖 が必要なのか」を 𝑂 𝑁 で求めることができる

実際に, この値は 𝑎 − 𝑥 + 1 × 𝑐𝑥 − σ𝑘=𝑥𝑎 𝑐𝑘 とかで求められる

このような 𝑥 を二分探索すれば, 𝑂(𝑁 log𝑁)で 𝑥 を決定することができる

小課題2の解法 (400点)

𝑥 を決定したところで, どのように変化させるのかも簡単な方法で求めることができる

イメージとしてはこんな感じ (高さを決定すればいけそう)

小課題2の解法 (400点)

右端の高さは, σ𝑥𝑎𝑖 𝑐𝑖+𝑏𝑖

𝑎−𝑥+1という感じになるので, うまくやれば, 足す処理も 𝑂(𝑁)

でできそう

よって, 1つのクエリに対して：

𝑥 の値を決める => 𝑂(𝑁 log𝑁)

値を足す => 𝑂(𝑁)

これより, 全体の計算量は 𝑂(𝑄𝑁 log𝑁) となるので, 小課題2には通る

小課題3の解法 (240点)

小課題3の制約は, 𝑁 ≤ 100,000, 𝑄 ≤ 100,000, 𝑏𝑖 = 1

この小課題は, 値を足す位置を2分探索で求めてやればよい

よって, 計算量は 𝑂(𝑄 log𝑁)となり, 小課題3に通る

満点解法 (1200点)

小課題4の制約は, 𝑁 ≤ 100,000, 𝑄 ≤ 100,000, 𝑏𝑖 ≤ 1012 である

ここで, 小課題2の解法について考えてみよう

ここでは1つのクエリについて考える

1. 𝑐𝑖 を求める： 𝑂(log𝑁) 回

2. 𝑐𝑖 + 𝑐𝑖+1 +⋯+ 𝑐𝑗 を求める： 𝑂(log𝑁) 回

3. 𝑐𝑖 , 𝑐𝑖+1, … , 𝑐𝑗 に 𝑓 を代入する： 2回

満点解法 (1200点)

ここで, 1つめの操作は, 2つめの操作の 𝑖 = 𝑗の場合なので, 2つめの操作に置き換えることができる

よって, 次のような処理ができるデータ構造が実装できれば良い

A：𝑐𝑖 , 𝑐𝑖+1, … , 𝑐𝑗 に 𝑓を代入する

B：𝑐𝑖 + 𝑐𝑖+1 +⋯+ 𝑐𝑗 を求める

満点解法 (1200点)

このようなデータ構造は, 遅延評価セグメント木を使えば実装できる

分からない人は, 次のページを見てください

kyuridenamida -僕のセグメントツリーの使い方

mayoko - square869120Contest #2 H問題解説

これより, A, B 両方のクエリが 𝑂(log𝑁)で処理できることが分かった

よって, この問題は 𝑂(𝑄 log2𝑁)で解くことが可能である

⇒すべてのテストケースに AC！

別解

実際、この問題には別解があります。

新しく作る区間の数は最大で2個です。

最初にある区間の数は1個です。

よって、「区間をつくる」＋「区間を消す」操作の合計数は最大でもQについて線形の回数であることが分かります。

そこで、全ての区間を配列に記録しておくことを考えます。

別解

まず、開始地点を二分探索で求めます。

そして、どこまで寿司を配れるかを、計算で求めます。

別解

区間を配列に記録するのに、「探索」「挿入」「削除」の3つの操作が必要なので、二分探索木を使えばできます。

ただし、コーナーケースもあるので平衡二分探索木を使いましょう。

よって、この問題は、𝐿𝑎𝑧𝑦𝑆𝑒𝑔𝑚𝑒𝑛𝑡𝑇𝑟𝑒𝑒・二分探索木のどちらの方法でも解くことができます。

結果

F問題（寿司）のAC者数は⇒⇒⇒

1200点者…19人

700点者…0人

460点者…3人

300点者…7人

60点者…7人

First AC…40分11秒

First AC者…yutaka1999

G問題フィボナッチ数列の和square869120Contest #3 解説

問題概要

フィボナッチ数列 𝑎1 = 𝑎2 = 1, 𝑎𝑘+2 = 𝑎𝑘+1 + 𝑎𝑘 がある

それを使って, 次のような数列 𝑑1, 𝑑2, 𝑑3, … 𝑑𝑛 を作る

𝑑1,𝑖 = 𝑎𝑖

𝑑𝑖,𝑗 = σ𝑘=1𝑗

𝑑𝑖−1,𝑘

整数 𝑛,𝑚が与えられるとき, 𝑑𝑛,𝑚を 998244353で割った余りを求めなさい

問題概要

制約

1 ≤ 𝑛 ≤ 2 × 105

1 ≤ 𝑚 ≤ 1018

問題概要

例えば, 𝑛 = 4,𝑚 = 7のとき

よって, 答えは 176 になる

𝒅𝒊,𝟏 𝒅𝒊,𝟐 𝒅𝒊,𝟑 𝒅𝒊,𝟒 𝒅𝒊,𝟓 𝒅𝒊,𝟔 𝒅𝒊,𝟕

1 1 2 3 5 8 13

1 2 4 7 12 20 33

1 3 7 14 26 46 79

1 4 11 25 51 97 176

小課題1の解法 (100点)

この小課題の制約は, 1 ≤ 𝑛,𝑚 ≤ 3000

まず, 問題文の通りにやってみることを考える

このとき, 𝑑𝑖,𝑗 を求めるときに 𝑂(𝑗)の計算量が必要

⇒全体の計算量は 𝑂(𝑛𝑚2)

⇒ 𝑛,𝑚 = 3000のとき, TLEをしてしまう

小課題1の解法 (100点)

ここで, 「累積和」を使うことを考える

まず, 数列 𝑑𝑖−1 を使って数列 𝑑𝑖 を求めることを考える

そのとき, 次のようなことが成り立つ

𝑑𝑖,1 = 1

𝑑𝑖,𝑗 = σ𝑘=1𝑗

𝑑𝑖−1,𝑘 = 𝑑𝑖−1,𝑗 + σ𝑘=1𝑗−1

𝑑𝑖−1,𝑘 = 𝑑𝑖−1,𝑗 + 𝑑𝑖,𝑗−1

よって, 数列 𝑑𝑖 は数列 𝑑𝑖−1 を使えば 𝑂(𝑚)で求めることができる

この問題は, 𝑂(𝑛𝑚)で解くことができる

⇒小課題1には通る (200点)

小課題2の解法 (170点)

この小課題の制約は, 1 ≤ 𝑛,𝑚 ≤ 100,000である

⇒小課題1の解法だと通らない

そのとき, どのような方法を使えばよいのか？

小課題2の解法 (170点)

ここで, 𝑑𝑖,𝑗 = 𝑑𝑖−1,𝑗 + 𝑑𝑖,𝑗−1 という漸化式に注目してみよう

この式は, H×Wのグリッド上を (1, 1) から (H, W) まで最短経路で移動する経路数を求める漸化式とすごく似ている

また, これは 2項係数を用いることで簡単に解くことができそう！？

※2項係数について

分からない人は ABC 034 C問題：経路を解きましょう

2項係数 𝑛𝑘は 𝑂 𝑛 時間で求めることができ, 𝑂 𝑛 の前処理をすると 1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤

𝑛に対して 𝑂(1)で求めることができる

小課題2の解法 (170点)

実際に, 式を展開してみると…

𝑑4,4 = 𝑑3,4 + 𝑑3,3 + 𝑑3,2 + 𝑑3,1

= 𝑑2,4 + 2𝑑2,3 + 3𝑑2,2 + 4𝑑2,1

= 𝑑1,4 + 3𝑑1,3 + 6𝑑1,2 + 10𝑑1,1

= 22𝑎4 +

32𝑎3 +

42𝑎2 +

52𝑎1

小課題2の解法 (170点)

ここで, 𝑑𝑖,1 の係数が本当に52になるかどうかを確かめる

下の図を見る限り, 2×3のマス目を左上から右下まで最短経路で進む動き方と同じ

になるので, 52と等しくなることはすぐにわかる

𝒅𝒊,𝟏 𝒅𝒊,𝟐 𝒅𝒊,𝟑 𝒅𝒊,𝟒

1 1 2 3

1 2 4 7

1 3 7 14

1 4 11 25

小課題2の解法 (170点)

よって, 𝑑𝑖,𝑗 = σ𝑘=1𝑗 𝑖−2+𝑗−𝑘

𝑖−2× 𝑎𝑘 である

2項係数は前処理に 𝑂(𝑛 +𝑚)かけるとそれぞれ 𝑂(1)で求めることができるので,

計算量は 𝑂 𝑛 +𝑚

⇒小課題2には通る

実際に, この考え方を使うと, square869120Contest #2: F – Range Sum

Queries で 60点を取ることができる

ぜひこちらも解いてみましょう！

https://s8pc-2.contest.atcoder.jp/tasks/s8pc_2_f

小課題3の解法 (230点)

この小課題は, 1 ≤ 𝑛 ≤ 3を満たす

まず, 𝑛 = 1の場合を考えてみよう

𝑛 = 1のとき, フィボナッチ数列の第 𝑚項が求められていればよい

どのように求めればよいか？

小課題3の解法 (230点) / n=1のとき

これは, 「行列累乗」という方法を使えば解ける

Wikipediaのページを見ればたぶん理解できると思います

よって, 𝑂(log𝑚)で求めることができる

小課題3の解法 (230点) / n=2のとき

次に, 𝑛 = 2のときについて考える

実際に, 𝑑2,𝑖 = 𝑎𝑖+2 − 1になることが分かる

※このページを見ればわかると思います

よって, 計算量は 𝑂(log𝑚)となる。

小課題3の方法 (230点) / n=3のとき

次に, 𝑛 = 3のときについて考える

実際に, 𝑑3,𝑖 = 𝑎𝑖+4 − (𝑖 + 3)が成立する

証明は, 𝑛 = 2のときと同じようにすればできる

よって, 計算量 𝑂(log𝑚)で解くことができる

これより, 𝑛 = 1, 2, 3のときすべて𝑂(log𝑚)で解けることが分かった

小課題4の解法 (420点)

この小課題は, 𝑛 ≤ 1000を満たす

小課題3の方法を工夫してできないか？

小課題4の解法 (420点)

ここで, 次のようなことが成立する

𝑑1,𝑖 = 𝑎𝑖

𝑑2,𝑖 = 𝑎𝑖+2 − 1

𝑑3,𝑖 = 𝑎𝑖+4 − (𝑖 + 3)

𝑑4,𝑖 = 𝑎𝑖+6 −1

2(𝑖2 + 7𝑖 + 16)

𝑑5,𝑖 = 𝑎𝑖+8 −1

6(𝑖3 + 12𝑖2 + 59𝑖 + 126)

小課題4の解法 (420点)

そこで, 次のようなことが分かる

𝑑𝑛,𝑚 = 𝑎𝑚+2𝑛−2 − 𝑃 𝑚 (deg 𝑃 ≤ 𝑖 − 2)となるような多項式 𝑃が 1 つ存在する

この多項式を求めてみよう！

小課題4 の解法 (420点)

ここで, 「多項式補間」について説明する。

多項式補間とは, 𝑛個の点をすべて通る 𝑛 − 1次以下の多項式 𝑃(𝑥)を求めることであり, 次のようなアルゴリズムが考えられる

Newton補間：𝑂 𝑛2 のアルゴリズムで, 多項式を 𝑎𝑛𝑥𝑛 + 𝑎𝑛−1𝑥

𝑛−1 +⋯+ 𝑎0𝑥0 の

形式で表すことができる。

Lagrange補間：この方法を用いると, 𝑂 𝑛 の前処理で 𝑥 が与えられたときに𝑂(𝑛)で 𝑃(𝑥)の値を求めることができる。

Lagrange補間は, ARC 033 D：見たことのない多項式の解説に載っているので,

これを見るといいと思います。

小課題4の解法 (420点)

多項式 𝑃(𝑥)を求めることを考えると, deg 𝑃 𝑥 ≤ 𝑛 − 2であることから, 𝑃 1 , 𝑃 2 , … , 𝑃(𝑛 − 1)の値を求めてやればOK

そこで, 𝑑𝑛,𝑖 = 𝑎𝑖+2𝑛−2 − 𝑃(𝑖)より, 𝑃 𝑖 = 𝑎𝑖+2𝑛−2 + 𝑑𝑛,𝑖 である

ここで, 𝑎2𝑛−1, 𝑎2𝑛, … , 𝑎3𝑛−3 の値は, 𝑂(𝑛)で求められる

また, 小課題2の方法を使えば, 𝑑𝑛,1, 𝑑𝑛,2, … , 𝑑𝑛,𝑛−1 の値は, 𝑂 𝑛2 で求められる

よって, 𝑃 1 , 𝑃 2 , … , 𝑃(𝑛 − 1)の値は 𝑂(𝑛2)で求められる

また, Lagrange補間を使うと, 𝑃(𝑚)の値が 𝑂(𝑛)で求められる

最後に, 𝑎𝑚+2𝑛−2 の値を 𝑂(log𝑚)で求めれば, 𝑑𝑛,𝑚 の値が求まる

全体の計算量は 𝑂(𝑛2 + log𝑚)

⇒小課題4には通る

満点解法 (1400点)

問題点は, 𝑑𝑛,1, 𝑑𝑛,2, … , 𝑑𝑛,𝑛−1 の値を, 𝑂 𝑛2 で求めていることなので, この計算速度を速くしたい

そこで, 𝑏𝑘 =𝑛−1+𝑘𝑛−1

とすると, 𝑑𝑛,𝑗 = σ𝑘=1𝑗 𝑛−1+𝑗−𝑘

𝑛−1× 𝑎𝑘 = σ𝑘=1

𝑗𝑎𝑘𝑏𝑗−𝑘 である

結果的に, 多項式 𝐴 = 𝑎𝑘𝑥𝑘 + 𝑎𝑘−1𝑥

𝑘−1 +⋯+ 𝑎1𝑥1 , 𝐵 = 𝑏𝑘−1𝑥

𝑘−1 + 𝑏𝑘−2𝑥𝑘−2 +

⋯+ 𝑏0𝑥0 とおくと, 𝐷 = 𝐴𝐵 としたときに 𝑖 次の係数が 𝑑𝑛,𝑖 と等しくなる

また, 𝑛次多項式の乗算は, 𝑚𝑜𝑑 998244353なので NTTという方法 (高速フーリエ変換を少し応用した方法) を使うことによって 𝑂(𝑛 log 𝑛)で求めることができる

NTTの実装は, mathさんのブログを見てください。

よって, 全体の計算量は 𝑂(𝑛 log 𝑛 + log𝑚 )

⇒すべてのテストケースに正解 (AC) ！

満点解法 (1400点)

今回使ったアルゴリズムは, 行列累乗, Lagrange補間, NTT の3つの数学的アルゴリズムです。

このように, たくさんのアルゴリズムを使って解くのは, 素晴らしいと思います。

これで, G問題：フィボナッチ数列の和の解説を終わります。

結果

G問題（フィボナッチ数の総和）のAC者数は⇒⇒⇒

1400点者…4人

920点者…2人

500～750点者…3人

230～330点者…5人

100点者…13人

First AC…80分01秒

First AC者…koba

H問題：爆弾ゲームSquare869120Contest #3

問題概要

50*50のフィールドがあります。

その中に250個の爆弾が置かれています。

あなたは、ある区間にある爆弾の数を聞くことができます。

応答型で、質問してきた区間にある爆弾の数を返します。

爆弾250個がどこにあるか、フィールドの状態を求めてください。

問題概要

この問題は、得点計算がとても複雑です。

質問回数をQとするとき、

・930≦Q≦2500⇒max(125 − 3.2 𝑄 − 920, 40)

・880≦Q≦930⇒288 − 22 𝑄 − 870

・100≦Q≦880⇒max(300,2860 − 3𝑄)

問題概要

というわけですが、配点表は単純に言えば以下のようになります。

平均質問回数 得点合計

2500 200

2000 200

1750 200

1500 261

1300 334

1200 378

1100 429

1000 498

平均質問回数 得点合計

980 516

960 537

940 562

930 578

920 599

910 691

905 740

900 793

平均質問回数 得点合計

895 850

890 913

885 985

880 1071

875 1175

870 1250

865 1325

860 1400

解法1（200点）

まず、最初の解法を説明します。

これは、区間(X,Y,X,Y)※0≦X,Y≦49に対して爆弾の数が1か0かを聞けば、全ての場所が求まります。

例えば、区間(4,6,4,6)にある爆弾の数が1個の場合、ここに爆弾があることが分かります。

また、区間(2,4,2,4)にある爆弾の数が0個の場合、ここに爆弾がないことが分かります。

よって、全てのマスの個数は50*50=2500回なので、質問回数は2500回となります。

⇒得点：200点

解法1（200点）

ちなみに、この解法を図示するとこんな感じになります。

1質問回数:1回

0質問回数:1回

仮に質問の答えが1でも0でも、質問回数は1回/1マスであることには変わりありません。

解法2（268点）

次に、よりよい解法を考えます。

爆弾のあるマスの割合が10%であることを考えてみましょう。

そうすると、2連続爆弾の無いマスはかなりあることが分かります。

⇒最初に1*2の区間を選んで、ここが0だったら1回の質問でできるので、質問回数を削減できそうです。

解法2（268点）

ここで、考察を図示してみます。

0 0 0 1 1 0 1 1

質問回数:1回 質問回数:1回

0 1 1 0質問回数:2回 質問回数:2回

ということで、2マスについての質問回数の平均は、

81%*1+9%*2+9%*2+1%*1=1.18⇒平均1450回

⇒得点：268点

解法3（447点）

結局は、爆弾の割合は10%なので、

4マスすべてに爆弾がないという事もあり得ます。

⇒2*2ごとに分割して、

爆弾が0であればこれ以上質問しない

爆弾が1～3であれば1*2の状態でやる

（上半分と下半分それぞれを求めるのにかかる質問回数は1（最初含めず））

爆弾が4であれば全部1とわかるのでこれ以上質問しない

解法3（447点）

とりあえず図示してみます。

0 00 0

1 00 0

1 10 0

1 00 1

1 00 0

1 00 0

1 10 0

1 00 1

1 00 1

1 00 1

1回

3回

2回

4回

結局1*2×2個の爆弾の個数を求めるのにかかる時間が減ります。全て0の場合はこの判定が1回でできるので、平均で65.61%*1*625≒410回削減されます。

⇒1450-410=1040回

⇒得点：447点

解法4（756点）

このまま4個から、8個、16個、32個、64個と、分割個数を増やしていくことを考えます。

そうすると、ある部分のコストは増えずに、減るだけなので、かなり効率的になります。

これは、再帰を使うと出来ます。

解法4（756点）

とりあえず、H=Wのときを考えます。

そのとき、この区間に爆弾があるかどうかをまず聞きます。

0個の時、return(枝刈り）します。

1個以上のとき、右半分と左半分に分けます。

（そしてまたその状態で再帰関数を呼び出す）

⇒H=2Wの場合も考えなければなりません。

0個

再帰

1個以上

再帰枝刈り

解法4（756点）

H=2Wの場合、左半分と右半分でなく、上半分と下半分に分けて同じことをするだけです。

0個の場合、上半分を数えずにreturn（枝刈り）します。

その場合、最初からH*2Wの領域にある爆弾の個数はわかっているので、この段階での質問回数は0回で済みます。

⇒ということで、2*2ごとに数えるのと同じことが32*32でもできるようになります。

0個枝刈り

1個以上

再帰

再帰

解法4（756点）

しかし、50*50だとどうでしょう。

25*50⇒25*25とすると、その後分割することができなくなります。

⇒そこで、32と18に分けるという工夫ができます。

P*Q(P≦Q)を2分割するとき、Qより小さく最も近い2𝑛数をRとするとき、P*Rの部分とP*(Q-R)の部分に分けるといいです。

それで、質問回数の平均は905回程度になりました。

⇒得点：756点

解法5（1,016点）

さっきの再帰を使った解法は、自分は約20分で思いつきましたが、次は考察に1日かかりました。

これは、以下のような方法です。2*2の場合に適用されます。

1 01 0

最初から分かっているので0回目

1 01 0

1回目

・ここは、上下両方1個の場合の2*1で調べます。・その場合、次で説明しますが、2*2の盤面上では4通りしか考えられません。

枝刈り

解法5（1,016点）

上半分、下半分が両方1個の場合は以下の4通りが考えられます。

1 01 0

0 10 1

1 01 0

1 00 1

0 11 0

0 10 1

1 00 1

0 11 0

1 00 1

0 11 0

2回

2回

3回

3回

ちなみに、上下に分けても左右に分けても両方1個ずつになるのは2通りしかありません。

左上が1か、0か、を判定するだけでできます。

解法5（1,016点）

よって、前のページの1個目と2個目の場合のみ質問回数が1回減ります。

ちなみにもともとの方法では全て3回です。

⇒これに入る可能性は0.9*0.9*0.1*0.1*2=1.62%なので、

1.62%*625=10.125回くらい全体で質問回数が減ります。

質問回数は、905-10=895回くらいです。

⇒得点：839点

解法5（1,016点）

2*2でできたということは、これを4*4にも、拡張できそうという事が分かります。

実際、左半分か右半分のどちらか一方が0個であり、

さらに上半分と下半分どちらも爆弾が1個以上という条件がそろえば

質問回数を1回減らせます。

例えば、以下のような盤面です。

その場合、全ての2*2の区間（4つ）の爆弾の数を

それぞれ求めるのに2回しかかかりません。

0 1 0 0

1 0 0 0

0 0 0 0

0 1 0 0

解法5（1,016点）

そうすると、かなりうまくいきます。

質問回数をさらに、平均で（全体）10回くらい減らすことができます。

⇒解法5の想定解は、4*4から以下のことをやるという方針です。

・上半分と下半分両方爆弾の数が1個以上の場合、左半分と右半分に分け、どちらかが0個の場合質問回数をへらすことができます。

⇒これで、895-10=885回くらいとなります。

⇒得点：1,016点

解法6（1,285点）

実際、さらに考察ができます。

実際私はこの解法が思いつくのに2日間かかりました。

まず、以下の盤面を考えます。

0 00 1

0 01 0

普通の場合、四角で囲まれた部分を最後に求めます。質問回数は合計で2+2=4回となります。

解法6（1,285点）

しかし、次のようにすれば効率的です。

また、以下のような場合、

0 00 1

0 01 0

そうすると、1が2つ⇒質問した区間がすべて1であることが分かるので、合計の質問回数が2+0=2回に減ります。

0 00 1

0 00 0

区間の合計が1個なので、とりあえず質問した2つのうちの左側に-2とかいう値を記録します。そうすると、右側の方が分かれば左側も自動的に分かるので、質問回数は前と変わりません。

解法6（1,285点）

このような操作は、2*2の中に爆弾が1個ある場合のみに有効で、質問回数が減るのは以下の場合のみです。

ただしここで指している2*2は、図の4*2の左半分です。

0 00 1

0 01 0

0 10 0

1 00 0

0 01 0

0 00 1

1 00 0

0 10 0

2回減

1回減

左下の回数が1減る理由は、右上の2*1に爆弾がないことが分かれば一番右下に爆弾があることが分かるからです。

解法6（1,285点）

全ての4*2の区間のうち、減らせる質問回数の期待値は以下のようになります。

・これらの盤面が出る確率

⇒0.9*0.9*0.9*0.9*0.9*0.9*0.1*0.1≒0.53%

・減らせる数の合計値

⇒2+2+1+1=6個

⇒24*25*0.53%*6≒19回≒20回、質問回数が全体で減らせます。

885-20=865回⇒1300点くらい？

⇒得点：1,285点

解法7（1,335点）

実は、まだ解説を書いた時点では1,450点解法を「実装していません」。

実際、1289点の時点で7,000バイトくらい実装しているので、本当に実装が重いです。

なので、自分が考えた1,450点解法を実装してしまうと、10,000Bくらいかかるかもしれないので、解説の方が先でした。本当に申し訳ございません。

解法7（1,335点）

今度は、解法6が2*2だったのを、解法7で4*4に拡張することができます。

例えば、以下のような場合、（1マスの大きさは2*2です）

赤いところが両方0なので、右下のマスが1と分かるまで

今までだと質問回数2

この方法だと質問回数1

よって、解法6と同様に1回分質問回数が減ります。

また、解法6と同じような局面なので、質問回数が増えることはありません。

0 0

≧1 0

0 0

0 ≧1

解法7（1,335点）

次に、この場合の期待される伸びを計算してみます。

0である確率は 0.94 = 0.6561であるため、1以上である確率は0.3439と分かります。

よって、期待値は、𝟎. 𝟔𝟓𝟔𝟏𝟔 ∗ 𝟎. 𝟑𝟒𝟑𝟗𝟐 ∗ 𝟏𝟐 ∗ 𝟏𝟐 = 𝟏. 𝟑𝟖くらい

これは、上下どちらに0があってもよいので、2を掛けられます。

⇒1.38*2=2.76 ➡約40点分の伸び

大体1,335点分になります。

0 0

≧1 0

0 0

0 ≧1

⇒得点：1,335点

解法8（1,435点）

次に、この場合について考えます。（2*4で）

この場合、赤い枠の場所を質問すれば、右半分の質問回数がもともと2回だったのが1回に減ります。

しかし、右図のような場合であっても、

いずれ3列目の合計の爆弾数が分かり、それによって2列目も後になって分かるので、質問回数は減ることはない

※なお、この場合、解法6では先に1*2（横長）を求めてしまっているので、2*4でなく4*2で求めた方がいい点数を得られます。

1 00 0

0 00 1

1 00 0

0 01 0

解法8（1,435点）

つまり、そういうことです。

2*4から4*2に直しても、質問回数が増えるパターンがないことには変わりありません。

なお、2*4の場合、解法6でアップグレードしたやつ（黄色い丸で囲まれている）とかぶるので、質問回数削減分の期待値は半分に減ってしまいます。

質問回数が1回減るパターン

1 00 00 01 0

1 00 00 00 1

0 10 00 01 0

0 10 00 00 1

質問回数が減らないパターン

1 00 01 00 0

1 00 00 00 0

1 01 01 10 1

解法8（1,435点）

次に、期待値を計算します。

まず、盤面の確率ですが、爆弾が2個あるので、

どれかが当たる確率は0.96 ∗ 0.12 ∗ 4 = 𝟎. 𝟎𝟐𝟏𝟐𝟓くらい

そして、2*4の盤面として数えられる（実際にそのうちの上半分が利用されるもの）は24*25=600個あるので、

期待値は𝟎. 𝟎𝟐𝟏𝟐𝟓 ∗ 𝟔𝟎𝟎 ∗ 𝟏 = 𝟏𝟐. 𝟕𝟓回くらい質問回数が減ります。

⇒各テストケースで{260,300,300,300,275}点くらいとれます。

⇒⇒⇒⇒⇒⇒⇒合計が1,435点！！！！！

⇒得点：1,435点

解法8（1,435点）

しかし、そもそも解法8まで行ける時点で本当に実装力がヤバイです。

まず、解法6の時点で7,000バイトも実装しているのにもかかわらず、さらにそれに加えて2*4,4*2,4*4などの場合の特別な処理を書かなければならず、10,000バイトを優に超えてしまうと思います。

さて、どこまで実装できたでしょうか…………………………

実際に、実装だけでなく、担当者（E869120）が考察するのにも約5日間か

かりました。

解法9（1,465点）

解法8について、もう少し考えてみます。

今まで、4*4に拡張させたときに4*8で見ることはあっても、8*4で見たことはありません。

つまり、被りなく2倍の大きさにまで拡張することができます。

例えば、こんな場合減らせます。

質問回数が1回減るパターン

≧1 00 00 0≧1 0

1 00 00 00 1

0 10 00 01 0

0 10 00 00 1

ただし、この図での1マスは2*2の大きさ、全体は8*4の大きさとなっています。

解法9（1,465点）

そこで、期待値を計算してみます。

まず、4マスの中に爆弾が0個ある確率は0.94 = 0.6561

次に、4マスの中に爆弾が1個以上ある確率は1 − 0.6561 = 0.3439

8(*4)マスの中に、0が6個、1が2個あるので、また、4*4の領域は全部で144個あるので、期待値は以下のようになります。

0.65616 ∗ 0.34392 ∗ 144 ∗ 4 = 𝟓. 𝟒𝟒くらい（4は減らせる盤面の通り数）

⇒1ケースにつき約15点～18点くらい伸びます。

⇒得点：1,465点

≧1 00 00 0≧1 0

解法10（1,500点）

さあ、最終問題も最後のひと踏ん張りとなりました。

そこで、以下のパターンについて考察をします。

1 01 0

0 ?0 ?

もともとは、赤く囲まれた部分の数を質問していました。しかし、以下のようにすると質問回数が1回減ります。

1 01 0

0 ?0 ? ?のうちどちらかが1以上である場

合、右側の質問回数はもともと2

回ですが、3列目がすべて0であることが分かるため、質問回数は1に減ります。

解法10（1,500点）

そこで、質問回数が減る場合を考えます。

下の場合、3列目が分かることによって2列目の合計が分かます。

よって、以下のようなフローチャートで処理を進めればよいです。

1 01 0

0 11 0

赤の中が0個1列目が2個、2列目が1個

赤の中が1個

3列目の合計が1個

3列目の合計が0個

1 01 0

とみて最後に2*2内を計算

1 00 1

か、0 11 0

とみて最後に2*2内を計算

解法10（1,500点）

このフローチャートの場合、どのような場合でももともとの場合より質問回数が増えることはありません。

ただし、これは左半分の中の爆弾数が2の場合のみです。

つまり、左半分(2*2)の中の爆弾数が2の場合、条件分岐で分けてやると効率が良いです。

ちなみに、期待値では0.94 ∗ 0.12 ∗ 0.19 ∗ 600 = 𝟏回分くらい

これで、テストケース1,4でそれぞれ3点ずつくらい伸びるという感じです。

⇒得点：1,470点

解法10（1,500点）

もちろん、これは4*4にも拡張可能です。

1マスの大きさを2*2と考え、4*8の大きさとして考えることで、さらに確率が上がります。

つまり、2つの?（4*2）の中に少なくとも1つ以上の爆弾があり、中2列は0個、左1列には各2*2のパックに少なくとも1個以上ある場合、1回質問を短くできる

期待値は、0.65614 ∗ 0.34392 ∗ 1 − 0.65612 = 𝟏. 𝟖くらい

1 01 0

0 ?0 ?

解法10（1,500点）

実際、これは横だけでなく縦にも活用できます。

例えば、右図のような感じの場合です。

さっきの1回と1.8回分それぞれをもう一倍減らすことができるので、さらに2.8回分質問回数を減らせるという意味になります。

よって、1470点解と比べて1+1.8+1.8=4.6回分の伸びです。

つまり、ケース1,4で4.6*3=13.8点ずつ足されることを考えると、1500点（1490点以上？）が取れることが期待されます。

1 10 00 00 0

⇒得点：1,500点

解法10（1,500点）

ちなみに、得点の色はこんな感じにつけました。（ちなみにこれはAtcoderのレートの色とは一切関係ありません）

色 点数

灰色 0～200点

茶色 201～400点

緑色 401～600点

水色 601～800点

色 点数

青色 800～1000点

黄色 1001～1200点

橙色 1201～1350点

赤色 1351～1499点

準急色 1500点

1,350点取れれば本当にすごいです。

最後に

この問題では、解説作成者（E869120）が1,291点までしか実装していないので、これに関しては深くお詫び申し上げます。

ただし、大体のケースで満点解法が存在することは保証されています(考察上で期待値計算をしたところそう）。

ということで、s8pcでは初めての応答型問題でしたが、この問題に触れた人、どうだったでしょうか。

面白かったならば、幸いです。

ということで、s8pc-3のH問題の解説を終わります。

結果

H問題（爆弾ゲーム）のAC者数は⇒⇒⇒

1500点者…0人

1201-1499点者…0人

901-1200点者…0人

601-900点者…7人

201-600点者…7人

001-200点者…3人

おしまい

ありがとうございました。

講評

今回のs8pc-3, どうでしたか？

今回は、s8pc-1に比べればかなり難しいセットになっているはずです。

第3回目、の有志コンテストとなりましたが、s8pcはs8pcとしての傾向があると思うので、過去問を解くとよいと思います。

ちなみに、writerはJOIerなので、情報オリンピックの対策にも少しはなると思います。

皆さん、ご参加ありがとうございました！

最終結果

問題名 配点 難易度 正解者数 部分点者数

A:カレンダー 250 250 106 57

B:石落としゲーム 300 400 47 5

C:XORパズル 400 350 55 23

D:お土産購入計画2 600 550 37 21

E:円と三角形 850 1100 6 11

F:寿司 1200 900 19 17

G:フィボナッチ数の総和 1400 1300 4 23

H:爆弾ゲーム 1500 2200 0 16

最終結果

最終結果②

問題名 最短 最短(人) 最速 最速(人) FA FA(人)

A:カレンダー 138B cojna 1ms yutaka1999 06:11 uwi

B:石落としゲーム 989B mn3twe 11ms sshirayama 15:13 uwi

C:XORパズル 498B mn3twe 5ms yutaka1999 12:19 nuip

D:お土産購入計画2 628B mn3twe 21ms rickytheta 18:10 kyuridenamida

E:円と三角形 1125B yutaka1999 64ms EvgeniSegreev 56:28 uwi

F:寿司 1564B yutaka1999 123ms BigINnner 40:11 yutaka1999

G:フィボナッチ数の総和 1478B gotoloop 33ms yosupo 80:01 koba

H:爆弾ゲーム - - - - - -