Xmas Contest 2018 ひとこと感想 (ネタバレ有り)

Xmas Contest 2018 ご参加ありがとうございました!

各問題についてひとことずつ重大なネタバレをしていこうと思います (ちゃんとした文章を書くには睡眠時間が足りなさすぎる)。

ちゃんとした文章は……、書くかもしれないし書かないかもしれません。







…(ネタバレ回避用余白)…







…(ネタバレ回避用余白)…







…(ネタバレ回避用余白)…








…(ネタバレ回避用余白)…








  • A: いいよねこれ。手作業してもいいし、解答キー生成スクリプト (Javascript) を読むとグラフが埋め込んであるのでそれを使って探索してもいい。
  • B: 思ったより解かれなかった感
  • C: WA を出さずに書くのは結構たいへん……ですが、けっこう素直に実装すれば一番取りこぼしがなくて WA を出しづらいみたいなところがあって良い。
  • D: びっくりするほど解かれなかった……。賢ければちゃんと構成できる (hogloid すげー) んですが、賢くなくても実は多少頑張って探索すれば爆速です。
  • E: これはびっくりです。
  • F: 唯一の原案。軽めの構成枠がほしいなと思って。
  • G: 超締切間際にこういうのが生えてくるのすごいよね。
  • H: これも思ったより難しかったっぽい (難易度推定無理すぎる〜)
  • I: 想定解はなんかやばかったです。人々が気合の入れた解をたくさん書いて (通して) くれてなんかいい問題っぽくなってて面白い。
  • J: 日本語実はそんな大変じゃなくて (実装は多少めんどいけど)、ふつうに計算するパートが意外とむずいよね……。

あんまネタバレせんかったな。

(2n-1)!! (奇数階乗) を mod 2^64 で求める

いろいろ忘れないようにメモ✍しておくとよさそうなので書いておきます。

やること

 n \geq 1 に対して  2n-1 以下の奇数をすべて乗算した奇数階乗 (奇数に対する二重階乗)

\begin{align}
(2n-1)!! = 1 \cdot 3 \cdot 5 \cdot \cdots (2n-3)(2n-1)
\end{align}

\mod 2^{64} で高速に求めます。具体的には  w=64 として  O(w^2 \log n) 時間です。

ここで  w^2 の部分は多項式の乗算と平行移動 ( P(x) の係数から  P(x+k) の係数を求める) にかかります。

やりかた

ソースコードです。Petrozavodsk Camp の問題で出たんですがジャッジがどこか分からない……。いちおう  n \leq 10^6 の範囲で愚直なのと比較して verify してあります。

uint64_t oddfact(uint64_t n) {
  if (n == 0) return 1;

  static uint64_t comb64[64][64];
  if (comb64[0][0] == 0) {
    for (int i = 0; i < 64; ++i) {
      comb64[i][0] = comb64[i][i] = 1;
      for (int j = 1; j < i; ++j) {
        comb64[i][j] = comb64[i - 1][j] + comb64[i - 1][j - 1];
      }
    }
  }

  using poly = array<uint64_t, 65>;
  poly p = {1};
  uint64_t k = 0;

  for (int b = 63 - __builtin_clzll(n); b >= 0; --b) {
    if (n & (1ULL << b)) {
      for (int i = 63; i >= 0; --i) {
        p[i + 1] += 2 * p[i];
        p[i] *= 2 * k + 1;
      }
      ++k;
    }
    if (b == 0) break;

    poly q = {}, r = {};
    for (int i = 0; i < 64; ++i) {
      uint64_t pk = 1;
      for (int j = i; j >= 0; --j) {
        q[j] += p[i] * comb64[i][j] * pk;
        pk *= k;
      }
    }
    for (int i = 0; i < 64; ++i) {
      for (int j = 0; i + j < 64; ++j) {
        r[i + j] += p[i] * q[j];
      }
    }
    p = r;
    k *= 2;
  }

  return p[0];
}

やってること

多項式  P_k(x) を以下のように定めます。要は  2x+1 から始まる  k 個の奇数の積です。

\begin{align}
P_k(x) = (2x+1)(2x+3)\cdots(2x+2k-1)
\end{align}

すると求めたい  (2n-1)!! P_n(0) になるので、これを計算すればよいです。ここで、すべての  x の出現に  2 が掛かっていることから、 \mod 2^{64} で考える場合  x^{64} 以上の高次の係数はすべて  0 になります。したがって  0 次から  63 次までの係数を持っておけば  P_k(x) を評価するには十分です。

