Codeforces Round #702 (Div. 3) 問題文和訳

A. Dense Array / Плотный массив
- 入力
- 出力
- 入出力例
- 注記
B. Balanced Remainders / Сбалансированные остатки
- 入力
- 出力
- 入出力例
- 注記
C. Sum of Cubes / Сумма кубов
- 入力
- 出力
- 入出力例
- 注記
D. Permutation Transformation / Трансформация перестановки
E. Accidental Victory / Случайная победа
F. Equalize the Array / Уравняй массив
G. Old Floppy Drive / Старый дисковод

A. Dense Array / Плотный массив

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

配列の隣接する2つの要素のうち大きい方が小さい方の2倍よりも大きくないとき、Поликарп*1はその配列を密と呼びます。より形式的には、任意の $i$ $(1 \leq i \leq n - 1)$ について次の条件が満たされてなければなりません。$$\frac{\max(a[i],\,a[i+1])}{\min(a[i],\,a[i+1])} \leq 2$$

例えば、配列 $[1,\,2,\,3,\,4,\,3]$ や $[1,\,1,\,1],$ $[5,\,10]$ は密です。また、配列 $[5,\,11]$ や $[1,\,4,\,2],$ $[6,\,6,\,1]$ は密ではありません。

$n$ 整数からなる配列 $a$ が与えられます。配列を密にするために追加する必要な数は最小で何個でしょうか? 配列内の任意の場所に数値を挿入することができます。もし配列が既に密であるなら、数を追加する必要はありません。

例えば $a = [4,\,2,\,10,\,1]$ のとき、答えは $5$ であり、要素を挿入した配列は次のようになります: $a = [4,\,2,\,\underline{\mathbf{3}},\,\underline{\mathbf{5}},\,10,\,\underline{\mathbf{6}},\,\underline{\mathbf{4}},\,\underline{\mathbf{2}},\,1]$ (このような $a$ を構成する方法は他にもあります)

入力

1行目には1つの整数 $t$ $(1 \leq t \leq 1000)$ が与えられる。その後、 $t$ 個のテストケースが続く。

各テストケースの1行目には1つの整数 $n$ $(2 \leq n \leq 50)$ が与えられる、 $n$ は配列 $a$ の長さである。

次の行には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 50)$ が与えられる。

出力

各テストケースについて単一の整数を出力せよ、その整数は配列を密にするために追加する数の最小数である。

入出力例

6
4
4 2 10 1
2
1 3
2
6 1
3
1 4 2
5
1 2 3 4 3
12
4 31 25 50 30 20 34 46 42 16 15 16

注記

1番目のテストケースは問題文で説明されています。

2番目のテストケースでは、1つの要素を挿入して密にできます: $a = [1,\,\underline{\mathbf{2}},\,3]$

3番目のテストケースでは、2つの要素を挿入して密にできます: $a = [6,\,\underline{\mathbf{4}},\,\underline{\mathbf{2}},\,1]$

4番目のテストケースでは、1つの要素を挿入して密にできます: $a = [1,\,\underline{\mathbf{2}},\,4,\,2]$

5番目のテストケースでは、配列 $a$ は既に密です。

B. Balanced Remainders / Сбалансированные остатки

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

数 $n$ ( $3$ で割り切れる)と配列 $a[1 \dots n$ ] が与えられます。1手で、任意の1つの配列の要素を1だけ大きくすることができます。形式的にはインデックス $i$ $(1 \leq i \leq n)$ を選び、 $a_i$ を $a_i + 1$ に置き換えることになります。異なる手番で同じインデックス $i$ を複数回選ぶことが可能です。

配列 $a$ のうち、 $3$ で割った時のあまりが $0,$ $1,$ $2$ である数の個数をそれぞれ $c_0,$ $c_1,$ $c_2$ とします。 $c_0,$ $c_1,$ $c_2$ が等しい配列 $a$ はバランスのとれた剰余を持つと呼ぶことにします。

例えば、 $n = 6$ で $a = [0,\,2,\,5,\,5,\,4,\,8]$ であるとき、次のような一連の手番が可能です。

