Codeforces Round #714 (Div. 2) 問題文和訳

A. Array and Peaks / Массив и пики (500点)
- 入力
- 出力
- 入出力例
- 注記
B. AND Sequences / Последовательности И (1250点)
- 入力
- 出力
- 入出力例
- 注記
Add One / Добавь единицу (1500点)
- 入力
- 出力
- 入出力例
- 注記
D. GCD and MST / НОД и МОД (2000点)
- 入力
- 出力
- 入出力例
- 注記
E. Cost Equilibrium / Ценовой баланс (2750点)
- 入力
- 出力
- 入出力例
- 注記
F. Swapping Problem / Задача об обмене (3500点)
- 入力
- 出力
- 入出力例
- 注記

A. Array and Peaks / Массив и пики (500点)

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

$n$ 整数の列は $1$ から $n$ までの全ての整数をちょうど1個ずつ含むとき順列と呼ばれます。

2つの整数 $n,\,k$ が与えられるので、ちょうど $k$ 個のピークをもつ $1$ から $n$ までの数の順列 $a$ を構築してください。大きさ $n$ の配列 $a$ のインデックス $i$ は $1 \lt i \lt n$ かつ $a_i \gt a_{i-1}$ かつ $a_i \gt a_{i+1}$ であるとき、ピークといいます。そのような順列が存在しない場合は、 $-1$ と出力してください。

入力

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

それから $t$ 行が続き、そのそれぞれには空白で区切られた2つの整数 $n$ $(1 \leq n \leq 100),$ $k$ $(0 \leq k \leq n)$ が与えられる、これらは配列の長さとピークの数である。

出力

$t$ 行出力せよ。各テストケースについて、与えられた長さとピークの数を持つ順列がない場合は、 $-1$ と出力せよ。そうでない場合は、 $1$ から $n$ までの数の順列を形成し、ちょうど $k$ 個のピークを持つような空白で区切られた $n$ 個の整数を1行に出力せよ。

答えが複数存在する場合、そのいずれかを出力せよ。

入出力例

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

注記

入出力例の2つ目のテストケースでは、配列 $a = [2,\,4,\,1,\,5,\,3]$ となります。ここでインデックス $i = 2$ と $i = 4$ がピークとなります。これは $(a_2 \gt a_1,$ $a_2 \gt a_3)$ で、 $(a_4 \gt a_3,$ $a_4 \gt a_5)$ であるからです。

B. AND Sequences / Последовательности И (1250点)

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

$n$ $(n \geq 2)$ 個の非負整数の列 $a_1,\,a_2,\,\dots,\,a_n$ は $1$ から $n-1$ までの全ての $i$ について次の条件が成立するとき、よい配列という。

$a_1 \: \& \: a_2 \: \& \: \dots \: \& \: a_i = a_{i+1} \: \& \: a_{i+2} \: \& \: \dots \: \& \: a_n$

ここで、 $\&$ はビットAND *1を表します。

大きさ $n$ $(n \geq 2)$ の配列 $a$ が与えられます。列 $a_{p_1},\,a_{p_2},\,\dots,\,a_{p_n}$ がよい配列となるような $1$ から $n$ までの数の順列 $p$ の個数を求めて下さい。この数は大きくなる可能性があるので、modulo $10^9 + 7$ で出力してください。

入力

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

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

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

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

出力

$t$ 行出力せよ、ここで、 $i$ 行目には $i$ 番目のテストケースでの良い順列の個数を $10^9 + 7$ で割った余りを出力せよ。

入出力例

注記

1つ目のテストケースでは、全ての数が同じなので、どのような順列をとっても良い配列になります。 $1$ から $3$ までの数の順列は次のように合計で $6$ 通り存在します: $[1,\,2,\,3],$ $[1,\,3,\,2],$ $[2,\,1,\,3],$ $[2,\,3,\,1],$ $[3,\,1,\,2],$ $[3,\,2,\,1]$ 。

2つ目のテストケースでは、よい配列となるような順列が存在しないことを証明することができます。

3つ目のテストケースでは、よい配列となるような順列が合計で $36$ 通り存在しますそのうち1つが順列 $[1,\,5,\,4,\,2,\,3]$ であり、このとき列は $s = [0,\,0,\,3,\,2,\,0]$ となります。これがよい配列となるのは以下の通りです。

$s_1 = s_2 \: \& \: s_3 \: \& \: s_4 \: \& \: s_5 = 0$
$s_1 \: \& \: s_2 = s_3 \: \& \: s_4 \: \& \: s_5 = 0$
$s_1 \: \& \: s_2 \: \& \: s_3 = s_4 \: \& \: s_5 = 0$
$s_1 \: \& \: s_2 \: \& \: s_3 \: \& \: s_4 = s_5 = 0$

Add One / Добавь единицу (1500点)

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

整数 $n$ が与えられます。それに $m$ 回操作を適用させなければなりません。

1回の操作では、数の各桁 $d$ を $d+1$ の十進数表現に置き換えなければなりません。例えば、 $1912$ は1回の操作を適用させると $21023$ となります。

$m$ 回の操作を適応させた後の $n$ の長さを求めなければなりません。この数は大きくなる可能性があるので、modulo $10^9 + 7$ で出力してください。

入力

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