この多項式  P_k(x) (の係数) は典型的な繰り返し二乗法の形で効率よく計算できます。

  •  P_{2k}(x) = P_k(x) \cdot P_k(x+k)
  •  P_{k+1}(x) = P_{k}(x) \cdot (2x+2k+1)

よって上のような多項式の計算を  O(\log n) 回やれば目的の  P_n(x) (の係数) が求められ、全体で  O(w^2 \log n) 時間で  (2n-1)!! が計算できました。

Xmas Contest 2017 D 問題 Inversion Number 解説

Xmas Contest 2017 D 問題「Inversion Number」の解説です。

問題概要

素数 N の順列であって、その転倒数を K で割った余りが m であるようなものの個数を 10^9 + 7 で割った余りを求めよ。

制約

  • 1 ≦ N ≦ 10^18
  • 0 ≦ m < K ≦ 10

解説

まず、N がさほど大きくない場合の解法を紹介します。この場合、

  • dp[n][k] := 長さ n の順列で、その転倒数を K で割った余りが k になるものの個数

という DP を行うことができます。長さ n の順列に新たに n+1 を挿入することを考えると、その挿入位置から転倒数の増分がすぐにわかるので、全体として以下のような DP になります。

dp[0][0] = 1;
for (int i = 0; i < N; ++i) {
  for (int j = 0; j < K; ++j) {
    for (int pos = 0; pos <= i; ++pos) {
      dp[i + 1][(j + pos) % K] += dp[i][j];
    }
  }
}

ここで、ちょうど K 番目の要素を挿入するときの DP 配列に注目しましょう(つまり、N=K となる場合の答えに注目します)。このときだけに注目すると DP 配列は次のように更新されています。

for (int mod = 0; mod < K; ++mod) {
  for (int pos = 0; pos < K; ++pos) {
    dp[K][(mod + pos) % K] += dp[K - 1][mod];
  }
}

これは、dp[K-1][mod] の値が、dp[K] の mod 番目、 (mod+1)%K 番目、(mod+2)%K 番目、……、(mod+K-1)%K 番目に足されているということで、結局 dp[K] の全体に1回ずつ足しているだけです。つまり、

  • dp[K][mod] = Σ_p dp[K-1][p]

が成り立ちます。この値は mod に依存していないので、N=K となる場合の答えは m に依存せずすべて同じであることがわかります。すなわち、N=K となる場合の答えは N! / K に他なりません。

さらに、このことに注意しながら N>K の場合を考えましょう。DP の更新式から、dp[n][mod] の値は dp[n-1] から n 個の値を持ってきて足し合わせたものになっていることがわかります。N=K のときに dp[K] の値はすべて同じになることがわかっているので、dp[K+1], dp[K+2], ..., もすべて mod に依らず同じ値を持つことになります。結局、N≧K となる場合の答えは N! / K であることがいえます。

ここまでくれば次のような解法でこの問題を解くことができます。

  • N < K のとき、N < K ≦ 10 なので DP や全探索によって解く。
  • N ≧ K のとき、N! / K を求める。

残った問題は N ≦ 10^18 のときに N! mod 10^9+7 をどう高速に求めるかという部分です。

N ≧ 10^9+7 のとき N! は 10^9+7 の倍数なので、当然 N! mod 10^9+7 = 0 となります。

N < 10^9+7 のとき、まだ O(N) かけていては間に合いません。そこで、N が何か適当な定数 (たとえば 500万とします) の倍数のときの N! mod 10^9+7 の値をあらかじめ求めてプログラム中にその結果をすべて埋め込んでおきます(これは手元で数秒〜数十秒程度の計算でできるはずです)。すると、任意の N < 10^9+7 に対しての N! の計算が高々 500 万回の掛け算で行えることになります(N 以下の 500 万の倍数で最大のものの階乗の値が埋め込んであるので、あとはそこから N までひとつずつ掛け算していく)。

以上でこの問題を十分高速に解くことができました。

Xmas Contest 2017 C 問題 Revenge of Kurousa 解説

Xmas Contest 2017 の C 問題「Revenge of Kurousa」の解説です。

問題概要

a〜z の 26 個の 8bit 整数型の変数がある。はじめ a に入力の値が入っており、b〜z は 0 である。できる操作は

  • ビットごとの論理演算: 16 種類ある論理演算のうち好きなものを選び、ビットごとの論理演算を行える(実質 Z = X NAND Y ができるのと同じ)。
  • 加算

