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

A. Three swimmers / Три пловца (500点)
- 入力
- 出力
- 入出力例
- 注記
B. Card Deck / Колода карт (1000点)
- 入力
- 出力
- 入出力例
- 注記
C. Maximum width / Максимальная ширина (1500点)
- 入力
- 出力
- 入出力例
- 注記
D. Genius's Gambit / Ход гения (2250点)
- 入力
- 出力
- 入出力例
- 注記
E. Almost Fault-Tolerant Database / Почти отказоустойчивая база данных (3000点)
- 入力
- 出力
- 入出力例
- 注記

A. Three swimmers / Три пловца (500点)

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

3人の水泳選手がプールでマラソンをしていました*1。彼らは正午にプールの左側から泳ぎ始めました。

1人目の水泳選手がプールを往復するのにちょうど $a$ 分かかり、2人目の水泳選手は $b$ 分、3人目の水泳選手は $c$ 分かかります。したがって、1人目はスタートしてから $0,$ $a,$ $2a,$ $3a,$ $\dots$ 分後に、2人目は $0,$ $b,$ $2b,$ $3b,$ $\dots$ 分後、3人目は $0,$ $c,$ $2c,$ $3c,$ $\dots$ 分後にプールの左側にいることになります。

彼らが泳ぎ始めてからちょうど $p$ 分後にプールの左側にあなたが来ました。水泳選手のうち1人がプールの左側に着くまでに何分待つ必要があるか求めてください。

入力

1行目には単一の整数 $t$ $(1 \leq t \leq 1000)$ が与えられる、 $t$ はテストケースの個数である。つづく $t$ 行にはテストケースについての記述が、1行につき1つずつ与えられる。

各行には4つの整数 $p,\,a,\,b,\,c$ $(1 \leq p,\,a,\,b,\,c \leq {10}^{18})$ が与えられる、これらの整数はそれぞれ、3人が泳ぎ始めてからあなたが来るまでの時間を分単位にしたものと3人の水泳選手がプールを泳いで戻ってくるのにかかる時間を分単位にしたものである。

出力

各テストケースについて、1つの整数を出力せよ、その整数とは水泳選手のうち1人がプールの左側に着くまでに待つ必要がある時間(分単位)である。

入出力例

注記

1つ目のテストケースでは、1人目の水泳選手は開始時刻から $0,$ $5,$ $10,$ $15,$ $\dots$ 分後に、2人目の水泳選手は $0,$ $4,$ $8,$ $12,$ $\dots$ 分後に、3人目の水泳選手は $0,$ $8,$ $16,$ $24,$ $\dots$ 分後にプールの左側にいます。あなたは開始時刻から $9$ 分後にプールに到着し、その1分後に1人目の水泳選手と出会います。

2つ目のテストケースでは、1人目の水泳選手は開始時刻から $0,$ $6,$ $12,$ $18,$ $\dots$ 分後に、2人目の水泳選手は $0,$ $10,$ $20,$ $30,$ $\dots$ 分後に、3人目の水泳選手は $0,$ $9,$ $18,$ $27,$ $\dots$ 分後にプールの左側にいます。あなたは開始時刻から $2$ 分後にプールに到着し、その $4$ 分後に1人目の水泳選手と出会います。

3つ目のテストケースでは、あなたは開始時刻から $10$ 分後にプールに到着しました。そのちょうど同じときに、3人の水泳選手がプールの左側にいます。何という幸運でしょう。

4つ目のテストケースでは、全ての水泳選手は開始時刻から $0,$ $9,$ $18,$ $27,$ $\dots$ 分後にプールの左側にいます。あなたは開始時刻から $10$ 分後にプールに到着し、その $8$ 分後に3人全員の水泳選手と出会います。

B. Card Deck / Колода карт (1000点)

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

$n$ 枚のカードのデッキがあり、それを新しいデッキへと並び変えようとしています。

各カードには $1$ と $n$ の間の $p_i$ の値が振られています。全ての $p_i$ はどの2つをとっても互いに異なります。デッキのカードには下から上へと番号が振られています、つまり、 $p_1$ は一番下のカードで、 $p_n$ は一番上のカードです。

各ステップにおいてある整数 $k \gt 0$ を選び、元のデッキの上から $k$ 枚を取り出し、そのままの順番で新しいデッキの上に置きます。この操作を元のデッキが空になるまで行います。(より理解するためには注記の部分を参照して下さい。)

デッキのオーダーを $\displaystyle\sum_{i = 1}^{n}\,n^{n-i} \cdot p_i$ と定義しましょう。

与えられる元のデッキについて、上記の操作を用いて得ることができる最大オーダーのデッキを出力してください。

入力

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

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