最初は $c_0 = 1,$ $c_1 = 1,$ $c_2 = 4$ で、これらの値は互いに等しくはない。 $a_3$ を1増やして、配列 $a = [0,\,2,\,6,\,5,\,4,\,8]$ となる。
$c_0 = 2,$ $c_1 = 1,$ $c_2 = 3$ で、これらの値は互いに等しくはない。 $a_6$ を1増やして、配列 $a = [0,\,2,\,6,\,5,\,4,\,9]$ となる。
$c_0 = 3,$ $c_1 = 1,$ $c_2 = 2$ で、これらの値は互いに等しくはない。 $a_1$ を1増やして、配列 $a = [1,\,2,\,6,\,5,\,4,\,9]$ となる。
$c_0 = 2,$ $c_1 = 2,$ $c_2 = 2$ で、これらの値は互いに等しく、配列 $a$ はバランスのとれた剰余を持つこととなる。

配列 $a$ がバランスのとれた剰余を持つようにするために必要な手番の数の最小値を求めてください。

入力

1行目には1つの整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる。その後、 $t$ 個のテストケースが続く。

各テストケースの1行目には1つの整数 $n$ $(3 \leq n \leq 3 \cdot 10^4)$ が与えられる、 $n$ は配列 $a$ の長さである。数 $n$ は $3$ で割り切れることは保証されている。

次の行には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 100)$ が与えられる。

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

出力

各テストケースについて単一の整数を出力せよ、その整数は配列 $a$ がバランスのとれた剰余を持つようにするために必要な手番の最小数である。

入出力例

4
6
0 2 5 5 4 8
6
2 0 2 1 0 0
9
7 1 3 4 2 10 3 9 6
6
0 1 2 3 4 5

注記

1番目のテストケースは問題文で説明されています。

2番目のテストケースでは $i = 2$ という1手を行う必要があります。

3番目のテストケースでは3手必要です

第1手: $i = 9$
第2手: $i = 9$
第3手: $i = 2$

4番目のテストケースでは $c_0,$ $c_1,$ $c_2$ の値が最初から等しく、配列 $a$ はバランスのとれた剰余を持っています。

C. Sum of Cubes / Сумма кубов

テストごとの時間制限: 2 秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

正整数 $x$ が与えられます。数 $x$ が2つの正整数の立方の和にとして表現できるか確かめてください。

形式的には $a^3 + b^3 = x$ となるような2つの整数 $a,\,b$ $(1 \leq a,\,b)$ が存在するか確かめなければなりません。

例えば、 $x = 35$ のとき、 $a = 2,$ $b = 3$ が適当な例となります $(2^3 + 3^3 = 8 + 27 = 35)$ 。 $x = 4$ のときは、適当な $a,\,b$ の組は存在しません。

入力

1行目には1つの整数 $t$ $(1 \leq t \leq 100)$ が与えられる、 $t$ はテストケースの数である。その後、 $t$ 個のテストケースが続く。

各テストケースでは1つの整数 $x$ $(1 \leq x \leq 10^{12})$ が与えられる。

$32$ -bit整数型に収まらないテストケースの入力が存在するためプログラミング言語の $64$ -bit以上の整数型を用いる必要があることに注意せよ。

出力

各テストケースについて個別の行に出力せよ。

$x$ が2つの正整数の立方の和にとして表現できる場合: "YES"
そうでない場合: "NO"

"YES"と"NO"の大文字小文字はいかなる組み合わせでもよい(例えば文字列yEs、yes、Yes、YESはどれもYESとみなされる)。

入出力例

7
1
2
4
34
35
16
703657519796

NO
YES
NO
NO
YES
YES
YES

注記

数 $1$ は2つの立方数の和として表現することはできません。

数 $2$ は $1^3 + 1^3$ として表現することができます。

数 $4$ は2つの立方数の和として表現することはできません。

数 $34$ は2つの立方数の和として表現することはできません。

数 $35$ は $2^3 + 3^3$ として表現することができます。

数 $16$ は $2^3 + 2^3$ として表現することができます。

数 $703657519796$ は $5779^3 + 7993^3$ として表現することができます。

D. Permutation Transformation / Трансформация перестановки

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

順列とは $1$ から $n$ までの長さ $n$ の整数列で全ての数がちょうど1回出現するものです。例えば、 $[1],$ $[3,\,5,\,2,\,1,\,4],$ $[1,\,3,\,2]$ は順列で、 $[2,\,3,\,2],$ $[4,\,3,\,1],$ $[0]$ は順列ではありません。

Поликарпは最近、長さ $n$ の配列 $a[1 \dots n]$ を貰いました。Поликарпは順列よりも木が好きなので順列 $a$ を根附き二分木に変換したいと思っています。彼は異なる整数の配列を次のようにして木に変換させます。

配列の最大要素が木の根になる
最大値の左側にあるすべての要素は、左側部分木を形成する(配列の左部分に同じルールを適用して構築される)が、最大値より左に要素がない場合根は左側の子をもたない
最大値の右側にあるすべての要素は、右側部分木を形成する(配列の右部分に同じルールを適用して構築される)が、最大値より右に要素がない場合根は左側の右をもたない