の計 17 種類。この操作だけを使って a の値をインクリメントする(255 は 0 にする)ようなプログラム(操作の列)を書け。

加算を使う回数が最小に抑えられていれば 100 点、最小の2倍以下に抑えられていれば 30 点が得られる。

解説

最初にネタバレをすると、必要な加算の最小回数は 1 回です。よって、30 点をとるためには 2 回の加算でインクリメントする必要があります。

部分点解法(加算2回)

最初に 1 を作って、それを a に加算することを考えます。よって、1 を加算 1 回で作れれば十分です。

1 を作るには、たとえば以下のようにします。

  • 11111111 を作る(b = b 1111 b など)
  • 11111110 を作る(c = b + b)
  • 00000001 を作る(d = b 0110 c、つまり d = b xor c)
満点解法(加算1回)

以下では整数は全て mod 256 で考えます。要は 255 (2進数で 11111111) のことを -1 とか書きます。

まず、ビットごとの論理演算だけで入力値 A と 0 だけから作れる数はほとんどありません。具体的には以下の 4 種類しか作れません。

  • 0
  • A
  • -1 (b = b 1111 b などとして作る)
  • -A-1 (255-A と同じ、要は not A)

なので、ここで 1 回加算を行う必要があります。0 と何かを足しても意味がなく、A + (-A-1) = -1 はすでに -1 が作れる以上意味がないので、加算した結果として意味があるのは

  • A-1
  • -A-2

のいずれかです。

ここで not X が 255 - X = -X - 1 だったことを思い出せば

  • not (-A-2) = 255 - (-A-2) = A + 1

となりインクリメントができました。

Xmas Contest 2017 B 問題 Hello, Xmas Contest 2017 解説

Xmas Contest 2017 の B 問題「Hello, Xmas Contest 2017」の解説です。

問題概要

長方形グリッドの各マスに文字を書いて(書かないマスがあってもよい)、そのグリッドを 0 度・90 度・180 度・270 度のいずれの角度に回転した場合でも "XmasContest2017" という文字列が読み取れるようにせよ。ただし文字列の読み取りは以下のように行われる。

  • 上の行から順番に一行ずつ見ていく。
  • 見ている行に文字が書かれたマスが1個もなければ無視する。
  • 見ている行に文字が書かれたマスがあれば、そのうち最も左にあるものに注目する。そこに書かれた文字がアスタリスク '*' なら、この行を無視する。そうでなければ、その文字を読み取る。

グリッドのサイズも 100x100 を超えない範囲で自由に決めてよい。文字の書かれたマスが 32 個以下で満点 (100点)、100個 以上なら 0 点で、その間は 100 点から 0 点まで線形に点数が得られる。

解答

64 文字解答
17 17
*7102tsetnoCsamX*
X...............7
m...............1
a...............0
s...............2
C...............t
o...............s
n...............e
t...............t
e...............n
s...............o
t...............C
2...............s
0...............a
1...............m
7...............X
*XmasContest2017*

どう回転しても、各行の最初の文字に読ませたい文字を置いておけばそれを読んでくれることを使えば、四辺に読ませたい文字列を書くことで条件を満たす看板が作れます。

32 文字回答
16 16
*7..............
X.1.............
.m.0............
..a.2...........
...s.t..........
....C.s.........
.....o.e........
......n.t.......
.......t.n......
........e.o.....
.........s.C....
..........t.s...
...........2.a..
............0.m.
.............1.X
..............7*

文字列を斜めに並べることで、1 つの文字列を 2 つの方向から読み取らせることができるようになります。

そのほか

共通する文字を頑張って省く、斜めに一本だけ文字列を置いて残りを辺で埋めるなど、32文字と64文字の間の解もコンテスト中にいくつか見られました。

Xmas Contest 2017 A 問題 Compressor 解説

Xmas Contest 2017 の A 問題「Compressor」の解説です。

問題概要

15 個の(数秒程度の)楽曲データについて、コンプレッサーを適用したものとしていないものの組(計 30 個の wav ファイル)が与えられる。15 個の楽曲それぞれについて、どちらがコンプレッサーの適用された音源かを当てよ。

コンプレッサーについて

問題文中にもあるように、コンプレッサーは「使いこなすのが難しいエフェクター」の代表格とも言える存在です。本問題の入力を聴いてもわかるように、適用したからといって音が劇的に変化するようなエフェクターではありません(もちろんコンプの種類やパラメタ設定によって劇的な変化を持たせることも可能ですが)。