各テストケースの2行目には $n$ 個の整数 $p_1,\,p_2,\,\dots,\,p_n$ $(1 \leq p_i \leq n;$ $i \neq j$ のとき $p_i \neq p_j)$ が与えられる、これらの値はデッキ内の下から上のカードの値である。

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

出力

各テストケースについて、最大可能オーダーのデッキを出力せよ。デッキのカードの値を下から上の順に出力せよ。

複数の答えが存在する場合、そのうち1つを出力せよ。

入出力例

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

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

注記

1つ目のテストケースでの最適戦略の1つは次のようなものです。

$p$ の上からカードを $1$ 枚 $p'$ へ移す: $p$ は $[1,\,2,\,3]$ となり、 $p'$ は $[4]$ となる
$p$ の上からカードを $1$ 枚移す: $p$ は $[1,\,2]$ となり、 $p'$ は $[4,\,3]$ となる
$p$ の上からカードを $1$ 枚移す: $p$ は $[1]$ となり、 $p'$ は $[4,\,3,\,2]$ となる
$p$ の上からカードを $1$ 枚移す: $p$ は空になり、 $p'$ は $[4,\,3,\,2,\,1]$ となる

結果として、 $p'$ は $4^3 \cdot 4 + 4^2 \cdot 3 + 4^1 \cdot 2 + 4^0 \cdot 1$ $= 256 + 48 + 8 + 1 = 313$ のオーダーを持つことになります。

2つ目のテストケースでの最適戦略の1つは次のようなものです。

$p$ の上からカードを $4$ 枚 $p'$ へ移す: $p$ は $[1]$ となり、 $p'$ は $[5,\,2,\,4,\,3]$ となる
$p$ の上からカードを $1$ 枚 $p'$ へ移す: $p$ は空になり、 $p'$ は $[5,\,2,\,4,\,3,\,1]$ となる

結果として、 $p'$ は $5^4 \cdot 5 + 5^3 \cdot 2 + 5^2 \cdot 4 + 5^1 \cdot 3 + 5^0 \cdot 1$ $= 3125 + 250 +100 + 15 + 1 = 3491$ のオーダーを持つことになります。

3つ目のテストケースでの最適戦略の1つは次のようなものです。

$p$ の上からカードを $2$ 枚 $p'$ へ移す: $p$ は $[4,\,2,\,5,\,3]$ となり、 $p'$ は $[6,\,1]$ となる
$p$ の上からカードを $2$ 枚 $p'$ へ移す: $p$ は $[4,\,2]$ となり、 $p'$ は $[6,\,1,\,5,\,3]$ となる
$p$ の上からカードを $2$ 枚 $p'$ へ移す: $p$ は空になり、 $p'$ は $[6,\,1,\,5,\,3,\,4,\,2]$ となる

結果として、 $p'$ は $6^5 \cdot 6 + 6^4 \cdot 1 + 6^3 \cdot 5 + 6^2 \cdot 3 + 6^1 \cdot 4 + 6^0 \cdot 2$ $= 46656 + 1296 + 1080 +108 + 24 + 2 = 49166$ のオーダーを持つことになります。

C. Maximum width / Максимальная ширина (1500点)

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

退屈*2であるのであまり好きではないが、頭の良さについて尊敬できるクラスメートがいます。彼は2つの文字列である長さ $n$ の $s$ と長さ $m$ の $t$ を持っています。

全ての $1$ から $m$ の $i$ について $s_{p_i} = t_i$ となるとき、 $1 \leq p_1 \lt p_2 \lt \dots \lt p_m \leq n$ である数列 $p_1,\,p_2,\,\dots,\,p_m$ は美しいといいます。数列の幅は $\displaystyle\max_{1 \leq i \lt m}\,(p_{i+1} - p_i)$ と定義されます。

クラスメートが、最大の幅をもつ美しい配列を特定するのを手伝ってください。与えられる文字列 $s$ と $t$ には少なくとも1つの美しい数列が存在することをクラスメートは約束しました。

入力

1行目には2つの整数 $n,\,m$ $(2 \leq m \leq n \leq 2 \cdot 10^5)$ が与えられる、これらは文字列 $s$ と $t$ の長さである。

つづく1行にはラテン文字の小文字からなる長さ $n$ の文字列 $s$ が与えられる。

最後の行にはラテン文字の小文字からなる長さ $m$ の文字列 $t$ が与えられる。

与えられる文字列について少なくとも1つ、美しい数列が存在することは保証されている。

出力

1つの整数を出力せよ、その整数とは美しい数列の最大幅である。

入出力例

5 3
abbbc
abc

5 2
aaaaa
aa

5 5
abcdf
abcdf

2 2
ab
ab

注記

1番目の例では幅 $3$ の美しい数列は2つ存在します: $\{1,\,2,\,5\},$ $\{1,\,4,\,5\}$

2番目の例では最大幅の美しい数列は $\{1,\,5\}$ です。

