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

A. Prison Break / Побег (500点)
- 入力
- 出力
- 入出力例
- 注記
B. Restore Modulo / Восстановление модуля (1250点)
C. Basic Diplomacy / Базовая дипломатия (1500点)
D. Playlist / Плейлист (2000点)
- 入力
- 出力
- 入出力例
- 注記
E. Skyline Photo / Панорама города (2500点)
- 入力
- 出力
- 入出力例
- 注記
F. Useful Edges / Полезные рёбра (2750点)
- 入力
- 出力
- 入出力例
- 注記

A. Prison Break / Побег (500点)

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

Michaelはソーシャルディスタンスをとるルールに違反し*1、コロナウイルスの拡散の危険性をを生じさせたと告発さています。彼は今、刑務所に送られています。幸いなことに、Michaelは刑務所の内部構造を知っていて、それはとてもシンプルなものです。

刑務所は $ab$ 個のセルに分割される $a \times b$ の長方形として表すことができ、各セルが刑務所の独房を、セル間の辺は独房間の壁を、外側の辺は外壁を表しています。Michaelは判決を受ける前に刑務官の友人に頼んでいくつかの壁(独房間の壁および外壁)に(隠れた)穴をあけてもらうことができます。Michaelは、自分がどの独房に入ったとしても刑務所から出られるようにしたいです。しかし一方で、できるだけ壁を壊さないようにしたいと思っています。

どの独房からも外に出る経路ができるように壊さなければならない壁の最小枚数を求めてください。

入力

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

つづく $t$ 行のそれぞれには2つの整数 $a,\,b$ $(1 \leq a,\,b \leq 100)$ が与えられる、これらは対応するテストケースを表している。

出力

各テストケースについて各行に単一の整数を出力せよ、その数とは問題hwの答えである。

入出力例

2
2 2
1 3

4
3

注記

テストケース例で考えられる逃走計画を以下に示します。壊した壁は灰色で、壊されていない壁は黒で表されています。
f:id:Flkanjin:20210322155935p:plain
f:id:Flkanjin:20210322155942p:plain

B. Restore Modulo / Восстановление модуля (1250点)

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

大会で優勝したЛёша*2は整数配列をたくさん獲得し、それらが非常に高価であると確信しました。授賞式の後、Лёшаはそれらを売ることにしました。配列の市通夜には次のようなルールがあります: 配列を圧縮して生成器にできるときのみ配列を売ることができるというものです。

この生成器は4つの非負数 $n,\,m,\,c,\,s$ を受け取ります。 $n$ と $m$ は正でなければならず、 $s$ は非負で、 $c$ については $0 \leq c \lt m$ でなければなりません。長さ $n$ の配列 $a$ が以下のルールに従って生成されます。

$a_1 = s \bmod{m}$ , ここで $x \bmod{y}$ は $x$ を $y$ で割った余りを表す
$1 \lt i \leq n$ である全ての $i$ について $a_i = (a_{i-1} + c) \bmod{m}$

例えば、 $n = 5,$ $m = 7,$ $c = 4,$ $s = 10$ とすると、 $a = [3,\,0,\,4,\,1,\,5]$ となります。

このような配列の価格は、この生成器の $m$ の値になります。

Лёшаは疑問に思いました、それぞれの配列についてどれだけの金額を得ることができるのだろうかと。全ての配列について、この配列を生成する4数 $n,\,m,\,c,\,s$ が存在するかどうかわかるように手助けしてください。もし存在するならば $m$ を最大化してください。

入力

1行目には単一の整数 $t$ $(1 \leq t \leq 100)$ が与えられる、これは配列の個数である。

配列についての記述の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^5$ を超えないことは保証されている。

出力

全ての配列について以下のものを出力せよ。

この配列を生成するような4数が存在しない場合; $-1$
$m$ が任意の大きさになる場合: $0$
その他の場合 $m$ の最大値と適切な $c$ $(0 \leq c \lt m)$

入出力例

6
6
1 9 17 6 14 3
3
4 2 2
3
7 3 4
3
2 2 4
5
0 1000000000 0 1000000000 0
2
1 1

19 8
-1
-1
-1
2000000000 1000000000
0

C. Basic Diplomacy / Базовая дипломатия (1500点)

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

Алексей*3には $n$ 人の友人がいます。彼は今休暇中であり、この新しい流行りの協力型ゲームを遊ぶ時間が $m$ 日あります。Алексейはこの $m$ 日のそれぞれに1人ずつチームメイトを必要としています。