難しいエフェクターということもあり、「コンプレッサー DTM」など適当に検索するとコンプレッサーの作用や使い方について解説しているウェブページがたくさん出てきます。今回の問題を解くにあたっては特に難しい使い方というよりも、コンプレッサーとはそもそも何をするエフェクターなのかという基本のところだけ分かれば十分です。

コンプレッサーは名前の通り「音量の大きすぎる部分を(なめらかに)抑える」効果を持ちます。要は音を小さくするエフェクター乱暴)なのですが、コンプレッサーを使う目的はむしろ「音を前に出したい」「存在感を出したい」という方向性であることが多いです。元々大きい部分を先に潰しておき、そのあとで全体を持ち上げることで、全体的にはよく聴こえる=存在感が大きくなるようにするという使い方です。

下に示すのは Waves 社の C1 というコンプレッサーの画面です。真ん中に出ているグラフが音量圧縮の形を表しています(横軸が入力で縦軸が応答)。大きい音を潰すという動作なので、基本的にこのような形のグラフになります。(今回のデータを作るのに使ったコンプレッサーは C1 ではないのですが、見た目がわかりやすいのでここでは C1 の画面を例にします)

f:id:JAPLJ:20171225174217p:plain

このグラフをよく見ると、音量の小さいところはむしろ音量が上がっていることが読み取れると思います。これはコンプレッションによって下がったぶんのレベルを持ち上げるという機能がすでにこのコンプレッサーに含まれているためです (このコンプでは Makeup というパラメタで持ち上げを指定します)。C1 にかぎらず、コンプレッサーには元から下がったぶんのレベルを持ち上げる機能が含まれていることが多いです。

今回、問題文中で「同じ音に対して音量が著しく変化しないように」コンプレッサーをかけるという表現をしましたが、これはコンプレッションによって音を潰したあと、全体の音量が同じくらいになるまで全体を持ち上げて調整するというかけかたをするという意味です(「音量」にも色々あるのですが今回は RMS を揃えました)。

解説

解法1

耳で判断する。はいプロ。

解法2

コンプレッサーは「大きい部分を抑える」のですが、今回はその後で全体を持ち上げていますので、行われた操作としては「極端に大きい部分を抑えるかわりに、その他の部分を持ち上げる」となります。

すると、「抑えられた部分」と「持ち上げられた部分」のどちらが多いかが問題です。大抵の楽器は(特に打楽器では顕著ですが)鳴らした瞬間に急激に音が大きく出て、その後は比較的小さい音になります。なので、「抑えられた部分」はほかと比べてかなり少ないと考えられます。

つまり、波形の変化としては「ごく一部の音量が大きい部分」が抑えられたかわりに「その他大勢の音量が小さい部分」が持ち上げられることになります。実際にサンプル入力 (sample_mono_(dry|comp).wav) のサンプル値の分布を見てみるとかなり分かりやすいです。

f:id:JAPLJ:20171225175541p:plain

もともとサンプル値が 0 付近に集中しているのが、(コンプレッション後の)持ち上げによって外側に広がっているのが顕著です。この例は問題文中にあるように極端にコンプレッションをかけているので明らかですが、実際の入力ではもっと微妙な変化です。それでも、同じような変化を認めることができます。

f:id:JAPLJ:20171225175954p:plain

01_A と 01_B に対しても同様に分布を見てみましょう。画像ではかなり見づらいですが、01_A (紫) の方が 0 付近の山が低く、かわりに裾野 (絶対値 0.4〜0.5 あたり) では高くなっていることがわかります。

あとはこれを頑張って判定すればよいです。

サンプル値の絶対値をそれぞれ比較していって大きいものが多かった方とかそういう適当な判定法でも大体判別できます。この方法だと 04〜06 (EDM群)、特に 06 は少し微妙で誤判定があり得ます。他のケースだと結構大差になるのがここだと微差になっているので、この辺は答えを何通りか試してみることなどが必要になるかもしれません。

中心に集中している分布が裾野のほうに広がるという変化を判定するには、omeometo さんがやったように 4 次モーメントを使うとより確実でしょう。

解法3

耳にも分布にも頼らない手法もあるようです。コンテスト後の Twitter では、スペクトログラムを眺めて目で判断するといった解法も見られました。

入力データについて

16 個(入力とサンプル)とも私が作りました(大変でした)。

