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

A. Square Counting / Сколько квадратов? (750点)
- 入力
- 出力
- 入出力例
- 注記
B. Quality vs Quantity / Качество против количества (1000点)
- 入力
- 出力
- 入出力例
- 注記
C. Factorials and Powers of Two / Факториалы и степени двойки (1250点)
- 入力
- 出力
- 入出力例
- 注記
D. Weight the Tree / Взвесьте дерево (2000点)
- 入力
- 出力
- 入出力例
- 注記
E. Power Board / Степенная таблица (2500点)
- 入力
- 出力
- 入出力例
- 注記
F. Playing Around the Table / Игра вокруг стола (3000点)
- 入力
- 出力
- 入出力例
- 注記

A. Square Counting / Сколько квадратов? (750点)

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

Luis*1は $n+1$ 個の整数 $a_1,\,a_2,\,\dots,\,a_{n+1}$ を持っています。各 $i = 1,\,2,\,\dots,\,n+1$ について、 $0 \leq a_i \lt n$ または $a_i = n^2$ であることが分かっています。彼は数列の全要素の和を計算し、その値を $s$ としました。

Luisは数列を失くしてしまいましたが、 $n$ と $s$ の値は覚えています。数列の要素のうち、 $n^2$ に等しいものの個数を求めることができますか?

与えられた制約のもとでは答えが一意であることは証明できます。

入力

各テストは複数のテストケースが含まれる。1行目にはテストケースの個数 $t$ $(1 \leq t \leq 2 \cdot 10^4)$ が与えられる。以下、テストケースの記述が続く。

各テストケースの唯一の行には2個の整数 $n,\,s$ $(1 \leq n \leq 10^6,$ $0 \leq s \leq 10^{18})$ が与えられる。 $s$ の値は、上記の制約を満足する数列の和として有効なものであることが保証されている。

出力

各テストケースについて、単一の整数を出力せよ、その数とは数列内の $n^2$ に等しい項の個数である。

入出力例

注記

1つ目のテストケースでは、 $s = 0$ であるため、全ての数が $0$ であり、 $49$ となる数は存在しません。

2つ目のテストケースでは、 $s = 1$ です。可能な数列は2つあります: $[0,\,1],$ $[1,\,0]$ 。どちらの場合でも、数 $1$ は一度だけ現れます。

3つ目のテストケースでは、 $s = 12$ で、このケースでの $s$ の可能な最大値です。そのため、数 $4$ は数列内に $3$ 回現れます。

B. Quality vs Quantity / Качество против количества (1000点)

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

$n$ 個の非負整数 $a_1,\,a_2,\,\dots,\,a_n$ が与えられます。初期状態では、数列のどの要素も彩色されていません。各数を $\color{red}{\underline{\text{赤}}}$ か $\color{blue}{\overline{\text{青}}}$ に塗ることができ(両方は不可)、塗らないままにしておくこともできます。

色 $c$ について、 $\operatorname{Count}(c)$ は数列内のその色で塗られた要素数、 $\operatorname{Sum}(c)$ は数列内のその色で塗られた要素の和を表します。

例えば、与えられた数列が $[2,\,8,\,6,\,3,\,1]$ で、次のように彩色します: $[\color{blue}{\overline{2}},\,8,\,\color{red}{\underline{6}},\,\color{blue}{\overline{3}},\,1]$ ( $6$ は赤に、 $2$ と $3$ は青に塗られ、 $1$ と $8$ は無彩色)。この時、 $\operatorname{Sum}(\color{red}{\underline{\text{赤}}}) = 6,$ $\operatorname{Sum}(\color{blue}{\overline{\text{青}}}) = 2 + 3 = 5,$ $\operatorname{Count}(\color{red}{\underline{\text{赤}}}) = 1,$ $\operatorname{Count}(\color{blue}{\overline{\text{青}}}) = 2$ となります。

$\operatorname{Sum}(\color{red}{\underline{\text{赤}}}) \gt \operatorname{Sum}(\color{blue}{\overline{\text{青}}})$ かつ $\operatorname{Count}(\color{red}{\underline{\text{赤}}}) \lt \operatorname{Count}(\color{blue}{\overline{\text{青}}})$ となるように数列を塗り分けることができるか判別してください。

