Educational Codeforces Round 124 問題文和訳

A. Playoff / Плей-офф
- 入力
- 出力
- 入出力例
- 注記
B. Prove Him Wrong / Докажи, что он не прав
- 入力
- 出力
- 入出力例
- 注記
C. Fault-tolerant Network / Отказоустойчивая сеть
- 入力
- 出力
- 入出力例
- 注記
D. Nearest Excluded Points / Ближайшие точки
E. Sum of Matchings / Сумма паросочетаний
F. Tower Defense

A. Playoff / Плей-офф

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

$2^n$ 人の選手が出場するプレーオフトーナメントを考えます。選手には $1$ から $2^n$ の番号が振られています。

トーナメントは $n$ ラウンドで行われます。各ラウンドでは、各選手が、ちょうど1つの組に属するように組み分けを行います。それぞれの組で選手が競い合い、どちらかが勝ちます。勝者は次のラウンドに進み、敗者はトーナメントから脱落します。

組み分けは次のように行われます。

第1回戦では、選手 $1$ と選手 $2$ 、選手 $3$ と選手 $4$ 、選手 $5$ と選手 $6$ 、…というように戦います。
第2回戦では、 $1-2$ の試合の勝者と $3-4$ の試合の勝者、 $5-6$ の試合の勝者と $7-8$ の試合の勝者、…というように戦います。
その後のラウンドも同じルールで行われます。

選手 $x$ と $y$ が戦ったとき、勝者は次のように決まります。

$x+y$ が奇数の場合、番号が小さい選手が勝つ(つまり、 $x \lt y$ なら $x$ が勝ち、そうでないなら $y$ が勝つ)
$x+y$ が偶数の場合、番号が大きい選手が勝つ

次図は、 $n=3$ の時のトーナメントの様子です。
f:id:Flkanjin:20220311134131p:plain
ここでの課題は、「整数 $n$ が与えらえれたとき、優勝する選手の番号を判別すること」です。

入力

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

各テストケースは1行から成り、1個の整数 $n$ $(1 \leq n \leq 30)$ が与えられる。

出力

各テストケースについて、1個の整数を出力せよ、その数とはトーナメントの勝者の番号である。

入出力例

2
3
1

7
1

注記

$n=3$ の場合は、問題文中の図に示されています。

$n=1$ の場合、選手 $1$ と $2$ の試合1回だけが行われます。 $1 + 2 = 3$ は奇数であるため、番号の小さい方の選手が勝ちます。よって、選手 $1$ が勝者となります。

B. Prove Him Wrong / Докажи, что он не прав

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

最近、貴方の友人は整数の配列 $a$ についてある興味深い操作を発見しました。

2つのインデックス $i,\,j$ $(i \neq j)$
$a_i = a_j = |a_i - a_j|$ とする*1

この操作でしばらく遊んでいたら、彼は次のような結論に達しました。

$1 \leq a_i \leq 10^9$ である $n$ 個の整数のどのような配列 $a$ に対しても、操作後に $a$ の総和が減少するようなインデックスの組 $(i,\,j)$ が見つけることができる*2

この文は疑わしいと思っているため、与えられた $n$ について反例を見つけたいと思っています。反例を見つけ、彼が間違っていると証明できるでしょうか?

言い換えると、どのようなインデックスの組 $(i,\,j)$ に対しても操作後に総和が減少しない(増加、または変化なし)ような $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 10^9)$ からなる配列 $a$ を見つけてください。

入力

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

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

出力

各テストケースについて、反例である大きさ $n$ の配列 $a$ が存在しない場合、NOと出力せよ。

そうでない場合、YESと出力し、その後、配列 $a$ 自身 $(1 \leq a_i \leq 10^9)$ を続けて出力せよ。反例が複数存在する場合、そのうちにいずれかを出力せよ。

入出力例

YES
1 337
NO
YES
31 4 159

注記

1つ目のテストケースでは、有効なインデックスの組は $(1,\,2),$ $(2,\,1)$ のみです。

インデックス $(1,\,2)$ (または $(2,\,1)$ )に対して操作を行うと、 $a_1 = a_2 = |1-337| = 336$ 、つまり、配列 $[336,\,336]$ を得ます。どちらの場合も操作が増加するため、この配列 $a$ は反例となります。

C. Fault-tolerant Network / Отказоустойчивая сеть

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

