Codeforces Global Round 13 問題文和訳

A. K-th Largest Value / K-е наибольшее (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n 整数からなる配列 a が与えられます。初期状態では、a の全ての要素は 01 のいずれかです。次の2種類のクエリを q 個処理しなければなりません。

  • 1 x: a_x に値 1 - a_x を代入する
  • 2 k: 配列内の k 番目に大きい値を出力する

注意点として配列内の k 番目に大きい値 b は次のように定義されています。

  • 配列を降順*1にソートし、その k 番目の要素を返す

例えば、配列 [0,\,1,\,0,\,1] を降順にソートすると [1,\,1,\,0,\,0] となり、その2番目の要素は 1 となるため、この配列の2番目に大きい要素は 1 となります。

入力

1行目には2つの整数 n,\,q (1 \leq n,\,q \leq 10^5) が与えられる、これらは配列の長さとクエリの数である。

2行目には n 個の整数 a_1,\,a_2,\,a_3,\,\dots,\,a_n (0 \leq a_i \leq 1) が与えられる、これらは初期配列の要素である。

つづく q 行には2つの整数が与えられる。1つ目の整数は t (1 \leq t \leq 2) で、これはクエリの種類である。

  • t = 1 の場合、2つ目の整数は x (1 \leq x \leq n) で、これは修正する数の位置である。a_x に値 1 - a_x を代入しなければならない
  • t = 2 の場合、2つ目の整数は k (1 \leq k \leq n) で、このとき配列の k 番目に大きい値を出力しなければならない

2番目の種類の(t = 2 を満たす)クエリが少なくとも1個は存在することは保証されている。

出力

各2番目の種類のクエリについて、単一の整数を出力せよ、その整数とはクエリへの答えである。

入出力例

5 5
1 1 0 1 0
2 3
1 2
2 3
2 1
2 5
1
0
1
0

注記

初期状態において、a = [1,\,1,\,0,\,1,\,0] である。

1番目の操作では、3番目に大きい値である 1 を出力しています。

2番目の操作では、a_2 に値 0 を代入していて、a[1,\,0,\,0,\,1,\,0] になります。

3番目の操作では、3番目に大きい値である 0 を出力しています。

4番目の操作では、1番目に大きい値である 1 を出力しています。

5番目の操作では、5番目に大きい値である 0 を出力しています。

B. Minimal Cost / Минимальная стоимость (750点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n10^6 + 2 列のグラフがあり、行は 1 から n まで、列は 0 から 10^6 + 1 までの番号が附けられています。
f:id:Flkanjin:20210301005303p:plain

ij 列の頂点(ノード)を (i,\,j) とします。

初期状態において各 i について i 行目にはちょうど1つの障害物が頂点 (i,\,a_i) に存在します。このグラフ上の辺を移動して(障害物を通過することはできない)頂点 (1,\,0) から頂点 (n,\,10^6 + 1) へ到達できるようにいくつかの障害物を移動させたいと思っています。辺によって隣接する障害物のない頂点に障害物を移動させるには、以下のようにu 枚、もしくは v 枚のコインがかかります。

  • 頂点 (i,\,j) に障害物があり、頂点 (i-1,\,j) もしくは (i+1,\,j) が存在して、その頂点に現在障害物がない場合、u 枚のコインを使うことでこの頂点に障害物を移動させることができる
  • 頂点 (i,\,j) に障害物があり、頂点 (i,\,j-1) もしくは (i,\,j+1) が存在して、その頂点に現在障害物がない場合、v 枚のコインを使うことでこの頂点に障害物を移動させることができる
  • 格子(グリッド)の外に障害物を移動させることができないことに注意せよ。例えば、(1,\,1) から (0,\,1) へ障害物を移動させることはできない

よりよく理解するためには上図を参照してください。

障害物を通過することなくこのグラフ上の辺を移動して頂点 (1,\,0) から頂点 (n,\,10^6 + 1) へ到達するために使わなければならないコインの最小枚数を計算しなければなりません。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる、これはテストケース数である。

各テストケースの1行目には3つの整数 n,\,u,\,v (2 \leq n \leq 100, 1 \leq u,\,v \leq 10^9) が与えられる、これらはそれぞれグラフの行数と、縦方向と横方向に移動するために必要なコインの枚数である。

各テストケースの2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 10^6) が与えられる、a_ii 行目の障害物は 頂点 (i,\,a_i)にあることを表している。

全てのテストケースでの n の和が 2 \cdot 10^4 を超えないことは保証されている。

出力

各テストケースについて、単一の整数を出力せよ、その整数とは障害物を通過することなくこのグラフ上の辺を移動して頂点 (1,\,0) から頂点 (n,\,10^6 + 1) へ到達するために支払わなければならないコインの最小枚数である。

問題の制約下では、そのような移動を可能にする方法が常に存在することは示すことができる。

入出力例

3
2 3 4
2 2
2 3 4
3 2
2 4 3
3 2
7
3
3

注記

1番目のサンプルでは、2つの障害物が (1,\,2)(2,\,2) にあります。(2,\,2) にある障害物を (2,\,3) に移動させ、そののち (1,\,3) に移動させることができます。総コストは u + v = 7 コインです。

f:id:Flkanjin:20210301013011p:plain

2番目のサンプルでは、2つの障害物が (1,\,3)(2,\,2) にあります。(1,\,3) にある障害物を (2,\,3) に移動させることができます。コストは u = 3 コインです。

f:id:Flkanjin:20210301013126p:plain

C. Pekora and Trampoline / Pekora и батуты (1000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
1列に n 個のトランポリンが並んだトランポリン公園があります。その i 番目のトランポリンは強度 S_i を持っています。

ぺこら*2は何回かのパスにおいてトランポリンで跳ぶことができます。彼女は、好きなトランポリンで跳ぶことでパスを開始します。

ぺこらがトランポリン i で跳んだ瞬間、このトランポリンは彼女を位置 i + S_i へ打ち上げ、S_i\max(S_i-1,\,1) になります。つまり、S_i1 のままとなる S_i = 1 の場合を除いて、S_i1 だけ小さくなります。

位置 i + S_i にトランポリンがない場合、このパスは終了します。そうでなければ、ぺこらは上記と同じルールで、位置 i + S_i にあるトランポリンで跳ねてパスを継続させます。

ぺこらは n よりも大きな位置(トランポリンがない場所)に着地するまでパス中のジャンプを止めることはできません。可哀そうなぺこら!

ぺこらは悪戯好きな兎で全ての S_i1 に減らしてトランポリン公園を台無しにしたいと思っています。全ての S_i1 に減らすのに必要な最小パス数は何個でしょう?

入力

1行目には単一の整数 t (1 \leq t \leq 500) が与えられる、これはテストケース数である。

各テストケースの1行目には単一の整数 n (1 \leq n \leq 5000) が与えられる、これはトランポリンの個数である。

各テストケースの2行目には n 個の整数 S_1,\,S_2,\,\dots,\,S_n (1 \leq S_i \leq 10^9) が与えられる、S_ii 番目のトランポリンの強度である。

全てのテストケースでの n の和が 5000 を超えないことは保証されている。

出力

各テストケースについて、単一の整数を出力せよ、その整数とは全ての S_i1 に減らすのにぺこらが必要とする最小パス数である。

入出力例

3
7
1 4 2 2 2 2 2
2
2 3
5
1 1 1 1 1
4
3
0

注記

1番目のテストケースでのぺこらがとることができる最適なパス列を示しています。(太字の数字がこれらのパスの間にぺこらが跳ぶ位置です。)

  • [1,\,4,\,\mathbf{2},\,2,\,\mathbf{2},\,2,\,\mathbf{2}]
  • [1,\mathbf{4},\,1,\,2,\,1,\,\mathbf{2},\,1]
  • [1,\,\mathbf{3},\,1,\,2,\,\mathbf{1},\,\mathbf{1},\,\mathbf{1}]
  • [1,\,\mathbf{2},\,1,\,\mathbf{2},\,1,\,\mathbf{1},\,\mathbf{1}]

2番目のテストケースでの最適なパス列は下の通りです。

  • [\mathbf{2},\,3]
  • [1,\,\mathbf{3}]
  • [1,\,\mathbf{2}]

3番目のテストケースでは、全ての S_i がすでに 1 となっています。

D. Zookeeper and The Infinite Zoo / Хранительница Бесконечного Зоопарка (1250点)

テストごとの時間制限: 3秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
シンガポール動物園*3に新しいアトラクション『無限動物園』が登場しました。

無限動物園は、1,\,2,\,3,\,\dots とラベル附けられた無限頂点のグラフで表すことができます。u\ \&\ v = v のとき、またその時に限り頂点 u から頂点 u + v への有向辺が存在します、ここで \& とはビットAND演算*4を表します。グラフには他の辺は存在しません。

Zookeeper*5q 個のクエリを投げてきます。i 番目のクエリでは彼女は有向辺を辿っていくことで頂点 u_i から v_i へ着くことができるかを訊いてきます。

入力

1行目には単一の整数 q (1 \leq q \leq 10^5) が与えられる、これはクエリの個数である。

つづく q 行の i 行目には2つの整数 u_i,\,v_i (1 \leq u_i,\,v_i \leq 2^{30}) が与えられる、これがZookeeperによるクエリである。

出力

q 個クエリの i 番目について、Zookeeperが頂点 u_i から v_i へ着くことができる場合、"YES"と出力せよ。そうでない場合、"NO"と出力せよ。

答えの大文字小文字はいかなる組み合わせでもよい。例えば、答えが"YES"の場合、"Yes"や"yeS"といった出力は正解とみなされる。

入出力例

5
1 4
3 6
1 6
6 2
5 5
YES
YES
NO
NO
YES

注記

頂点 1,\,2,\,3,\,4,\,5,\,6 上の部分グラフを以下に示します。
f:id:Flkanjin:20210301022600p:plain

E. Fib-tree / Фиб-дерево (1750点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
F_k を以下に定義されるFibonacci*6数列の k 項目とします。

  • F_0 = F_1 = 1
  • 任意の整数 n \geq 0 について F_{n + 2} = F_{n + 1} + F_n

n 頂点の木が与えられます。木とは、サイクルのない無向連結グラフです。

頂点数が F_k であるような k が存在し*7、以下の条件のうち少なくとも1つが満たされる場合、その木をFib-treeと呼びます。

  • この木は 1 頂点のみから成る
  • 木から取り除けば2つのFib-treeとに分割できるような辺が存在する

与えられた木がFib-treeであるかどうか判別してください。

入力

1行目には単一の整数 n (1 \leq n \leq 2 \cdot 10^5) が与えられる、これは木の頂点数である。

n - 1 行が続き、それぞれの行には2つの整数 u,\,v (1 \leq u,\,v \leq n u \neq v) が与えられる、これは頂点 uv の間の辺を表している。与えられた辺が木を形成することは保証されている。

出力

与えられた木がFib-treeである場合、"YES"と出力せよ。そうでない場合、"NO"と出力せよ。

答えの大文字小文字はいかなる組み合わせでもよい。例えば、答えが"YES"の場合、"Yes"や"yeS"といった出力は正解とみなされる。

入出力例

3
1 2
2 3
YES
5
1 2
1 3
1 4
1 5
NO
5
1 3
1 2
4 5
3 4
YES

注記

1番目のサンプルでは、辺 (1,\,2) を取り除くことで木をそれぞれサイズ 122 つの木に分割することができます。サイズ 2 の木はサイズ 1 の木 2 つに分割することができるので、どんな木でもFib-treeとなります。

2番目のサンプルでは、どの辺を取り除くいても、サイズ 142 つの木に分割します。4 は任意の k に対して F_k ではないので、Fib-treeではありません。

3番目のサンプルでは、全ての木がFib-treeとなるような可能な分割方法を1つ考えます: (1,\,3), (1,\,2), (4,\,5), (3,\,4)

F. Magnets / Магниты (2000点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
これはインタラクティブ問題です。

東風谷早苗*8は磁石で遊んでいます。その磁石の中には消磁されているものがあることに気づき、彼女はそれがどれなのか知りたいと思っています。

磁石が n 個あり、これらは次の 3 種類のいずれかです。

  • N
  • S
  • - この磁石は消磁されている

これらの磁石の種類は前もっては分からないことに注意してください。

磁石同士の力を測定できる機械を持っていて、それを最大 n + \lfloor \log_2 n \rfloor 回用いることができます。

機械の左側に磁石をいくつか置いて、右側にもいくつか置いて、機械を起動させることができます。明らかに1つの磁石は高々1か所にしか置けません(全ての磁石を用いる必要はありません)。同じ磁石を複数のクエリで用いることができます。

そうすると、機械はこれらの磁石が生み出す力を示します。形式的には、n_1,\,s_1 をそれぞれ左側にある NSの磁石の数とし、n_2,\,s_2 も右側にある同様のものとします。このとき、これらの磁石の力は n_1n_2 + s_1s_2 - n_1s_2 - n_2s_1 となります。力は符号附きの値であることに注意してください。

しかし、力の絶対値が n よりも真に大きいとき、機械は粉々に壊れてしまいます。

機械を壊すことなく、全てのタイプが-である(消磁されている)磁石を見つけなければなりません。

相互入出力機(インタラクタ)は状況適用的ではないことに気を付けて下さい。磁石の種類は相互入出力の開始前に固定されていて、クエリによって変わることはありません。

種類が-でない磁石が少なくとも 2 つ存在し、種類が-である磁石が少なくとも 1 つ存在することは保証されています。

入力

1行目には単一の整数 t (1 \leq t \leq 100) が与えられる、t はテストケース数である。

相互入出力

各テストケースにおいて、初めに1つの整数 n (3 \leq n \leq 2000) を読み取らなければならない、n は磁石の個数である。

全てのテストケースでの n の和が 2000 を超えないことは保証されている。

そののち、機械にいくつかの磁石を入れ、出力によってクエリを作ることができる。

各クエリは3行で出力しなければなりません。

  • 1行目には”? l r”(引用符なし)と出力せよ、l,\,r (1 \leq l,\,r \lt n, l + r \leq n)はそれぞれ左右に置く磁石の個数を表す
  • 2行目には l 個の整数 a_1,\,\dots,\,a_l (1 \leq a_i \leq n, i \neq j\ について\ a_i \neq a_j)を出力せよ、 これらは左側に置く磁石のインデックスである
  • 3行目には r 個の整数 b_1,\,\dots,\,b_r (1 \leq b_i \leq n, i \neq j\ について\ b_i \neq b_j)を出力せよ、 これらは右側に置く磁石のインデックスである
  • 同じ磁石を同一クエリ内で両側に置くことはできない。形式的には任意の i,\,j について a_i \neq b_j となることを保証しなければならない。しかし、一部使わないままにしておく磁石があってもよい

クエリの出力後、改行出力、出力バッファのflushを忘れないようにせよ。そうするためには次を利用せよ。

  • C++の場合、fflush(stdout)cout.flush()
  • Javaの場合、System.out.flush()
  • Pascalの場合、flush(output)
  • Pythonの場合、stdout.flush()
  • 他の言語の場合は、ドキュメントを参照せよ

そののち、1つの整数 F を読み取らなければならない、これは磁石の生み出す力である。

クエリが無効な場合(クエリ制限を超えた場合や、機械が壊れた場合、引数が無効な場合)、相互入出力機は直ちに終了することに気をつけよ。この場合、他の恣意的な結果ではなくWrong Answerという結果を受けるためにプログラムを終了させよ。

答えに自信がある場合、次の形式で報告せよ。

  • ! k A”、ここで k は見つけた磁石の数、A は見つかった種類-の磁石のインデックスを表す k 個の 1 から n の異なる整数の配列である。A の要素は任意の順で出力することができる
  • そののち、それが最後のテストケースである場合、プログラムを終了させなければなりません。そうでない場合、直ちに次のテストケースの処理を続けなければなりません。

相互入出力機は状況適用的ではないことに気を付けよ。磁石の種類は相互入出力の開始前に固定されていて、クエリによって変わることはない。

ハックケース

答案をハックするには、次の形式を用いよ。

1行目には単一の整数 t (1 \leq t \leq 100) を出力せよ、これはテストケース数である。

次に t 個のテストケースを、それぞれ2行ずつ出力することで続けよ。

  • 1行目には単一の整数 n (3 \leq n \leq 2000) を出力せよ、これは磁石の数である
  • 2行目には磁石の種類を表すNS-から成る長さ n の文字列 S を出力せよ
  • 各テストケースにおいて、種類が-でない磁石が少なくとも 2 つ存在し、種類が-である磁石が少なくとも 1 つ存在することは保証しなければなりません。また、全てのテストケースでの n の和が 2000 を超えないことも保証しなければなりません。

入出力例

1
4



0



1



0



0

? 1 1
3
4

? 1 2
1
2 3

? 1 1
1
4

? 1 1
1
3

! 2 3 4

注記

サンプルの空行は、相互入出力機のよりよい理解のためのものです。これらを出力する必要はありません。

このサンプルでは、磁石の種類はNN--です。

まず、左側に3番目の磁石を置き、右側に4番目の磁石を置きます。どちらも種類は-であるため、力は生み出されません。

次に、左側に1番目の磁石を置き、右側に2番目と3番目の磁石を置きます。3番目の磁石の種類は-で、他の2つの磁石の種類はNなので、生成される力は 1 となります。

つづく2つのクエリでは、右側には種類-の磁石しかないため、力は 0 となります。

すると、種類-の磁石は3番目と4番目の磁石であると判断でき、! 2 3 4と出力して終了します。

G. Switch and Flip / Обменяйте и переверните (2250点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
1 から n までの番号が振られた n 枚のコインがあります。最初、コイン c_i は位置 i にあり、表を向いています((c_1,\,c_2,\,\dots,\,c_n)1 から n までの数の順列になっています)。これらのコインに対して操作を行うことができます。

1回の操作で次のようなことを行えます。

  • 2 つの異なるインデックス i,\,j を選ぶ
  • 位置 i,\,j にあるコインを入れ替える
  • 位置 i,\,j にある2枚のコインを裏返す(もし最初に表向きになっていれば裏向きになり、またその逆も同様)

全てを実行すると最終的にコイン i が位置 i表を向いているような最大 n + 1 個の操作の列を構築してください。

操作の数を最小化する必要はありません

入力

1行目には1つの整数 n (3 \leq n \leq 2 \cdot 10^5) が与えられる、これはコインの枚数である。

2行目には n 個の整数 c_1,\,c_2,\,\dots,\,c_n (1 \leq c_i \leq n, i \neq j\ について\ c_i \neq c_j) が与えられる。

出力

1行目には1つの整数 q (0 \leq q \leq n + 1) を出力せよ、これは行う操作の回数である。

つづく q 行には2つの整数 i,\,j (1 \leq i,\,j \leq n, i \neq j) を出力せよ、これは操作で選択する位置である。

入出力例

3
2 1 3
3
1 3
3 2
3 1
5
1 2 3 4 5
0

注記

表向きのコイン ii と、裏向きのコイン i-i と表記します。

1番目のサンプルで行われたる一連の操作はコインを次のように変化させます。

  • [~~~2,\,~~~1,\,~~~3]
  • [-3,\,~~~1,\,-2]
  • [-3,\,~~~2,\,-1]
  • [~~~1,\,~~~2,\,~~~3]

2番目のサンプルでは、すでにコインは所定の位置あるため、交換の必要はありません。

H. Yuezheng Ling and Dynamic Tree / Yuezheng Ling и динамическое дерево (3000点)

テストごとの時間制限: 1.5秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
乐正绫*9洛天依*10n 頂点で、1 を根とする木をあげます。

洛天依はあなたに i 番目の頂点の親が a_i (2 \leq i \leq n について 1 \leq a_i \lt i) であることを伝え、2 種類の q 個のクエリを実行するように頼んできます。

  1. 3つの整数 l,\,r,\,x (2 \leq l \leq r \leq n, 1 \leq x \leq 10^5) が与えられる。l \leq i \leq r である全ての i について a_i\max(a_i - x,\,1) を代入しなければならない。
  2. 2つの整数 u,\,v (1 \leq u,\,v \leq n) が与えられる。頂点 u,\,vLCA*11(最小共通祖先)を求めなければならない

入力

1行目には2つの整数 n,\,q (2 \leq n,\,q \leq 10^5) が与えられる、これらはそれぞれ頂点数とクエリ数である。

2行目には n - 1 個の整数 a_2,\,a_3,\,\dots,\,c_n (1 \leq a_i \lt i) が与えられる、a_i は頂点 i の親である。

つづく q 行にはクエリが与えられる。各クエリについて1つ目の整数は t (t = 1 or 2) であり、クエリの種類である。

t = 1 の場合、これは1番目の種類のクエリを表す。こののち、3つの整数 l,\,r,\,x (2 \leq l \leq r \leq n, 1 \leq x \leq 10^5) が続く、これらはl \leq i \leq r である全ての i について a_i\max(a_i - x,\,1) を代入することを表す。

t = 2 の場合、これは2番目の種類のクエリを表す。こののち、2つの整数 u,\,v (1 \leq u,\,v \leq n) が続き、u,\,vLCAを求めなければならない。

2番目の種類のクエリが少なくとも1回来ることは保証されている。

出力

各2番目の種類のクエリについて、新しい行に答えを出力せよ。

入出力例

6 4
1 2 3 3 4
2 3 4
1 2 3 1
2 5 6
2 2 3
3
3
1

注記

入出力例の木は次のようになります。
f:id:Flkanjin:20210301125254p:plain
1番目の種類のクエリの後、木は変化し、次のようになります。
f:id:Flkanjin:20210301125329p:plain

I. Ruler Of The Zoo / Правитель зоопарка (5000点)

テストごとの時間制限: 3秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Zookeeperがただの鴨であることに気付いた動物達はZookeeperを倒しました。現在、彼等は次の形式の戦闘トーナメントで新しい支配者を決定しなければなりません。

最初、動物 0 が王で、他の動物が動物 1 を先頭に、動物 n - 1 を最後尾とする待ち行列に並びます。待ち行列の先頭の動物は王に戦いを挑み、力の強い動物が勝ちます。勝者が王となり、敗者は待ち行列の最後尾に並びます。

3 連勝した動物が動物園全体の支配者となります。各動物の強さは何連勝しているかによって決まります。動物 i の強さは 0 連勝中で A_i1 連勝中で B_i2 連勝中で C_iとなります。初期状態では全員が 0 連勝の状態です。

全ての動物について A_i \gt B_i かつ C_i \gt B_i が成り立ちます。また、A_i,\,B_i,\,C_i の値は相異なります(3n 個全ての値がどの組も互いに等しくない)。

言い換えると、王でない動物の強さは A_i です。王の強さは通常 B_i または C_i です。例外として、最初のターンでは最初の王(動物 0)の強さは A_i です。

何回の戦闘の後、誰が新しい支配者になるでしょうか? それとも、動物たちは永遠に戦いを続け、誰も支配者にならないのでしょうか?

入力

1行目には1つの整数 n (4 \leq n \leq 6000) が与えられる、惟男は動物の数である。

つづく n 行の i 行目には 3 つの整数 A_i ,\,B_i,\,C_i (0 \leq A_i,\,B_i,\,C_i \leq 10^9)*12 が与えられる。

A_i \gt B_i かつ C_i \gt B_i であり、全てのA_i ,\,B_i,\,C_i の値が相異なることは保証される。

出力

単一行に2つの整数を出力せよ。1つ目の整数は支配者となる動物のインデックスで、2つ目の整数はその動物が支配者になるまでに行われる戦いの数である。

動物が無限に戦う場合、代わりに-1 -1と出力せよ。

入出力例

4
5 1 2
10 8 11
9 0 3
7 4 6
-1 -1
5
11 7 12
8 6 14
2 1 10
13 0 9
5 3 4
1 7

注記

以下に2つ目のサンプルでの事象列について説明します。戦闘 1 において、王(動物 0)の強さが A_0 であることに注意してください。動物 1 戦闘 5,\,6,\,7 で勝利し、トーナメントは戦闘 7 で終了します。
f:id:Flkanjin:20210301134015p:plain

*1:non-increasing orderなので正確には非昇順

*2:Virtual YouTuberの兎田ぺこら

*3:実在する

*4:原文では英語、ロシア語のWikipediaへのリンク

*5:Хранительница Зоопарк 動物園の職員という意味だが、大文字始まりなので固有名詞のように用いられている。また、後の問題から管理人等の意味でとった方が良い

*6:伊[fiboˈnattʃi] Leonardo Fibonacci この数列で有名な人

*7:原文をそのまま訳すと「ある k について頂点数が F_k であり」

*8:東方Projectのキャラクター

*9:中/yɛ.ʈʂəŋ liŋ/ 拼音: yuèzhèng líng 楽正綾 中国語VOCALOID

*10:中/luɔ tʰiɛn.i/ 拼音: luò tiānyī 中国語VOCALOID

*11:日本語版Wikipediaには生物用語としてのページしかないため英語版にリンクを繋げた

*12:本当は添え字は i-1であると思われる