各日に何人かの友人はプレイ可能で、その他の友人はプレイができません。毎日Алексейはプレイ可能な友人のうち1人を選んで、プレイすることを申し出ます(勿論、彼等は常に承諾します)。しかし、彼らのうち誰かが $\displaystyle \left\lceil \frac{m}{2} \right\rceil$ 回より厳密に多く選ばれてしまうと、他の全ての友人は気分を害してしまいます。勿論、Алексейは誰かを怒らせてしまいたくありません。

誰も $\displaystyle \left\lceil \frac{m}{2} \right\rceil$ 回よりも厳密に多い回数選ばれないように、彼がチームメイトを選ぶのを手伝ってください。

入力

各テストは複数のテストケースから成る。1行目にはテストケース数 $t$ $(1 \leq t \leq 10\,000)$ が与えられる。テストケースについての記述が続く。

各テストケースの1行目にはそれぞれ友人の人数とプレイ日数を表す2つの整数 $n,\,m$ $(1 \leq n,\,m \leq 100\,000)$ が与えられる。

つづく $m$ 行の $i$ 行目には 1つの整数 $k_i$ $(1 \leq k_i \leq n)$ が与えられ、それに空白区切りの $k_i$ 個の異なる整数 $f_{i1},\,\dots,\,f_{ik_i}$ $(1 \leq f_{ij} \leq n)$ が続く、これらは $i$ 日に目にプレイ可能な友人のインデックスである。

全てのテストケースでの $n,\,m$ の和が(それぞれ) $100\,000$ を超えないことは保証されている。全てのテストケースの全ての日での $k_i$ の和が $20\,000$ を超えないことは保証されている。

出力

各テストケースについて答えを出力せよ。目標を達成する方法がない場合は"NO"と出力せよ。

そうでない場合、1行目に"YES"と出力し、2行目に空白で区切られた $m$ 個の整数 $c_1,\,\dots,\,c_m$ を出力せよ。各 $c_i$ は $i$ 日目に選ばれた友人を表していなければならない(したがって、 $f_{ij}$ の1つでなければならない)。

どの値も $\displaystyle \left\lceil \frac{m}{2} \right\rceil$ 回よりも多く出現してはいけない。複数の答えが存在する場合、そのいずれかを出力せよ。

入出力例

YES
1 2 1 1 2 3 
NO

D. Playlist / Плейлист (2000点)

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

Аркадий*4は初期状態で $n$ 曲からなるプレイリストを持っていて、各曲にはプレイリストに出てくる順に $1$ から $n$ までの番号がつけられている。プレイリストは循環しています、即ち、最後の曲を聴いた後、Аркадийは最初から聞き続けます。

各曲には正整数であるジャンル $a_i$ が振られています。Аркадийがジャンル $y$ の曲を聴き終え、その前に聴いていた曲のジャンルを $x$ とします。 $\gcd(x,\,y) = 1$ の場合、最後に聴いていた(ジャンル $y$ の)曲をプレイリストに削除します。その後、削除された曲をスキップし、前に聴いた曲について忘れて、通常通り曲を聴き続けます。言い換えれば、ある曲を削除した後、すぐに次の曲を削除することはできません。

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

例えば、初期状態の曲のジャンルが $[5,\,9,\,2,\,10,\,15]$ であったとすると、プレイリストは次のように変換されます: $[\mathbf{5},\,9,\,2,\,10,\,15]$ $\rightarrow$ $[\mathbf{5},\,\mathbf{9},\,2,\,10,\,15]$ $\rightarrow$ $[5,\,2,\,10,\,15]$ $(\gcd(5,\,9) = 1$ であるため $)$ $\rightarrow$ $[5,\,\mathbf{2},\,10,\,15]$ $\rightarrow$ $[5,\,\mathbf{2},\,\mathbf{10},\,15]$ $\rightarrow$ $[5,\,2,\,\mathbf{10},\,\mathbf{15}]$ $\rightarrow$ $[\mathbf{5},\,2,\,10,\,\mathbf{15}]$ $\rightarrow$ $[\mathbf{5},\,\mathbf{2},\,10,\,15]$ $\rightarrow$ $[5,\,10,\,15]$ $(\gcd(5,\,2) = 1$ であるため $)$ $\rightarrow$ $[5,\,\mathbf{10},\,15]$ $\rightarrow$ $[5,\,\mathbf{10},\,\mathbf{15}]$ $\rightarrow \dots$ 。太数字は、最後に再生された2つの曲を表しています。曲が削除された後は、Аркадийはその曲と前の曲を聴いたことを忘れてしまうことに注意してください。