例えば、彼が順列 $a = [3,\,5,\,2,\,1,\,4]$ から木を構築する場合、根は要素 $a_2 = 5$ となり、左側部分木は部分列 $a[1 \dots 1] = [3]$ から構築される木となり、右側部分木は部分列 $a[3 \dots 5] = [2,\,1,\,4]$ から構築される木となります。結果として、次のような木が構築されます。

f:id:Flkanjin:20210218155747p:plain — 順列 $a = [3,\,5,\,2,\,1,\,4]$ に対応する木

他の例として順列を $a = [1,\,3,\,2,\,7,\,5,\,6,\,4]$ としてみましょう。この場合、木は次のようになります。

f:id:Flkanjin:20210218160040p:plain — 順列 $a = [1,\,3,\,2,\,7,\,5,\,6,\,4]$ に対応する木

頂点 $a_v$ の深さ、すなわち、根から $a_v$ の番号のついた頂点までのパス上の辺の数を $d_v$ とします。根の深さは0であることに注意してください。順列 $a$ が与えられた時、各頂点について $d_v$ の値を求めてください。

入力

1行目には1つの整数 $t$ $(1 \leq t \leq 100)$ が与えられる、 $t$ はテストケースの数である。その後、 $t$ 個のテストケースが続く。

各テストケースの1行目には1つの整数 $n$ $(1 \leq n \leq 100)$ が与えられる、 $n$ は順列の長さである。

そののち、 $n$ 個の数 $a_1,\,a_2,\,\dots,\,a_n$ が続く、これらは順列 $a$ である。

出力

各テストケースについて $n$ 個の値を出力せよ、その値とは $d_1,\,d_2,\,\dots,\,d_n$ である。

入出力例

1 0 2 3 1 
0 
0 1 3 2

E. Accidental Victory / Случайная победа

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

$n$ 人の選手が参加するチャンピオンシップがBerland*2で開催される。番号 $i$ の選手は $a_i$ $(a_i \geq 1)$ 枚のトークンを持っています。

チャンピオンシップは次のルールの下で行われる $n-1$ 試合で構成されています。

各試合でトークン数が0枚でない2人の選手が無作為に選ばれる
トークン数が多い方が勝者となる(同数の場合、無作為に勝者が選ばれる)
勝者は敗者のトークンをすべてとる

最後に残ったトークン数が0でない選手がこのチャンピオンシップの優勝者となります。

チャンピオンシップ中に行われる無作為抽選は等確率で独立して行われます。

例えば、 $n = 4,$ $a = [1,\,2,\,4,\,3]$ のとき、試合の展開のうちの1つは次のようになります(他の可能性もあり得る)。

第1試合で第1選手と第4選手が選ばれた。第4選手がより多くのトークンを持っているため、第1選手のトークンを全てもらう。ここで $a = [0,\,2,\,4,\,4]$
第2試合で第3選手と第4選手が選ばれた。トークン数は同数であるが、無作為抽選により第3選手が勝者となる。ここで $a = [0,\,2,\,8,\,0]$
第3試合で第2選手と第3選手が選ばれた。第3選手がより多くのトークンを持っているため、第1選手のトークンを全てもらう。ここで $a = [0,\,0,\,10,\,0]$
第3選手がチャンピオンシップの優勝者となる

チャンピオンシップの優勝者には名前入りの賞品が送られます。そこで、審査員はどの選手が優勝する可能性があるのか、すなわち、0でない優勝確率があるのかを事前に知りたいと思っています。そのような選手をすべて見つけてください。

入力

1行目には1つの整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる、 $t$ はテストケースの数である。その後、 $t$ 個のテストケースが続く。

各テストケースの1行目には1つの整数 $n$ $(1 \leq n \leq 2 \cdot 10^5)$ が与えられる、 $n$ はチャンピオンシップの選手数である。

各テストケースの1行目には $n$ 個の正整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 10^9)$ が与えられる、これらは選手の持っているトークンの枚数である。

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

出力

各テストケースについてチャンピオンシップでの優勝確率が0でない選手の数を出力せよ。次の行にはそのような選手の番号を昇順で出力せよ。選手には入力に現れた順に番号が1から順に振られている。

入出力例

F. Equalize the Array / Уравняй массив

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