各テストケースの唯一の行には2つの整数 $n$ $(1 \leq n \leq10^9, [tex:m$ $(1 \leq m \leq 2 \times 10^5)$ が与えられる、これらは初期状態の数と操作回数である。

出力

各テストケースについて結果として得られる数の長さを $10^9 + 7$ で割った余りを出力せよ。

入出力例

注記

1つ目のテストケースについて、 $1912$ は $1$ 回の操作の後 $21023$ となり、その長さは $5$ となります。

2つ目のテストケースについて、 $5$ は $6$ 回の操作の後 $21$ となり、その長さは $2$ となります。

3つ目のテストケースについて、 $999$ は $1$ 回の操作の後 $101010$ となり、その長さは $6$ となります。

4つ目のテストケースについて、 $88$ は $2$ 回の操作の後 $1010$ となり、その長さは $4$ となります。

D. GCD and MST / НОД и МОД (2000点)

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

$n$ $(n \geq 2)$ 個の正整数から成る配列 $a$ と整数 $p$ が与えられます。頂点 $i$ と $j$ $(i \lt j)$ の間の辺が次のようにして追加される $1$ から $n$ までの番号がついた $n$ 個の頂点からなる重み付き無向グラフを考えます。

$gcd(a_i,\,a_{i+1},\,a_{i+2},\,\dots,\,a_j) = min(a_i,\,a_{i+1},\,a_{i+2},\,\dots,\,a_j)$ である場合、 $i$ から $j$ の間に重さ $min(a_i,\,a_{i+1},\,a_{i+2},\,\dots,\,a_j)$ の辺が存在する
$i + 1 = j$ である場合、 $i$ と $j$ の間に重さ $p$ の辺が存在する

ここで $gcd(x,\,y,\,\dots)$ は整数 $x,\,y,\,\dots$ の最大公約数(greatest common divisor, GCD)*2を表します。

上記の条件の両方を満たす場合、 $i$ と $j$ の間には多重辺が存在し、何方の条件も満たさない場合、 $i$ と $j$ の間には辺が存在しないことに注意してください。

目標は、このグラフの最小全域木(minimum spanning tree, MST)*3の重みを求めることです。

入力

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

各テストケースの1行目には2つの整数 $n$ $(2 \leq n \leq 2 \cdot 10^5),$ $p$ $(1 \leq p \leq 10^9)$ が与えられる、これらは頂点数とパラメータ $p$ である。

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

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

出力

$t$ 行出力せよ。各テストケースでについて対応するグラフの重さを出力せよ。

入出力例

4
2 5
10 10
2 5
3 3
4 5
5 2 4 9
8 8
5 3 3 6 10 100 9 15

注記

ここでは、例題の4つのテストケースのグラフを示しています(グラフの可能なMSTの辺はピンク色で示されています)。
テストケース1について
f:id:Flkanjin:20210412183948p:plain
テストケース2について
f:id:Flkanjin:20210412184017p:plain
テストケース3について
f:id:Flkanjin:20210412184118p:plain
テストケース4について
f:id:Flkanjin:20210412184143p:plain

E. Cost Equilibrium / Ценовой баланс (2750点)

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

配列の全ての要素が等しい場合、その配列は美しいといいます。

以下の手順で、配列を任意の回数変換することができます。

2つのインデックス $i,\,j$ $(1 \leq i,\,j \leq n)$ と整数 $x$ $(1 \leq x \leq a_i)$ を選ぶ。 $i$ をソースインデックス、 $j$ をシンクインデックスとする
$i$ 番目の要素を $x$ だけ減らし、 $j$ 番目の要素を $x$ だけ増やす。 $i$ 番目と $j$ 番目で得られる値はそれぞれ $a_i - x,$ $a_j + x$ となる
この操作のコストは $x \cdot |j - i|$ である
ここで、 $i$ がシンクインデックス、 $j$ がソースインデックスになることはなくなる

変換の総コストはステップ $3$ の全てのコストの合計です。
例えば、配列 $[0,\,2,\,3,\,3]$ は総コスト $1 \cdot |1-3| + 1 \cdot |1-4| = 5$ で美しい配列 $[2,\,2,\,2,\,2]$ に変換できます。

美しい配列に変換することができ、その変換のコストが一意に定まる配列をバランス型といいます。言い換えれば、美しい配列に変換するための最小のコストは、最大のコストに等しいものです。

非負整数から成る長さ $n$ の配列 $a_1,\,a_2,\,\dots,\,a_n$ が与えられます。貴方の仕事は、与えられた配列の並べ替えであるバランス型の配列の数を求めることです。要素が異なる位置が存在する場合2つの配列は異なる配列とみなされます。答えが大きくなる可能性があるため、modulo $10^9+7$ で出力して下さい。

入力

1行目には単一の整数 $n$ $(1 \leq n \leq 10^5)$ が与えられる、これは配列の大きさである。

2行目には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(0 \leq a_i \leq 10^9)$ が与えられる。

出力

単一の整数を出力せよ、これはバランス型である並び替えの数を $10^9 + 7$ で割った余りである。

入出力例

3
1 2 3

4
0 4 0 4

5
0 11 12 13 14

注記

1つ目の入出力例では、値 $3$ のインデックスをソース、値 $1$ のインデックスをシンクと考えることができるので、 $[1,\,2,\,3]$ は有効な並び替えです。したがって、変換後は美しい配列 $[2,\,2,\,2]$ となり，総コストは $2$ となります。これが美しい配列になる唯一の変換であることを示すことができます。同様に他の並び替えについても調べることができます。