入力

各テストは複数のテストケースが含まれる。1行目にはテストケースの個数 $t$ $(1 \leq t \leq 1000)$ が与えられる。以下、テストケースの記述が続く。

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

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

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

出力

各テストケースについて、与えられた数列を上記の要件を満たすように塗ることが可能であればYESと出力せよ、そうでなければNOと出力せよ。

YESとNOはどのレターケースで出力してもよい(例えば、文字列yEs, yes, Yes, YESは肯定とみなされる)。

入出力例

4
3
1 2 3
5
2 8 6 3 1
4
3 5 4 2
5
1000000000 1000000000 1000000000 1000000000 1000000000

NO
YES
NO
NO

注記

1つ目の入力例では、条件を満たす数列の彩色方法はありません。例えば、次のように彩色したとします: $[\color{blue}{\overline{1}},\,\color{blue}{\overline{2}},\,\color{red}{\underline{3}}]$ ( $3$ は赤、 $1$ と $2$ は青)。この時、 $\operatorname{Count}(\color{red}{\underline{\text{赤}}}) = 1 \lt \operatorname{Count}(\color{blue}{\overline{\text{青}}}) = 2$ ですが、 $\operatorname{Sum}(\color{red}{\underline{\text{赤}}}) = 3 \ngtr \operatorname{sum}(\color{blue}{\overline{\text{青}}}) = 3$ です。そのため、これは条件を満たす数列の彩色方法ではありません。

2つ目の入力例では、問題文で記述されているように塗ることができます。 $\operatorname{Sum}(\color{red}{\underline{\text{赤}}}) = 6 \gt \operatorname{Sum}(\color{blue}{\overline{\text{青}}}) = 5,$ $\operatorname{Count}(\color{red}{\underline{\text{赤}}}) = 1 \lt \operatorname{Count}(\color{blue}{\overline{\text{青}}}) = 2$ であることが確認できます。

3つ目の入力例では、条件を満たす数列の彩色方法はありません。例えば、次のように彩色したとします: $[\color{red}{\underline{3}},\,\color{red}{\underline{5}},\,\color{blue}{\overline{4}},\,\color{blue}{\overline{2}}]$ ( $3$ と $5$ は赤、 $4$ と $2$ は青)。この時、 $\operatorname{Sum}(\color{red}{\underline{\text{赤}}}) = 8 \gt \operatorname{Sum}(\color{blue}{\overline{\text{青}}}) = 6$ ですが、 $\operatorname{Count}(\color{red}{\underline{\text{赤}}}) = 2 \nless \operatorname{Count}(\color{blue}{\overline{\text{青}}}) = 2$ ] です。そのため、これは条件を満たす数列の彩色方法ではありません。

4つ目の入力例では、sumとcountの制約を満たす数列の塗り分けは不可能であることを証明することができます。

C. Factorials and Powers of Two / Факториалы и степени двойки (1250点)

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

ある数が2の累乗か、階乗である場合、その数を強力であるといいます。つまり、 $m = 2^d$ または $m = d!$ であるような非負整数 $d$ が存在するとき、数 $m$ は強力であるといいます、ここで $d! = 1 \cdot 2 \cdot \cdots \cdot d$ (また特別に $0! = 1$ ) を表します。例えば $1,$ $4,$ $6$ は $1 = 1!,$ $4 = 2^2,$ $6 = 3!$ であるので強力な数ですが、 $7,$ $10,$ $18$ はそうではありません。

正整数 $n$ が与えられます。 $n$ が $k$ 個の相異なる強力な数の和として表現できるような最小の数 $k$ を求めて下さい、もしくは、そのような $k$ が存在しないことを判別してください。

入力

各テストは複数のテストケースが含まれる。1行目にはテストケースの個数 $t$ $(1 \leq t \leq 100)$ が与えられる。以下、テストケースの記述が続く。