Поликарпは長さ $n$ の配列 $a$ をもらいました。配列内に各数が0回か $C$ 回出現するような数 $C$ が存在するような場合Поликарпはその配列を美しいと考えます。Поликарпは配列 $a$ からいくつかの要素を削除して美しくしたいと思っています。

例えば、 $n = 6,$ $a = [1,\,3,\,2,\,1,\,4,\,2]$ のとき、配列を美しくするために以下のような操作が可能です。

Поликарпは $2,$ $5$ の場所の要素を削除する。配列 $a$ は $[1,\,2,\,1,\,2]$ となる
Поликарпは $1,$ $6$ の場所の要素を削除する。配列 $a$ は $[3,\,2,\,1,\,4]$ となる
Поликарпは $1,$ $2,$ $6$ の場所の要素を削除する。配列 $a$ は $[2,\,1,\,4]$ となる

Поликарпのため、配列 $a$ を美しくするために削除しなければならない要素の最小数を求めてください。

入力

1行目には1つの整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる、 $t$ はテストケースの数である。その後、 $t$ 個のテストケースが続く。

各テストケースの1行目には1つの整数 $n$ $(1 \leq n \leq 2 \cdot 10^5)$ が与えられる、 $n$ は配列 $a$ の長さである。

各テストケースの2行目には $n$ 個の数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 10^9)$ が与えられる、これらは配列 $a$ である。

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

出力

各テストケースについて単一の整数を出力せよ、その整数は配列 $a$ を美しくするために必要な削除する要素の最小数である。

入出力例

3
6
1 3 2 1 4 2
4
100 100 4 100
8
1 2 3 3 3 2 6 6

2
1
2

G. Old Floppy Drive / Старый дисковод

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

Поликарпは屋根裏部屋を解体していて、古いフロッピードライブを見つけました。そのドライブの中には、 $n$ 個の整数が書かれた丸いディスクが入っていました。

Поликарпはディスクの数字を配列 $a$ に書きました。ドライブは次のようなアルゴリズムに従って動作することが分かりました。

ドライブは1つの正数 $x$ を入力として受け取り、配列 $a$ の最初の要素へのポインタを置く
その後、ドライブはディスクを回転させ始め、毎秒ポインタを次の要素へ移動させ、ポインタが指してきた要素の和を数える。ディスクは丸いため、配列 $a$ では最後の要素の次に最初の要素が続く
和が $x$ 以上になるとドライブはシャットダウンする

Поликарпはドライブ操作についてもっと知りたいと思いましたが、彼には自由な時間が全くありません。そこで彼は $m$ 個の質問をしてきました。 $i$ 番目の質問に答えるためには、ドライブに入力として $x_i$ を与えたときドライブは何秒間動作するかを調べる必要があります。ドライブが無限に動作する可能性があることに注意してください。

例えば、 $n = 3,$ $m = 3,$ $a = [1,\,-3,\,4],$ $x = [1,\,5,\,2]$ のとき、質問への答えは次のようになります。

第1クエリへの答えは $0$ となる: ドライブが最初の要素にポインタを向け、最初の和が $1$ となる
第2クエリへの答えは $6$ となる: ドライブがちょうど2回ディスクを回転させ、和が $1 + (-3) + 4 + 1 + (-3) + 4 = 5$ となる
第3クエリへの答えは $2$ となる: 和は $1 + (-3) + 4 = 2$ である

入力

1行目には1つの整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる、 $t$ はテストケースの数である。その後、 $t$ 個のテストケースが続く。

各テストケースの1行目には2つの整数 $n,\,m$ $(1 \leq n,\,m \leq 2 \cdot 10^5)$ が与えられる、それらはディスクに書かれた数字の数と質問数である。

各テストケースの2行目には $n$ 個の数 $a_1,\,a_2,\,\dots,\,a_n$ $(-10^9 \leq a_i \leq 10^9)$ が与えられる。

各テストケースの3行目には $m$ 個の数 $x_1,\,x_2,\,\dots,\,x_m$ $(1 \leq x \leq 10^9)$ が与えられる。

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

出力

各テストケースについて、各行に $m$ 個の整数を出力せよ。 $i$ 番目の整数は以下の通りである。

ドライブが永遠に動作する場合: $-1$
そうでない場合: ドライブが動作する秒数

入出力例

0 6 2 
-1 -1 
1 3

*1:露[pəlʲɪˈkarp]、ポリカルプ、ポリカープ、Polycarp: 古希Πολύκαρπος/po.lý.kar.pos/、ポリュカルポスに由来する人名

*2:Берлянд: 木やグラフに関する問題でしばしば登場する架空の国家