コンピュータが2列に並んでいる教室があります。各列には $n$ 台のコンピュータが置かれていて、各コンピュータはそれぞれ等級で分類されている。1列目のコンピュータの等級は $a_1,\,a_2,\,\dots,\,a_n$ であり、2列目のコンピュータの等級は $b_1,\,b_2,\,\dots,\,b_n$ です。

初期状態では、各列の隣接するコンピュータの組(全ての $1 \leq i \lt n$ について組 $(i,\,i+1)$ )はワイヤーでつながれていて、2列が2つの独立したコンピュータネットワークを形成しています。

ここでの課題は、「1つ以上の異なる列のコンピュータの組を繋ぐことで1つの共通ネットワークに結合する」ことです。1列目の $i$ 台目のコンピュータと2列目の $j$ 台目のコンピュータを繋ぐには $|a_i - b_j|$ のコストがかかります。

1台のコンピュータを他の複数のコンピュータと接続することはできますが、少なくとも基本的な障害耐性(フォールトトレランス)を確保する必要があります、即ち、1台のコンピュータが故障しても、ネットワークがつながったままになるようにコンピュータを接続する必要があります。言い換えれば、1台のコンピュータが故障しても(それがどのコンピュータであっても)、ネットワークが2つ以上に分かれないようにするということです。

障害耐性ネットワークを構築するために必要は最小コストはいくつでしょう?

入力

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

各テストケースの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)$ が与えられる、これらは1列目のコンピュータの等級である。

各テストケースの3行目には、 $n$ 個の整数 $b_1,\,b_2,\,\dots,\,b_n$ $(1 \leq b_i \leq 10^9)$ が与えられる、これらは2列目のコンピュータの等級である。

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

出力

各テストケースについて単一の整数を出力せよ、その数とは障害耐性ネットワークを構築するために必要は最小コストである。

入出力例

2
3
1 10 1
20 4 25
4
1 1 1 1
1000000000 1000000000 1000000000 1000000000

31
1999999998

注記

1つ目のテストケースでは、4組のコンピュータを接続するのが最適です。

1列目のコンピュータ $1$ と2列目のコンピュータ $2$ : コスト $|1-4| = 3$
1列目のコンピュータ $3$ と2列目のコンピュータ $2$ : コスト $|1-4| = 3$
1列目のコンピュータ $2$ と2列目のコンピュータ $1$ : コスト $|10-20| = 10$
1列目のコンピュータ $2$ と2列目のコンピュータ $3$ : コスト $|10-25| = 15$

合計で、 $3+3+10+15=31$ です。

2つ目のテストケースでは、1列目の $1$ と2列目の $1$ 、1列目の $4$ と2列目の $4$ を接続するのが最適です。

D. Nearest Excluded Points / Ближайшие точки

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

平面上の相異なる $n$ 個の点が与えられます。 $i$ 番目の点の座標は $(x_i,\,y_i)$ です。

各点 $i$ について、与えられた $n$ 点に含まれない、(マンハッタン距離で)最も近い整数座標の点を求めて下さい。そのような点が複数存在する場合、どれを選んでもいいです。

2点 $(x_1,\,y_1),$ $(x_2,\,y_2)$ 間のマンハッタン距離は $|x_1-y_1| + |x_2-y_2|$ です。

入力

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

続く $n$ 行は点についての説明である。その $i$ 行目には2個の整数 $x_i,\,y_i$ $(1 \leq x_i,\,y_i \leq 2 \cdot 10^5)$ が与えられる、これは $i$ 番目の点の座標である。

入力内の全ての点が相異なることは保証されている。

出力

$n$ 行出力せよ。 $i$ 行目には与えられた $n$ 点に含まれない、 $i$ 番目の点から(マンハッタン距離で)最も近い整数座標の点を出力せよ。

出力する座標は範囲 $[-10^6;\,10^6]$ 内でなければならない。どのような最適解もこれらの制約を満たすことは証明することができる。

答えが複数存在する場合、どれを出力してもよい。

入出力例

E. Sum of Matchings / Сумма паросочетаний

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

グラフ $G$ の最大マッチングの大きさを $MM(G)$ とします。

2部グラフが与えられます。第1部の頂点には $1$ から $n$ までの、第2部の頂点委は $n+1$ から $2n$ までの番号が振られています。各頂点の次数は $2$ です。

