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

Codeforces 競技プログラミング Codeforces 和訳 Codeforces Div. 2 和訳

A. Add and Divide / Прибавляй и дели (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
2つの正整数 a,\,b があります。

以下の2種類の操作を行うことができます。

  • a = \displaystyle\left\lfloor\frac{a}{b} \right\rfloor (a を b で割った時の商の整数部分に a を置き換える)
  • b = b+1 (b を 1 だけ大きくする)

a=0 にするために必要な操作回数の最小値を求めてください。

入力

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

各テストケースについての記述の唯一の行には2つの整数 a, b (1 \leq a,\,b \leq 10^9) が与えられる。

出力

各テストケースについて単一の整数を出力せよ、その整数は a = 0 とするために必要な操作回数の最小値である。

入出力例

6
9 2
1337 1
1 1
50000000 4
991026972 997
1234 5678
4
9
2
12
3
1

注記

最初のテストケースにおいて、最適解の1一つは次のようなものです。

  1. a を b で割る。操作後 a=4,\,b=2 となる。
  2. a を b で割る。操作後 a=2,\,b=2 となる。
  3. b を大きくする。操作後 a=2,\,b=2 となる。
  4. a を b で割る。操作後 a=0,\,b=3となる。

B. Replace and Keep Sorted / Замена и возрастание (1000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
正整数 k が与えらたとき、2つの配列が以下の場合、k-類似しているといいます。

  • どちらの配列も狭義単調増加である
  • 長さが同じである
  • それらの全ての要素は 1 から k (両端を含む)の正整数である
  • ちょうど1つの位置の要素が異なる

整数k、狭義単調増加列 a と q 個のクエリが与えられます。各クエリについて、2つの整数 l_i \leq r_i が与えられます。配列 [a_{l_i},\,a_{l_i+1},\,\dots,\,a_{r_i}] に k-類似するような配列 b が何個あるかを求めてください。

入力

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

2行目にはn個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq k) が与えられる。この配列は狭義単調増加である。即ち、a_1 \lt a_2 \lt \dots \lt a_n。

続く q 列には2つの整数 l_i,\,r_i (1 \leq l_i \leq r_i \leq n) が与えられる。

出力

q 行出力せよ。i 行目には i 番目のクエリに対する答えを出力せよ。

入出力例

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

注記

最初の例において

1個目のクエリについて [2,\,4] に 5-類似する配列は 4 つ存在します: [1,\,4], [3,\,4], [2,\,3], [2,\,5]。

2個目のクエリについて [4,\,5] に 5-類似する配列は 3 つ存在します: [1,\,5], [2,\,5], [3,\,5]。

C. Floor and Mod / Деление и остаток (1500点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
\displaystyle\left\lfloor\frac{a}{b} \right\rfloor = a \bmod b となるとき正整数の組 (a,\,b) を特別と呼びます。ここで、\displaystyle\left\lfloor \frac{a}{b} \right\rfloor は a を b で割った時の整数商で a \bmod b はそのあまりです。

2整数 x,\,y が与えられます。1 \leq a \leq x と 1 \leq b \leq y を満たす特別な組 (a,\,b) の個数を求めてください。

入力

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

各テストケースについての記述の唯一の行には2つの整数 x,\,y (1 \leq x,\,y \leq 10^9) が与えられる。

出力

各テストケースに対する答えをそれぞれ単一行に出力せよ。

入出力例

9
3 4
2 100
4 3
50 3
12 4
69 420
12345 6789
123456 789
12345678 9
1
0
2
3
5
141
53384
160909
36

注記

1つ目のテストケースにおいて、特別な組はただ1組存在します: (3,\,2)。

2つ目のテストケースにおいて、特別な組は存在しません。

3つ目のテストケースにおいて、特別な組は2組存在します: (3,\,2) と (4,\,3)。

D. Multiples and Power Differences / Делители и степенные разности (1750点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
正整数からなる行列 a が与えられます。a は n 行 m 列です。

正整数からなる行列 b を構成してください。b は a と同じサイズであり、次の条件を満たしていなければなりません。

  • 1 \leq b_{i, j} \leq 10^6
  • b_{i, j} は a_{i, j} の倍数である
  • b 内の任意の隣接する要素のペア(同じ辺を共有する2つの要素)の差の絶対値はある整数 k \geq 1 について k^4 である(k は全てのペアで同じである必要はなく、各ペアで独自のものでよい)

答えが常に存在することは証明できます。

入力

1行目には2つの整数 n,\,m (2 \leq n,\,m \leq 500)が与えられる。

続く n 行にはそれぞれ m 個の整数が与えられる。i 行目の j 番目の整数は a_{i,j} (1 \leq a_{i,j} \leq 16) である。

出力

m 個の整数を含む n 行を出力せよ。i 行目の j 番目の整数は b_{i,j} である。

入出力例

2 2
1 2
2 3
1 2
2 3
2 3
16 16 16
16 16 16
16 32 48
32 48 64
2 2
3 11
12 8
327 583
408 664

注記

1つ目のテストケースでは、任意の隣接する要素ペアの差の絶対値が 1 = 1^4 であるため、行列 a を行列 b として用いることができます。

3つ目のテストケースにについて

  • 327 は 3 の倍数、583 は 11 の倍数、408 は 12 の倍数、664 は 8 の倍数
  • |408-327| = 3^4, |538-327| = 4^4, |664-408| = 4^4, |664-538| = 3^4

E. Move and Swap / Передвижения и замены (2500点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n - 1 個の整数 a_2,\,\dots,\,a_n と頂点数 n の頂点 1 を根とする木が与えられます。根から葉の距離は全て d です。

木とはサイクルをもたない連結無効グラフです。2つの頂点間の距離はそれらを結ぶ単純パス上の辺の数です。根でない次数 1 の頂点は全て葉です。頂点 f と s が辺で結ばれていて、根から f までの距離が根から s までの距離よりも大きい時、f は s の子と呼ばれます。

初期状態において、頂点 1 に赤いコインと青いコインが置かれています。r を赤いコインがある頂点、b を青いコインがある頂点とします。d 回の移動を施さなければなりません。1回の移動は次の3ステップからなります。

  • r の任意の子に赤いコインを移動させる
  • dist(i,\,b') = dist(i,\,b) + 1 となるような任意の頂点 b' に青いコインを移動させる。ここで dist(x,\,y) とは x と y の間の単純パスの長さを表す。b と b' が辺で結ばれてなくてもよいことに注意せよ
  • 2枚のコインを任意で入れ替えることができる(このステップは省略可)

r と b はいつでも等しくなる可能性があり、根には数字が書かれていないことに注意してください。

移動を施すたび |a_r - a_b| 点を得ます。d 回移動を施したあとに得られる最大点数は何点でしょうか?

入力

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

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

各テストケースの2行目には n - 1 個の整数 v_2,\,v_3,\,\dots,\,v_n (1 \leq v_i \leq n, v_i \neq i) が与えられる、i 番目の数は頂点 i と v_i の間に辺があることを表す。これらの辺が木を形成することは保証されている。

各テストケースの3行目には n - 1 個の整数 a_2,\,a_3,\,\dots,\,a_n (1 \leq a_i \leq 10^9) が与えられる、a_i は頂点に書かれた数字である。

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

出力

各テストケースについて単一の整数を出力せよ、その整数は d 回移動を施した後に得られる最大点数である。

入出力例

4
14
1 1 1 2 3 4 4 5 5 6 7 8 8
2 3 7 7 6 9 5 9 7 3 6 6 5
6
1 2 2 3 4
32 78 69 5 41
15
1 15 1 10 4 9 11 2 4 1 8 6 10 11
62 13 12 43 39 65 42 86 25 38 19 19 43 62
15
11 2 7 6 9 8 10 1 1 1 5 3 15 2
50 19 30 35 9 45 13 24 8 44 16 26 10 40
14
45
163
123

注記

1番目のテストケースでは最適解は以下のものです。

  • 移動 1: r=4,\,b=2、入れ替えなし
  • 移動 2: r=7,\,b=6、入れ替えあり(入れ替え後はr=6,\,b=7)
  • 移動 3: r=11,\,b=9、入れ替えなし

合計点数は |7 - 2| + |6 - 9| + |3 - 9| = 14 となります。(図は問題文のページ参照)

2番目のテストケースでは最適解は以下のものです。

  • 移動 1: r=2,\,b=2、入れ替えなし
  • 移動 2: r=3,\,b=4、入れ替えなし
  • 移動 3: r=5,\,b=6、入れ替えなし

合計点数は |32 - 32| + |78 - 69| + |5 - 41| = 45 となります。

F. Copy or Prefix Sum / Копия или префиксная сумма (3000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
整数列 b_1,\, b_2,\,\dots,\,b_n が与えられる。

それぞれの i (1 \leq i \leq n) において以下の条件の内少なくとも1つを満たすとき整数列 a_1,\,a_2,\,\dots,\,a_n はハイブリッドであるといいます。

  • b_i = a_i
  • b_i = \displaystyle\sum_{j=1}^{i}\ a_j

ハイブリッドな配列 a_1,\,a_2,\,\dots,\,a_n の個数を求めてください。答えは非常に大きくなることがあるため、答えをmodulo 10^9+7*1 で出力してください。

入力

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

各テストケースの1行目には単一の整数 n (2 \leq n \leq 2 \cdot 10^5) が与えられる。

各テストケースの2行目には n 個の整数 b_1,\,b_2,\,\dots,\,b_n (-10^9 \leq b_i \leq 10^9) が与えられる。

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

出力

各テストケースについて単一の整数を出力せよ、その整数はハイブリッドな配列 a_1,\,a_2,\,\dots,\,a_n の個数のmodulo 10^9+7 である。

入出力例

4
3
1 -1 1
4
1 2 3 4
10
2 -1 1 -2 2 3 -5 0 2 -1
4
0 0 0 1
3
8
223
1

注記

1番目のテストケースにおけるハイブリッドな配列は [1,\,-2,\,1], [1,\,-2,\,2], [1,\,-1,\,1] です。

2番目のテストケースにおけるハイブリッドな配列は [1,\,1,\,1,\,1], [1,\,1,\,1,\,4], [1,\,1,\,3,\,-1], [1,\,1,\,3,\,4], [1,\,2,\,0,\,1], [1,\,2,\,0,\,4], [1,\,2,\,3,\,-2], [1,\,2,\,3,\,4] です。

4番目のテストケースにおけるハイブリッドな配列は [0,\,0,\,0,\,1] です。

*1:10^9+7 であった余り