初期状態のプレイリストが与えられるので、どの曲が最終的に削除されるか、そして、度の順に削除されるかを判別してください。

入力

各テストは複数のテストケースから成る。1行目にはテストケース数 $t$ $(1 \leq t \leq 10\,000)$ が与えられる。テストケースについての記述が続く。

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

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

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

出力

各テストケースについて、単一行に出力せよ。まず、単一の整数 $k$ を出力せよ、これは削除された曲数である。そのあと、 $k$ 個の異なる整数を出力せよ、これらは削除された順番で削除された曲を表している。

入出力例

5
5
5 9 2 10 15
6
1 2 4 2 4 2
2
1 2
1
1
1
2

注記

1つ目のテストケースについての説明は問題文中にあります。

2つ目のテストケースではプレイリストは次のように変換されます。 $[\mathbf{1},\,2,\,4,\,2,\,4,\,2]$ $\rightarrow$ $[\mathbf{1},\,\mathbf{2},\,4,\,2,\,4,\,2]$ $\rightarrow$ $[1,\,4,\,2,\,4,\,2]$ $(\gcd(1,\,2) = 1$ であるため $)$ $\rightarrow$ $[1,\,\mathbf{4},\,2,\,4,\,2]$ $\rightarrow$ $[1,\,\mathbf{4},\,\mathbf{2},\,4,\,2]$ $\rightarrow$ $[1,\,4,\,\mathbf{2},\,\mathbf{4},\,2]$ $\rightarrow$ $[1,\,4,\,2,\,\mathbf{4},\,\mathbf{2}]$ $\rightarrow$ $[\mathbf{1},\,4,\,2,\,4,\,\mathbf{2}]$ $\rightarrow$ $[4,\,2,\,4,\,2]$ $(\gcd(2,\,1) = 1$ であるため $)$ $\rightarrow$ $[\mathbf{4},\,2,\,4,\,2]$ $\rightarrow \dots$

3つ目のテストケースではプレイリストは次のように変換されます。 $[\mathbf{1},\,2]$ $\rightarrow$ $[\mathbf{1},\,\mathbf{2}]$ $\rightarrow$ $[1]$ $(\gcd(1,\,2) = 1$ であるため $)$ $\rightarrow$ $[\mathbf{1}]$ $\rightarrow$ $[\mathbf{1}]$ (Аркадийは同じ曲を2回続けて聴いた) $\rightarrow$ $[\,]$ $(\gcd(1,\,1) = 1$ であるため $)$

4つ目のテストケースでは2曲目を削除した後の3つ目のテストケースと同じです。

5つ目のテストケースでは同じ曲を何度も何度も聴いていますが、 $\gcd(2,\,2) \neq 1$ であるため、削除されません。

E. Skyline Photo / Панорама города (2500点)

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

AliceはNew York市を訪れています。旅行を楽しむため、Aliceは街のスカイライン *6の写真を撮って、その写真の集合をプレゼントとしてBobに上げたいと思っています。しかし、彼女は最大の美しさを持つ写真の集合を求めたいので、貴方の助けを必要としています。

街には $n$ 個のビルがあり、 $i$ 番目のビルの高さは正の値 $h_i$ です。街にある $n$ 個の全てのビルの高さは異なります。さらに、それぞれのビルの美しさは $b_i$ です。街には醜い建物もあるので、美しさは正にも負にもなりえることに注意してください。

写真の集合はスカイライン上のビルを撮影した1枚以上の写真から成ります。各写真は連続インデックス区間を形成する1つ以上のスカイライン上のビルが含まれます。各ビルはちょうど1枚の写真に写っていなければなりません。つまり、どの写真にも写っていないビルがあったり、複数の写真に写っているビルが存在する場合、その写真の集合は有効ではないという訳です。

写真の美しさは、写っている最も短いビルの美しさ $b_i$ に等しいです。写真の集合の美しさの合計は、その写真に含まれる全ての写真の美しさの合計です。有効な写真の集合が持つ最大の美しさを求めるAliceの手伝いをしてください。

入力

1行目には単一の整数 $n$ $(1 \leq n \leq 3 \cdot 10^5)$ が与えられる、これはスカイライン上のビルの数である。

2行目には $n$ 個の異なる整数 $h_1,\,h_2,\,\dots,\,h_n$ $(1 \leq h_i \leq n)$ が与えられる。 $i$ 番目の数は建物 $i$ の高さを表す。