$1 \leq l \leq rleq n$ かつ $n+1 \leq L \leq R \leq 2n$ を満たす整数4つ組 $(l,\,r,\,L,\,R)$ について、区間 $[l,\,r]$ または区間 $[L,\,R]$ に含まれる与えられたグラフの全ての頂点と、端点がこれらの区間どちらかに属する与えられたグラフの辺から成るグラフを $G’(l,\,r,\,L,\,R)$ と定義します。即ち、元のグラフから $G’(l,\,r,\,L,\,R)$ を得るには、 $i \notin [l,\,r]$ かつ $i \notin [L,\,R]$ を満たす全ての頂点 $i$ と、これらの頂点にくっついている全ての辺を削除しなければなりません。

$1 \leq l \leq r \leq n$ かつ $n+1 \leq L \leq R \leq 2n$ を満たす全ての整数の組 $(l,\,r,\,L,\,R)$ に対する $MM(G(l,\,r,\,L,\,R))$ *3 の和を計算してください。

入力

1行目には単一の整数 $n$ $(2 \leq n \leq 1500)$ が与えられる、これは各部の頂点数である。

$2n$ 行が続き、各行はグラフの辺を表す。 $i$ 行目には2個の整数 $x_i,\,y_i$ $(1 \leq x_i \leq n;$ $n+1 \leq y_i \leq 2n)$ が与えられる、これらは $i$ 本目の辺の端点である。

与えられるグラフには多重辺はなく、各頂点はちょうど2本の接続辺を持つ。

出力

各テストケースについて単一の整数を出力せよ、その数とは、 $1 \leq l \leq r \leq n$ かつ $n+1 \leq L \leq R \leq 2n$ を満たす全ての整数の組 $(l,\,r,\,L,\,R)$ に対する $MM(G(l,\,r,\,L,\,R))$ の和である。

入出力例

F. Tower Defense

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

Монокарп(Monocarp)*4はタワーディフェンスゲームをプレイしています。このゲームのレベルはOX軸で表すことができ、その軸上の $1$ から $n$ までの各格子点には塔が立っています。

$i$ 番目の地点の塔のマナ容量は $c_i$ でマナ再生率は $r_i$ です。初期状態 $0$ 秒時点では、各塔のマナは最大値です。ある秒数立った時点で $i$ 番目の塔のマナ量が $x$ である場合、その $1$ 秒後には $min(x+r_i,\,c_i)$ マナになります。

$1$ つのレベルにはモンスターが $q$ 体登場します。 $j$ 体目のモンスターは $t_j$ 秒後に体力 $h_j$ で地点 $1$ にスポーンします。各モンスターは、座標が増加する方向に毎秒 $1$ ポイントずつ移動します。

モンスターが塔を通過するとき、塔はモンスターに $min(H,\,M)$ ダメージを与えます、ここでの $H$ はモンスターの現在体力で、 $M$ はタワーの現在マナ量です。この値をモンスターの体力とタワーのマナ量から差し引きます。

残念なことに、塔を全て通過してしまうモンスターがいることもあります。Монокарпは、全ての塔を通過した後のモンスターの体力の総和を知りたいと思っています。

入力

1行目には単一の整数 $n$ $(1 \leq n \leq 2 \cdot 10^5)$ が与えられる、これは塔の個数である。

続く $n$ 行の $i$ 行目には、2個の整数 $c_i,\,r_i$ $(1 \leq r_i \leq c_i \leq 10^9)$ が与えられる、これらは $i$ 番目の塔のマナ容量とマナ再生率である。

次の行には単一の整数 $q$ $(1 \leq q \leq 2 \cdot 10^5)$ が与えられる、これはモンスターの数である。

続く $q$ 行の $j$ 行目には、2個の整数 $t_j,\,h_j$ $(0 \leq t_j \leq 2 \cdot 10^5;$ $1 \leq h_j \leq 10^{12})$ が与えられる、これらは $j$ 体目のモンスターのスポーン位置と体力である。

モンスターはスポーン時間の昇順に並んでいるため、全ての $1 \leq j \leq q -1$ について $t_j \lt t_{j+1}$ が成立する。

出力

単一の整数を出力せよ、その数とは全ての塔を通過した後のモンスターの体力の総和である。

入出力例

*1:正確には $a_i$ と $a_j$ に $|a_i - a_j|$ を代入

*2: $\forall a; \exists (i, j)$ s.t. … という形式

*3:恐らく $MM(G'(l,\,r,\,L,\,R) )$ の間違い

*4:モノカルプ、モノカープ: ロシア男性名Поликарп(Polycarp)をもじった名前であると思われる。英単語としては一巡植物を意味する