各テストケースはただ1つの行から成り、1個の整数 $n$ $(1 \leq n \leq 10^{12})$ が与えられる。

出力

各テストケースについて、別々の行に答えを出力せよ。

$n$ が相異なる強力な数の和として表現できない場合は、 $-1$ を出力せよ。

そうでない場合、単一の正整数を出力せよ、その数とは、 $k$ の可能な最小値である。

入出力例

4
7
11
240
17179869184

注記

1つ目のテストケースでは、 $7$ は $7 = 1 + 6$ と表現することができ、 $1$ と $6$ は強力な数です。 $7$ は強力な数ではないので、このケースでの $k$ の可能な最小値は $k = 2$ であることが分かります。

2つ目のテストケースでは、 $11$ を3個の強力な数の和として表現できる方法として $11 = 1 + 4 + 6$ が考えられます。 $11$ を2個以下の強力な数の和として表現することができないことを証明することができます。

3つ目のテストケースでは、 $240$ は $240 = 24 + 32 + 64 + 120$ と表現することができます。強力な数は相異ならなければならないので $240 = 120 + 120$ は有効な表現でないことに注意して下さい。

4つ目のテストケースでは、 $17179869184 = 2^{34}$ であるため、 $17179869184$ は強力な数であり、このケースの最小の $k$ は $k = 1$ です。

D. Weight the Tree / Взвесьте дерево (2000点)

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

$1$ から $n$ の番号を附けられた $n$ 個の頂点の木が与えられます。木とはサイクルの無い連結無向グラフのことです。

各 $i = 1,\,2,\,\dots,\,n$ について、 $i$ 番目の頂点の重みを $w_i$ とします。その重みが全ての隣接頂点の重みの和と等しい時、その頂点は良いと言います。

初期状態では、全ての頂点の重みは未定義です。木内の良い頂点の数が最大になるように、各頂点に正整数の重みを割り当てて下さい。複数の方法がある場合は、木の全頂点の重みの和を最小にする方法を求めて下さい。

入力

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

その後、 $n-1$ 行が続く。各行には、頂点 $u$ と $v$ の間の辺を表す2個の整数 $u,\,v$ $(1\leq u,\,v \leq n)$ が与えられる。辺が木を形成することは保証されている。

出力

1行目には、2個の整数を出力せよ、その数とは良い頂点の最大数とその最大値に対する重みの和の可能な最小値である。

2行目には、 $n$ 個の整数 $w_1,\,w_2,\,\dots,\,w_n$ $(1 \leq w_ i \leq 10^9)$ を出力せよ、これらは各頂点に割り当てられた重みである。これらの制約を満たす最適解が存在することは証明することができる。

複数の最適解が存在する場合は、いずれを出力してもよい。

入出力例

3 4
1 1 1 1

3
1 2
1 3

2 3
1 1 1

2
1 2

2 2
1 1

6 11
1 1 1 1 1 1 1 3 1

注記

1つ目のテストケースでの木はこちらです。

f:id:Flkanjin:20220305151214p:plain:w300

このケースでは、各頂点に重み $1$ を割り当てると、良い頂点(黒)は $1,$ $3,$ $4$ となります。全ての頂点を良い頂点にするように重みを割り当てることはできません。このケースでの重みの和の最小値は $1 + 1 + 1 + 1 = 4$ であり、重みは正整数でなければならないので、和をこれより小さくすることはできません。
2つ目のテストケースでの木はこちらです。

f:id:Flkanjin:20220305163135p:plain:w300

このケースでは、各頂点に重み $1$ を割り当てると、良い頂点(黒)は $2,$ $3$ となります。これが最適な割り当てであることを示すことができます。

E. Power Board / Степенная таблица (2500点)

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

大きさ $n \times m$ ( $n$ 行 $m$ 列)の長方形のボードがあります。 $n$ 個の行には上から下へ [tex1] から $n$ までの番号が、 $m$ 個の列には左から右へ [tex1] から $m$ までの番号が振られています。

$i$ 行と $j$ 列の交点にあるセルには $i^j$ ( $i$ の $j$ 乗)が書かれています。例えば、 $n = 3,$ $m = 3$ であるとき、このボードは次のようになります。