3行目には $n$ 個の異なる整数 $b_1,\,b_2,\,\dots,\,b_n$ $(-10^9 \leq b_i \leq 10^9)$ が与えられる。 $i$ 番目の数は建物 $i$ の美しさを表す。

出力

有効なスカイラインの写真の集合についてAliceが達成できる最大の美しさを表す1つの数値を出力せよ。

入出力例

5
1 2 3 5 4
1 5 3 2 4

5
1 4 3 2 5
-3 4 -10 2 7

2
2 1
-2 -3

-3

10
4 7 3 2 5 1 9 10 6 8
-4 40 -46 -8 -16 4 -10 41 12 3

注記

1つ目の入出力例では、Aliceは5枚の写真を撮り、それぞれに1つのビルを写すことで最大の美しさを得ることができます。

2つ目の入出力例では、Aliceは4枚の写真を撮ることで、最大の美しさ $10$ を達成することができます。1つのビルを写したビル $1,\,2,\,5$ の3枚の写真のそれぞれの美しさ $-3,\,4,\,7$ で、もう1枚の写真はビル $3,\,と4$ を写し、美しさ $2$ です。

3つ目の入出力例では、Aliceは街全体の写真を1枚だけ撮ります。

4つ目の入出力例では、Aliceは最大の美しさを得るために、1つのビルを写したビル $1,\,2,\,8,\,9,\,10$ の写真と、ビル $3,\,4,\,5,\,6,\,7$ を写した1枚の写真を撮ります。

F. Useful Edges / Полезные рёбра (2750点)

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

$n$ 頂点の重み附き無向グラフと $q$ 個の三つ組 $(u,\,v,\,l)$ が与えられます、ここで各三つ組の $u$ と $v$ は頂点で $l$ は正整数です。以下の条件を満たすような少なくとも1つの三つ組 $(u,\,v,\,l)$ と経路(必ずしも単純ではない)が存在する場合、辺 $e$ は有用といいます。

$u$ と $v$ がこの経路の端点である
$e$ はこの経路の辺の1つである
この経路の全ての辺の重さの合計が $l$ を超えない

このグラフ上の有用な辺の数を出力してください。

入力

1行目には2つの整数 $n,\,m$ $\biggl(2 \leq n \leq 600,$ $\displaystyle 0 \leq m \leq \frac{n(n-1)}{2} \biggr)$ が与えられる。

つづく $m$ 行の各行には3つの整数 $u,\,v,\,w$ $(1 \leq u,\,v \leq n,$ $u \neq v,$ $1 \leq w \leq 10^9)$ が与えられる、これらは $u$ と $v$ を結ぶ重さ $w$ の辺を表す。

次の行には唯一の整数 $q$ $\left(\displaystyle 1 \leq q \leq \frac{n(n-1)}{2} \right)$ が与えられる、これは三つ組の個数である。

つづく $q$ 行の各行には三つ組 $(u,\,v,\,l)$ を表す3つの整数 $u,\,v,\,l$ $(1 \leq u,\,v \leq n,$ $u \neq v,$ $1 \leq l \leq 10^9)$ が与えられる。

次のことは保証されている。

グラフにはループや多重辺は含まれない
三つ組内の全ての組 $(u,\,v)$ は異なる

出力

グラフ内の有用な辺の数を表す単一の整数を出力せよ。

入出力例

注記

1つめの入出力例では重み $5$ のものを除いてすべての辺が有用です。

2つ目の入出力例では、 $1$ と $2$ の間の辺は、経路 $1-2$ に属し、 $10 \leq 11$ であるため、唯一有用です。一方で、 $3$ と $4$ の間の辺は、有用ではありません。

3つ目の入出力例では、長さがちょうど $5$ の経路 $1-2-3-2$ が存在するので、両方の辺が有効です。経路が1つの頂点を2回以上通過することがあることに注意してください。

*1:ロシア語版ではマスクをせず

*2:Леша 露[ˈlʲɵʂə] (Ljosha): Алексе́й [ɐlʲɪkˈsʲej] の愛称、Alexanderなどと同語源英語版ではAlex

*3:露[ɐlʲɪkˈsʲej] Aleksej, Aleksey, Alexey

*4:露[ɐrˈkadʲɪ] Arkadij, Arkady

*5:原文では英語、ロシア語のWikipediaへのリンク

*6:空を背景とした高層建築物や山岳が描く輪郭線の事