3番目の例では美しい数列は1つだけ存在します: $\{1,\,2,\,3,\,4,\,5\}$

4番目の例では美しい数列は1つだけ存在します: $\{1,\,2\}$

D. Genius's Gambit / Ход гения (2250点)

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

3つの整数 $a,\,b,\,k$ が与えられています。

次の条件を満たす2つの二進数整数 $x,\,y$ $(x \geq y)$ を求めてください。

$x$ も $y$ も $a$ 個の0と $b$ 個の1から成る
$x - y$ (これも二進数表記される)がちょうど $k$ 個の1を含む

$x$ も $y$ も頭に0を付けることは禁止されています。

入力

唯一の行に3つの整数 $a,\,b,\,k$ $(0 \leq a;$ $1 \leq b;$ $0 \leq k \leq a + b \leq 2 \cdot 10^5)$ が与えられる、これらは0の数、1の数と計算結果の1の数である。

出力

2つの最適な整数が存在するならば、"Yes"と出力し、その次に $x$ と $y$ を2進数で出力せよ。

そうでなければ、"No"と出力せよ。

複数の答えが存在する場合、そのうち1つを出力せよ。

入出力例

4 2 3

Yes
101000
100001

3 2 1

Yes
10100
10010

3 2 5

No

注記

1つ目の例では $x = 101000_2 = 2^5 + 2^3 = 40_{10},$ $y = 100001_2 = 2^5 + 2^0 = 33_{10},$ $40_{10} - 33_{10} = 7_{10} = 2^2 + 2^1 + 2^0 = 111_{2}$ となります。したがって $x - y$ は2進数で $3$ つの1を持ちます。

2つ目の例では $x = 10100_2 = 2^4 + 2^2 = 20_{10},$ $y = 10010_2 = 2^4 + 2^1 = 18,$ $x - y =20 - 18 = 2_{10} = 10_{2}$ となります。これは1がちょうど1つあります。

3つ目の例では答えを見つけることができないことを示すことができます。

E. Almost Fault-Tolerant Database / Почти отказоустойчивая база данных (3000点)

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

データベースに長さ $m$ の整数列を格納しています。内部の整合性を維持し、データを保護するため、このデータベースにはこの配列の $n$ 個のコピーが保存されています。

不幸なことに、最近の事件でデータベースの全てのコピーに保存されている情報が変更された可能性があります。

今回の事件ではどのコピーでも2つまでの要素が変わったと考えられています。データベースの現在の状態に基づいて元の配列を復元しなければなりません。

復元方法が複数ある場合は、そのいずれかを報告してください。全てのコピーから2ヶ所以内しか違わない配列が存在しない場合、そのことを報告してください。

入力

1行目には2つの整数 $n,\,m$ $(2 \leq n;$ $1 \leq m;$ $n \cdot m \leq 250\,000)$ が与えられる、これらはコピーの数と配列のサイズである。

つづく $n$ 行のそれぞれにはデータベースに保存されているコピーの1つが記述されている、これは $m$ 個の整数 $s_{i,1},\,s_{i,2},\,\dots,\,s_{i,m}$ $(1 \leq s_{i,j} \leq 10^9)$ からなる。

出力

与えられる全てのコピーと食い違わない配列があるとき、"Yes"と出力し、そののちに配列そのものを出力せよ。この配列は長さが $m$ で、 $1$ から $10^9$ までの整数しか含んではいけない。

そうでなければ"No"と出力せよ。

複数の可能な配列が存在する場合、そのうち1つを出力せよ。

入出力例

3 4
1 10 10 100
1 1 1 100
10 100 1 100

Yes
1 10 1 100

10 7
1 1 1 1 1 1 1
1 1 1 1 1 1 2
1 1 1 1 1 2 2
1 1 1 1 2 2 1
1 1 1 2 2 1 1
1 1 2 2 1 1 1
1 2 2 1 1 1 1
2 2 1 1 1 1 1
2 1 1 1 1 1 1
1 1 1 1 1 1 1

Yes
1 1 1 1 1 1 1

2 5
2 2 1 1 1
1 1 2 2 2

No

注記

1つ目の例では、配列 $[1,\,10,\,1,\,100]$ は1つ目のコピーと2つ目のコピーとは1か所のみが異なり、3つ目のコピーとは2ヶ所が異なります。

2つ目の例では、配列 $[1,\,1,\,1,\,1,\,1,\,1,\,1]$ は1つ目のコピーと同じであり、全ての他のコピーとは高々2ヶ所が異なります。

第3の例では、すべてのデータベースのコピーから高々2ヶ所が異なるような配列は存在しません。

*1:英語版ではorganize a partyとなっていましたが意味がうまく取れなかったのでロシア語の問題文の方を訳したマラソンの方を選びました

*2:ロシア語の問題文ではオタク