ongakusei.booth.pm

ところで 音楽性の違いにより結成しました という同人音楽サークルが存在して、その1作目の CD (https://ongakusei.tumblr.com/001) が BOOTH でダウンロード販売中だったりして(露骨な宣伝)、サンプルとして使ったピアノ曲がこの CD に収録されているんだって!? まずは是非クロスフェードデモをチェックだ!(露骨な宣伝)

本当の話をすると、15個のデータを頑張って作ったあとに、「アッ……サンプル用の音源もいるじゃん……」となってしまい、新たに1個作るのが面倒だったので既存の自作曲を持ってきました。

本番用の 15 個のデータはそれぞれ単一の音源を用いてテキトーに (それこそループ素材を重ねるだけとかで) 作りました。以下特に誰も得しない情報です:

Xmas Contest 2016 C問題 Cutting Swiss Roll 解説

Xmas Contest 2016 C 問題「Cutting Swiss Roll」の解説です。

問題概要

N 要素の整数列 A が与えられ、これを使って 2 人 でゲームをする。ゲームは

  • ひとりが A を好きなところで 2 つに切り分け、もうひとりが 2 つに分かれた整数列のうち好きな方を選んで捨てる。

という操作を、切る人と捨てる人を交代しながら交互に行う。最後に長さ 1 の整数列が残ったら終了とする。

先手が最後に残った整数を最大化、後手が最後に残った整数を最小化する戦略をとるとき、最後に残る整数を X とする。

先手の最適戦略 (後手が何をしても最後に X 以上の値を残せる戦略) を実装したプログラムを作成せよ。

制約

  • 1 ≦ N ≦ 5,000
  • 1 ≦ A[i] ≦ 10^9

解説

最適戦略は X の何になるかを示すときの証明から導くことができるので、X の値を求めよう。

まず、X の値を求めるために二分探索を行うことを考える。つまり、先手が X 以上の値を残せるかどうかの問題を解くことを考える。これは、A の各要素を X 以上なら +1、X 未満なら -1 に置き換えてゲームを行い、先手が +1 を残せるかどうか(残せるならば先手の勝ち)という問題になる。

ここで、この +1, -1 版のゲームの勝敗について以下の定理が成り立つ。この定理の内容は小さいケースを実験するなどして推測できる(何かこの定理に至る良い説明があったら教えてください)。

定理. 以下の 2 条件 (P), (Q) のうちどちらかが成り立つことと、先手が勝つことは同値である:

  • (P) A の中にある +1 の個数が -1 の個数より多い。
  • (Q) +1 の個数と -1 の個数が等しく、A の先頭 k 個の和 S[k] = A[1] + ... + A[k] が 0 になるような k が偶数個存在する。

この定理では A 全体やその接頭辞における +1, -1 それぞれの個数を問題としているので、定理中で導入した累積和 S を折れ線グラフの形で示したものをゲームの盤面と考えるとわかりやすくなる。

たとえば以下のような状況は条件 (P) が満たされている例である。折れ線の末尾が 0 より大きいところで終わっており、これは A 全体で +1 の個数が -1 の個数より多いことを表している。

f:id:JAPLJ:20161227182437p:plain

また、以下のような状況は条件(Q) が満たされている例である。折れ線の末尾が 0 で終わっており全体としては +1 と -1 の個数が等しく、また先頭を除いた 4 つの箇所で折れ線が 0 と交わっているため、条件 (Q) における k が 4 つ存在している。

f:id:JAPLJ:20161227182615p:plain

上記定理を証明する。証明は整数列の要素数 N についての帰納法による。

N=1 のとき

A = {+1} のとき、何もせず先手の勝ちであり、確かに (P) を満たす。A = {-1} のとき、何もせず先手の負けであり、(P) を満たさない。

N≧2 のとき

A の長さが N-1 以下のときに定理が成り立っていると仮定する。(P) ならば先手必勝、(Q) ならば先手必勝、先手必勝ならば (P) または (Q)、の 3 つを示せばよい。

なおこのゲームでは一回の手番のあと、+1, -1 をすべて反転することで、+1, -1 について対称に考えることができる。つまり、先手必勝であるとは、先手がある場所で切ったあと +1, -1 をすべて反転して、残った左右のどちらも (P), (Q) いずれも満たさない先手必敗の形を押し付けることができる、ということになる。

(P) ⇒ 先手必勝

2 通りの場合がある。まず、S (折れ線) が途中で 0 と交わる場合であるが、このとき先手は最初に S が 0 と交わるところ (青い線) で切ればよい。そうすると、切られた左側・右側のどちらも (+1, -1 を反転して) (P), (Q) いずれも満たさない形になっており、帰納法から両方ともに先手必敗の形である。よって青い線の部分で切れば相手に先手必敗の形を押しつけられるので、全体として先手必勝である。

f:id:JAPLJ:20161227183730p:plain

次に S が途中で 0 と交わらない場合を考える。A の先頭と末尾が両方とも +1 のとき、全体として +1 は -1 より 2 個以上多い。なぜなら、S が途中で 0 になっておらず、最後に正になっているため、S の最後から 2 番目の値も正 (1 以上)であり、よって S の最後の値は 2 以上と言えるからである。したがってこのとき先手は先頭 1 要素だけを切り離すことで、左右どちらも +1 の方が多い形を相手に押しつけられて先手必勝である。

そうでないとき、必ず A の末尾が -1 である。なぜなら、A の先頭が -1 で S の最後の値を正にするためには、途中で S が 0 と交わる必要があるためである。ここで、A 全体を reverse してもゲームとしては全く同じであることに注意すると、A を reverse することで先頭を -1 にできる。reverse しても S の最後の値は正のままなので、reverse することで S を途中で 0 と交わるようにでき、前述のように最初に S が 0 と交わるところで切れば先手必勝である。

(Q) ⇒ 先手必勝

ここでは、S の最後の値が 0 である場合のみについて考える。そのような場合のみに限れば、(Q) と先手必勝が同値であることが示せる。

k=1 のとき、S は以下のような形 (あるいはそれを上下折り返した形) をしているはずである。

f:id:JAPLJ:20161227185643p:plain

このとき、先手がどこで切っても、+1 と -1 の個数を均等に切り分けることはできない (そのように切り分けるには S が 0 のところで切らねばならない)。すなわち、左右のどちらかでは +1 の方が多くなり、もう一方では -1 の方が多くなる。よって相手が -1 の多い方を選択して残すことで勝つことができ、先手は必敗となる。

k≧2 のときは S が 0 のところで切る場合のみを考えればよい。なぜなら、そうでない場所で切っても +1, -1 の個数が均等でなくなり負けることが確定するためである。つまり、以下の図で青く示した点のみで切るゲームを考えればよい。

f:id:JAPLJ:20161227185949p:plain

これはつまり、k 個の山 (以下の図で◯で示した部分) を切り分けていき、最後に山 1 個の状態 (k=1) を押しつけられれば勝ちというゲームである。

f:id:JAPLJ:20161227190124p:plain

すると

  • k が偶数のとき、k = 奇数 + 奇数 の形に切り分けることで相手に奇数を押しつけられる。
  • k が奇数のとき、k = 偶数 + 奇数 と切り分けることしかできず、相手に偶数をとられる。

ことがわかる。k=1 (奇数) を受け取った側が負けることから、(S の最後が 0 という状況下に限れば) k が偶数であること、すなわち条件 (Q) は先手必勝であることと同値である。

先手必勝 ⇒ (P) または (Q)

(P) でも (Q) でもなければ先手必敗であることを示す。

まず (P) ではないので S の最後の値は 0 か負である。負のときは、どこで切っても -1 の多い部分を相手にとられてしまうので必敗である。したがって S の最後の値が 0 であるときを考える。

ところで、先程 S の最後の値が 0 のときに限れば、(Q) は先手必勝と同値であることを示した。ゆえに (Q) ではないことは先手必敗であることを意味する。

したがって (P) でも (Q) でもなければ先手必敗である。

以上で定理が証明された。最後に、具体的な戦略のみをまとめておく。

戦略

まず、上記定理に従って X の値を実際に求め、A[i] を X 以上なら +1、X 以下なら -1 に置き換えておく。すると A は先手必勝 (先手が必ず X 以上を残せる) 形になっているので、あとはこの上で必勝手順を行えばよい。具体的には以下のようにする。

切るとき

まず累積和 S を計算しておく。

  • +1 の方が個数が多いなら、S が最初に 0 になる点で切る。そのような点がなければ A を reverse したときの S が最初に 0 になる点で切る。そのような点もなければ最初の 1 要素を切り離す。
  • +1 と -1 の個数が同じなら、S が最初に 0 になる点で切る。

選ぶとき

上記定理によって勝敗判定は簡単に行えるので、勝てる方を残す。