ボード上に書かれた相異なる整数の数を求めて下さい。

入力

唯一の行には2個の整数 $n,\,m$ $(1 \leq n,\, m \leq 10^6)$ が与えられる、これらはボードの行と列の数である。

出力

1個の整数を出力せよ、その数とはボード上の相異なる整数の数である。

入出力例

3 3

2 4

4 2

注記

問題文には、1つ目のテストケースでのボードが示されています。このケースでは $1,$ $2,$ $3,$ $4,$ $8,$ $9,$ $27$ の $7$ 個の相異なる整数が書かれています。

2つ目のテストケースでは、ボードは次のようになります。

$1,$ $2,$ $4,$ $8,$ $16$ の $5$ 個の相異なる整数が書かれています。

3つ目のテストケースでは、ボードは次のようになります。

$1,$ $2,$ $3,$ $4,$ $9,$ $16$ の $6$ 個の相異なる整数が書かれています。

F. Playing Around the Table / Игра вокруг стола (3000点)

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

$1$ から $n$ の番号が振られた $n$ 人のプレイヤーが円卓を囲むように座っています。 $1 \leq i \lt n$ について $(i + 1)$ 番目のプレイヤーは $i$ 番目のプレイヤーの右側に座っていて、 $1$ 番目のプレイヤーは $n$ 番目のプレイヤー右側に座っています。

$1$ から $n$ までの整数が1つ書かれているカードが $n^2$ 枚あります。 $1$ から $n$ までの各整数について、ちょうど $n$ 枚のカードにこの数が書かれています。

始めに、各プレイヤーがちょうど $n$ 枚のカードを持っているように、カードがプレイヤーに分配されます。1ステップで各プレイヤーは自分のカードを1枚選び、右側のプレイヤーに渡します。全プレイヤーが同時にこのステップを実行します。

プレイヤー $i$ が持っている全てのカードに整数 $i$ が書かれている場合、そのプレイヤーはsolidであるといいます。プレイヤーの目的は、全員がsolidであるカード配置にすることです。 $(n^2 - n)$ 回以内の操作で実現できる方法を求めて下さい。操作数を最小化する必要はありません。

入力

1行目には1個の整数 $n$ $(2 \leq n \leq 100)$ が与えられる。

それから $n$ 行が続く。その $i$ 行目には $n$ 個の整数 $c_1,\,c_2,\,\dots,\,c_n$ $(1 \leq c_j \leq n)$ が与えられる、これらは $i$ 番目のプレイヤーの初期カードである。

$1$ から $n$ までの各整数 $i$ について、数 $i$ が書かれたカードがちょうど $n$ 枚あることは保証されている。

出力

1行目には、1個の整数 $k$ $(0 \leq k \leq (n^2 - n))$ を出力せよ、これは操作数である。

その後、 $k$ 行を続けよ。その $i$ 行目には $n$ 個の整数 $d_1,\,d_2,\,\dots,\,d_n$ $(1 \leq d_j \leq n)$ を出力せよ。ここで、 $d_j$ は $j$ 番目のプレイヤーが右隣のプレイヤーに渡したカードに書かれている数字である。

与えられた制約の中で、必ず答えが存在することを示すことはできる。複数の解がある場合は、いずれかを出力せよ。

入出力例

2
2 1
1 2

1
2 1

注記

1つ目のテストケースでは、1番目のプレイヤーが数 $2$ のカードを、2番目のプレイヤーが数 $1$ のカードをパスすると、1番目のプレイヤーは数 $1$ のカードを2枚、2番目のプレイヤーは数 $2$ のカードを2枚持っていることになります。そして、この操作を行った後、両プレイヤーはsolidとなります。

2つ目のテストケースでは、 $0$ 回の操作で十分です。操作回数を最小化する必要はないことに注意してください。

*1:西[lwis]、ルイス: 高地ゲルマン語のHlūtwīg(名高い戦い)に由来する名前、Lewis(英)、Louis(仏)、Luigi(伊)、Ludwig(独)等と同語源