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

Codeforces 競技プログラミング Codeforces 和訳 インタラクティブ 和訳 Codeforces Div. 2 和訳

A. Shifting Stacks / Сдвигая стопки (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
ブロックのスタックが n 個あります。i 番目のスタックには h_i 個のブロックが入っていて、そのスタックの高さはブロックの個数です。1手で(少なくともブロックが1個以上ある場合) i 番目のスタックから i + 1 番目のスタックへブロックを1個移動させることができます。高さの列を狭義単調増加にすることができるでしょうか?

スタックの数は常に n 個であることに気を付けてください。ブロックの数が 0 個になってもスタックは消えません。

入力

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

各テストケースの1行目には単一の整数 n (1 \leq n \leq 100) が与えられる。各テストケースの2行目には n 個の整数 h_i (0 \leq h_i \leq 10^9) が与えられる、これらの数はスタックの高さである。

全ての n の和が 10^4 を超えないことは保証されている。

出力

各テストケースについて高さの列を狭義単調増加にすることができる場合YESを、そうでない場合NOを出力せよ。

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

入出力例

6
2
1 2
2
1 0
3
4 4 4
2
0 0
3
0 1 0
4
1000000000 1000000000 1000000000 1000000000
YES
YES
YES
NO
NO
YES

注記

1つ目のテストケースでは、手を打つ必要はありません、最初から高さの列は増加列です。

2つ目のテストケースでは、ブロックを1つ、1つ目のスタックから2つ目のスタックへ移動させる必要があります。そうすれば、高さは 0\ 1 となります。

3つ目のテストケースでは、ブロックを1つ、1つ目のスタックから2つ目のスタックへ移動させ、2つ目のスタックから3つ目のスタックへ移動させると、高さは 3\ 4\ 5 となります。

4つ目のテストケースでは、何も手を打つことができませんが、列は増加列ではないため、答えはNOとなります。

5つ目のテストケースでは、たった1手(2番目のスタックから3番目のスタックへの移動)しかすることができず、このとき高さは 0\ 0\ 1 となります。0\ 1\ 0 も 0\ 0\ 1 も増加列ではないため、答えはNOとなります。

B. Eastern Exhibition / Восточная выставка (1000点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
貴方と友人は n 個の家に住んでいます。それぞれの家は2次元平面上の、整数座標上に位置します。同一座標上に複数の家が存在する場合もあります。市長は東方博覧会用の建物を建てるための場所を求めています。全ての家から博覧会までの距離の合計が最小となるような場所(整数座標上)の数を求めなければなりません。博覧会はいずれかの家と同じ地点に立てることも可能です。2点 (x_1,\, y_1) と (x_2,\, y_2) 間の距離は |x_1 - x_2| + |y_1 - y_2| で、ここでの |x| は x の絶対値です。

入力

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

各テストケースの1行目には単一の整数 n (1 \leq n \leq 1000) が与えられる。続く n 行には家の位置 (x_i,\, y_i) (0 \leq x_i,\, y_i \leq 10^9) が与えられる。

全ての n の和が 1000 を超えないことは保証されている。

出力

各テストケースについて単一の整数を出力せよ、その整数とは、博覧会を建てることのできる位置の数である。博覧会はいずれかの家と同じ地点に立てることも可能である。

入出力例

6
3
0 0
2 0
1 2
4
1 0
0 2
2 3
3 1
4
0 0
0 1
1 0
1 1
2
0 0
1 1
2
0 0
2 0
2
0 0
0 0
1
4
4
4
3
1

注記

以下にテストケースの例の図を示します。青点は家を、緑点は博覧会を建てる可能性のある位置を表しています。
f:id:Flkanjin:20210220155912p:plain:w387
1つ目のテストケースです。

f:id:Flkanjin:20210220160146p:plain:w355
2つ目のテストケースです。

f:id:Flkanjin:20210220160324p:plain:w296
3つ目のテストケースです。

f:id:Flkanjin:20210220160437p:plain:w378
4つ目のテストケースです。

f:id:Flkanjin:20210220160526p:plain:w413
5つ目のテストケースです。

f:id:Flkanjin:20210220160639p:plain
6つ目のテストケースです。2つの家のどちらも (0,\, 0) に位置しています。

C1. Guessing the Greatest (easy version) / Найти наибольшее (простая версия) (750点)
C2. Guessing the Greatest (hard version) / Найти наибольшее (сложная версия) (750点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
イージー版とハード版の違いはクエリの制限数のみです。

この問題はインタラクティブ問題です。

異なる n 個の数から成る配列 a があります。1回のクエリで部分列 a[l. . r] 内で2番目に大きい要素の位置を尋ねることができます。40(イージー版)/20(ハード版)回以内のクエリで配列内の最大要素の位置を求めてください。

部分列 a[l. . r] は a_l,\,a_{l+1},\,\dots,\,a_r の要素全てです。この部分列について尋ねると、この部分列内で2番目に大きい要素の全体配列内の位置が与えられます。

入力

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

相互入出力

"\texttt{?}\ \ l\ \ r"と出力することでクエリを投げることができる。その返答は a_l,\,a_{l+1},\,\dots,\,a_r の全ての要素内の2番目に大きい要素のインデックスである。配列 a は予め固定されていて、相互入出力の際に変わることはない。

"\texttt{!}\ \ p"と出力することで答えを出力することができる、ここで p とは配列内の最大要素のインデックスである。

40(イージー版)/20(ハード版)回までクエリを投げることができる。答えの出力はクエリとしてカウントされない。

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

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

ハックケース

ハックを行うには、次のテスト形式に従いなさい。

1行目に単一の整数 n (2 \leq n \leq 10^5) を出力せよ。2行目に n 個の整数 1 から n の順列を出力せよ。n の位置が最大値の位置となる。

入出力例

5

3

4

? 1 5

? 4 5

! 1

注記

このサンプルでは a が [5,\,1,\,4,\,2,\,3] であるとします。部分列 [1..5] について尋ねた場合、4 が2番目に大きい要素で、その位置は 3 となります。部分列 [4..5] について尋ねた場合、2 が2番目に大きい要素で、その位置は 4 となります。

同じ相互入出力をする他の配列 a がありますが、答えは異なる可能性があります。出力例は相互入出力の理解のためにを示されています。

D. Max Median / Максимальная медиана (1750点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
長さ n の配列 a が与えられます。中央値が最大となる、長さが k 以上の部分列 a[l. .r] を求めてください。

長さ n の配列の中央値は、要素を昇順に並べ替えたのちの \displaystyle\left\lfloor \frac{n+1}{2} \right\rfloor の場所に位置する要素です。例えば median([1,\,2,\,3,\,4]) = 2, median([3,\,2,\,1]) = 2, median([2,\,1,\,2,\,1]) = 1*1となります。

部分列 a[l. .r] はある 1 \leq l \leq r \leq n についての配列 a_l,\,a_{l+1},\,\dots,\,a_r であり、その長さは r - l + 1 です。

入力

1行目には2つの整数 n,\,k (1 \leq k \leq n \leq 2 \cdot 10^5) が与えられる。

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

出力

1つの整数 m を出力せよ、m とは得られる中央値の最大値である。

入出力例

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

注記

1つ目の例では、可能な部分列は [1..3], [1..4], [1..5], [2..4], [2..5], [3..5] で全てであり、それらの中央値は全て 2 であるため、得られる中央値の最大値も 2 です。

2つ目の例では、median([3..4]) = 3 となります。

E. Paired Payment / Парный платёж (2250点)

テストごとの時間制限: 4秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
この国には n 個の都市と、m 本の双方向道路があります。この国の道路は重み付き無向グラフを形成します。このグラフが連結であるとは保証されていません。各道路にはパラメータ w があります。これらの道は通ることができますが、政府は新しい法律を定めました: 一度に2本の道路を通る(都市 a から都市 b へ行き、都市 b から都市 c へ行く)*2ことのみが許され、これらの道を通るためには (w_{ab} + w_{bc})^2 の金額を払わなければならない、という法律です。都市 1 から他の都市 t にそれぞれ行くことができるか、そして、1 から t へ行くために必要な最低金額を求めてください。

入力

1行目には2つの整数 n,\,m \biggl(2 \leq n \leq 10^5, 1 \lt m \lt min\displaystyle\left(\frac{n \cdot (n-1)}{2},\, 2 \cdot 10^5\right) \biggr) が与えられる。

続く m 行には3つの整数 v_i,\,u_i,\,w_i (1 \leq v_i,\,u_i \leq n, 1 \leq w_i \leq 50, u_i \neq v_i) が与えられる。多重辺がないこと、すなわち、任意の辺 (u_i,\,v_i) に対して (u_i,\,v_i) や (v_i,\,u_i) となる他の辺が存在しないことは保証されている。

出力

各都市 t について1つの整数を出力せよ。1 と t との間に有効なパスが存在しない場合、-1 を出力せよ。そうでない場合、1 から t へ行くために必要な最低金額を出力せよ。

入出力例

5 6
1 2 3
2 3 4
3 4 5
4 5 6
1 5 1
2 4 2
0 98 49 25 114
3 2
1 2 1
2 3 2
0 -1 9

注記

1つ目の例のグラフは次のようになります。
f:id:Flkanjin:20210220173825p:plain

2つ目の例では 1 から 3 へのパスは 2 を通り、結果として、(1 + 2)^2 = 9 を支払います。
f:id:Flkanjin:20210220173950p:plain

F. Pairs of Paths / Пары путей (3000点)

テストごとの時間制限: 6秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
n 頂点からなる木と m 個の単純頂点パスが与えられます。これらのパスのうち、正確に1つの頂点で交差する組が何組あるか求めてください。より形式的には、path_i と path_j がちょうど1個の頂点を共有するような組 (i,\,j) (i \leq i \lt j \leq m) の個数を求める必要があります。

入力

1行目には単一の整数 n (1 \leq n \leq 3 \cdot 10^5) が与えられる。

続く n - 1 行には木についての記述がなされる。各行には、頂点 u と頂点 v 間の辺を表す2つの整数 u,\,v (1 \leq u,\,v \leq n) が与えられる。

次の行には単一の整数 m (1 \leq m \leq 3 \cdot 10^5) が与えられる。

続く m 行にはパスについての記述がなされる。各行には、2つの端点 u,\,v (1 \leq u,\,v \leq n) によってパスが表される。与えられたパスは u から v までの最短パス (u,\,v 自身も含む)を表す。

出力

1つの整数を出力せよ、その整数は正確に1つの頂点で交差するパスの組の個数である。

入出力例

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

注記

f:id:Flkanjin:20210220190421p:plain
1つ目の例の木とパスは上のようになります。組 (1,\,4) と (3,\,4) が1つの頂点で交差します。

2つ目の例では3つの全てのパスが同じ単一の頂点を含むため、組 (1,\,2), (1,\,3), (2,\,3) の全てが1つの頂点で交差します。

3つ目の例は1つ目の例に2つのパスを追加したものです。組 (1,\,4), (1,\,5), (2,\,5), (3,\,4), (3,\,5), (3,\,6), (5,\,6) の全てが1つの頂点で交差します。

*1:medianなどは本来立体で表記するべきですが、原文に合わせて斜体で表記しています

*2:ちょうど2本でなければならない