Codeforces Round #710 (Div. 3) 問題文和訳

A. Strange Table / Странная таблица
B. Partial Replacement / Частичная замена
C. Double-ended Strings / Двусторонние строки
D. Epic Transformation / Эпическая трансформация
E. Restoring the Permutation / Восстановление перестановки
F. Triangular Paths / Треугольные пути
G. Maximize the Remaining String / Максимизируй оставшуюся строку

A. Strange Table / Странная таблица

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

Поликарп*1は $n$ 行 $m$ 列の長方形の表を見つけました。表の各セルには数字が書かれていて、その数は次のような「列による」アルゴリズムによって得られることに気が付きました。

セルは1から順に数が振られる
セルは列ごとに左の列から右の列へと数が振られ、各列内では上から下へ向かって数が振られる
各セルの番号は前のセルよりも1大きい整数である

例えば、 $n =3,$ $m = 5$ の場合、表は次のように数が振られます。
$$
\begin{matrix}
1 & 4 & 7 & 10 & 13 \\
2 & 5 & 8 & 11 & 14 \\
3 & 6 & 9 & 12 & 15 \\
\end{matrix}
$$
しかし、Поликарпはこのような番号付けは不便であると考えています。彼は「行による」番号付けを好みます。

セルは1から順に数が振られる
セルは行ごとに上の行から下の列へと数が振られ、各列内では左から右へ向かって数が振られる
各セルの番号は前のセルよりも1大きい整数である

例えば、 $n =3,$ $m = 5$ の場合、Поликарпは次のような表の番号付けを好みます。
$$
\begin{matrix}
1 & 2 & 3 & 4 & 5 \\
6 & 7 & 8 & 9 & 10 \\
11 & 12 & 13 & 14 & 15 \\
\end{matrix}
$$
Поликарпにはあまり時間がないため、「列による」番号付けで $x$ であるようなセルの「行による」番号付けでの番号が何になるかを調べるよう頼まれています。

入力

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

各テストケースは単一行で構成され、3つの整数 $n,\,m,\,x$ $(1 \leq n,\,m \leq 10^6,$ $1 \leq x \leq n \cdot m)$ が与えられる、ここで、 $n,\,m$ は行数と列数であり、 $x$ はセルの番号である。

数値が $32$ -bit整数型に収まらないテストケースが存在するため、プログラミング言語の $64$ -bit以上の整数型を用いる必要があることに注意せよ。

出力

各テストケースについて、「列による」番号付けでのセルの番号を出力せよ。

入出力例

5
1 1 1
2 2 3
3 5 11
100 100 7312
1000000 1000000 1000000000000

1
2
9
1174
1000000000000

B. Partial Replacement / Частичная замена

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

数 $k$ と、文字'.'と'*'から成る $n$ 文字の文字列 $s$ が与えられます。以下の条件を満たすようにいくつかの'*'文字を'x'文字に置換したいと思っています。

元の文字列の最初の'*'文字は'x'に置換されてなければならない
元の文字列の最後の'*'文字は'x'に置換されてなければならない
置換された隣り合う2つの文字'x'間の距離は $k$ を超えてはならない(より形式的には、位置 $i$ と $j$ $(i \lt j)$ で置換を行い、位置 $[i+1,\,j-1]$ に記号'x'が存在しない場合、 $j-i$ は $k$ 以下でなければならない)

例えば、 $n = 7,$ $s=$ .**.*** $,$ $k=3$ の場合、以下の文字列は上記の条件を満たしています。

.xx.*xx
.x*.x*x
.xx.xxx

しかし、例えば、以下の文字列は条件を満たしません。

.**.*xx (最初の'*'文字は'x'に置換されてなければならない)
.x*.xx* (最後の'*'文字は'x'に置換されてなければならない)
.x*.*xx (位置 $2$ と $6$ 間の距離は $k = 3$ よりも大きい)

$n,\,k,\,s$ が与えられたとき、上記を条件を満たすために'x'に置換しなければならない'*'文字の最小数を求めてください。

入力

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

各テストケースの1行目には2つの整数 $n,\,k$ $(1 \leq k \leq n \leq 50)$ が与えられる。

各テストケースの2行目には文字'.'と'*'から成る $n$ 文字の文字列 $s$ が与えられる。

文字列 $s$ には少なくとも1つの'*'が存在することは保証される。

任意の隣り合う2つの'*'文字の間の距離が $k$ を超えないことは保証される。

出力

各テストケースについて上記を条件を満たすために'x'に置換しなければならない'*'文字の最小数を出力せよ。

入出力例

5
7 3
.**.***
5 1
..*..
5 2
*.*.*
3 2
*.*
1 1
*

C. Double-ended Strings / Двусторонние строки

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

小文字のラテン文字から成る文字列 $a,\,b$ が与えられます。以下の操作を任意の回数、任意の順番で行うことができます。

$|a| \gt 0$ の(文字列 $a$ の長さが0より大きい)とき、文字列 $a$ の最初の文字を削除する、つまり、 $a$ を $a_2 a_3 \dots a_n$ に置換する
$|a| \gt 0$ のとき、文字列 $a$ の最後の文字を削除する、つまり、 $a$ を $a_1 a_2 \dots a_{n-1}$ に置換する
$|b| \gt 0$ の(文字列 $b$ の長さが0より大きい)とき、文字列 $b$ の最初の文字を削除する、つまり、 $b$ を $b_2 b_3 \dots b_n$ に置換する
$|b| \gt 0$ のとき、文字列 $b$ の最後の文字を削除する、つまり、 $b$ を $b_1 b_2 \dots b_{n-1}$ に置換する

それぞれの操作の後、文字列 $a$ または $b$ が空になることがあることに注意して下さい。

例えば、 $a=$ "hello" $,$ $b=$ "icpc"の場合、次のような一連の操作を行うことができます。

文字列 $a$ の最初の文字を削除 $\Rightarrow$ $a=$ "ello" $,$ $b=$ "icpc"
文字列 $b$ の最初の文字を削除 $\Rightarrow$ $a=$ "ello" $,$ $b=$ "cpc"
文字列 $b$ の最初の文字を削除 $\Rightarrow$ $a=$ "ello" $,$ $b=$ "pc"
文字列 $a$ の最後の文字を削除 $\Rightarrow$ $a=$ "ell" $,$ $b=$ "pc"
文字列 $b$ の最後の文字を削除 $\Rightarrow$ $a=$ "ell" $,$ $b=$ "p"

与えられた文字列 $a,\,b$ について、文字列 $a,\,b$ を等しくするための最小の操作回数を求めてください。空文字列同士も等しいものとすることに注意して下さい。

入力

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

各テストケースの1行目には小文字のラテン文字から成る文字列 $a$ $(1 \leq |a| \leq 20)$ が与えられる。

各テストケースの2行目には小文字のラテン文字から成る文字列 $b$ $(1 \leq |b| \leq 20)$ が与えられる。

出力

各テストケースについて、文字列 $a,\,b$ を等しくするための最小の操作回数を出力せよ。

入出力例

5
a
a
abcd
bc
hello
codeforces
hello
helo
dhjakjsnasjhfksafasd
adjsnasjhfksvdafdser

D. Epic Transformation / Эпическая трансформация

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

整数から成る長さ $n$ の配列 $a$ が与えられます。配列 $a$ に対し、数ステップからなる次の操作を0回以上適用することができます。

配列内の異なる2数 $a_i,\,a_j$ を選ぶ
配列から $i$ 番目と $j$ 番目の要素を削除する

例えば、 $n = 6,$ $a = [1,\,6,\,1,\,1,\,4,\,4]$ の場合、次のような一連の操作を行うことができます。

$i = 1,$ $j = 5$ を選び、配列 $a$ は $[6,\,1,\,1,\,4]$ になる
$i = 1,$ $j = 2$ を選び、配列 $a$ は $[1,\,4]$ になる

配列に一連の操作を施した後の配列のサイズの最小値はどうなるでしょうか?

入力

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

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

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

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

出力

各テストケースについて、配列に一連の操作を施した後の、サイズの可能な最小値を出力せよ。

入出力例

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

E. Restoring the Permutation / Восстановление перестановки

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

順列とは $1$ から $n$ までの $n$ 個の整数がちょうど1回ずつ現れるような数列です。例えば、 $[1],$ $[3,\,5,\,2,\,1,\,4],$ $[1,\,3,\,2]$ は順列で、 $[2,\,3,\,2],$ $[4,\,3,\,1],$ $[0]$ は順列ではありません。

Поликарпは $1$ から $n$ までの数の順列 $p$ を貰いました。しかし、Поликарпが家に帰ったとき、ポケットの中の順列 $p$ が以下のルールに従っ配列 $q$ に変わっていることに気が付きました。

$q_i = \max(p_1,\,p_2,\,\dots,\,p_i)$

ここで、Поликарпは与えられた順列としてあり得る辞書順最小の配列と辞書順最大の配列がどんなものか疑問に思いました。

長さ $n$ の配列 $a$ が長さ $n$ の配列 $b$ よりも辞書順で小さいとは配列 $a$ と $b$ の最初の $i - 1$ 個の要素が一致し、配列 $a$ の $i$ 番目の要素が配列 $b$ の $i$ 番目の要素より小さい場合です。例えば、配列 $[1,\,3,\,2,\,3]$ は配列 $[1,\,3,\,4,\,2]$ よりも辞書順で小さいです。

例えば、 $n = 7,$ $p = [3,\,2,\,4,\,1,\,7,\,5,\,6]$ の場合、 $q = [3,\,3,\,4,\,4,\,7,\,7,\,7]$ となり、この場合、元の $p$ としては次のような順列が考えられます。

$[3,\,1,\,4,\,2,\,7,\,5,\,6]$ (辞書順最小順列)
$[3,\,1,\,4,\,2,\,7,\,6,\,5]$
$[3,\,2,\,4,\,1,\,7,\,5,\,6]$
$[3,\,2,\,4,\,1,\,7,\,6,\,5]$ (辞書順最大順列)

与えられた配列 $q$ についてПоликарпに最初に渡された可能性のある辞書順最小の順列と辞書的最大の順列を求めて下さい。

入力

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

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

各テストケースの2行目には $n$ 個の整数 $q_1,\,q_2,\,\dots,\,q_n$ $(1 \leq q_i \leq n)$ が与えられる。

配列 $q$ がある順列 $p$ に問題文中のルールを適用して得られたものであることは保証されている。

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

出力

各テストケースについて、2行を出力せよ。

1行目に $n$ 個の整数を出力せよ、これらはПоликарпに最初に渡された可能性のある辞書順最小の順列である
2行目に $n$ 個の整数を出力せよ、これらはПоликарпに最初に渡された可能性のある辞書順最大の順列である

入出力例

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

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

F. Triangular Paths / Треугольные пути

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

複数の層で構成された無限の三角形を考えてみましょう。三角形の上から(上から下へ)、1から順に番号を振っていきます。三角形の $k$ 層目は左から右に番号が振られた $k$ 点が含まれます。無限三角形の各点は数の組 $(r,\,c)$ $(1 \leq c \leq r)$ で記述されます、ここで、 $r$ は層の番号で、 $c$ は層内の点の番号です。各点 $(r,\,c)$ からは点 $(r+1,\,c)$ へと $(r+1,\,c+1)$ への2本の有向辺がありますが、そのうち1本のみが活性化しています。 $r + c$ が偶数の場合は $(r+1,\,c)$ への辺が活性化され、そうでない場合は $(r+1,\,c+1)$ への辺が活性化されます。よりよい理解のためには図を見てください。

f:id:Flkanjin:20210326134127p:plain — 活性辺は黒で色づけられています。非活性辺は灰色で色づけられています。

活性辺のみから成る経路が存在する場合、点 $(r_1,\,c_1)$ から点 $(r_2,\,c_2)$ へ行くことができます。例えば、上図で、 $(1,\,1)$ から $(3,\,2)$ への経路は存在しますが、 $(2,\,1)$ から $(1,\,1)$ への経路は存在しません。

最初は点 $(1,\,1)$ にいます。各ターン次のことが行えます。

点 $(r,\,c)$ 空の辺を取り換える。点 $(r+1,\,c)$ への辺が活性化されていれば、それの代わりに点 $(r+1,\,c+1)$ への辺が活性化され、そうではなく点 $(r+1,\,c+1)$ への辺が活性化されていれば、それの代わりに点 $(r+1,\,c)$ への辺が活性化される。この行動は経路のコストを $1$ 増加させる
活性辺を辿って現在の点から次の点へ移動する。この行動は経路のコストを増加させない

無限三角形上の $n$ 点 $(r_1,\,c_1),$ $(r_2,\,c_2),$ $\dots,$ $(r_n,\,c_n)$ が与えられます。 $(1,\,1)$ から任意の順序で $n$ 個の点を全て通過する最小コストの経路を求めてください。

入力

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

各テストケースは単一の整数 $n$ $(1 \leq n \leq 2 \cdot 10^5)$ が与えられる行で始まる、これは訪れる点の個数である。

各テストケースの2行目には $n$ 個の整数 $r_1,\,r_2,\,\dots,\,r_n$ $(1 \leq r_i \leq 10^9)$ が与えられる、ここで $r_i$ は $i$ 番目の点が位置する層の番号である。

各テストケースの2行目には $n$ 個の整数 $c_1,\,c_2,\,\dots,\,c_n$ $(1 \leq c_i \leq r_i)$ が与えられる、ここで $c_i$ は $r_i$ 層目内の $i$ 番目の点の番号である。

全ての $n$ 点が異なることは保証されている。

全ての $n$ 点を横断する方法が常に少なくとも1通り存在することは保証されている。

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

出力

各テストケースについて、対応するテストケースの全ての点を通過する経路の最小コストを出力せよ。

入出力例

4
3
1 4 2
1 3 1
2
2 4
2 3
2
1 1000000000
1 1000000000
4
3 10 5 8
2 5 2 4

G. Maximize the Remaining String / Максимизируй оставшуюся строку

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

小文字のラテン文字で構成された文字列 $s$ が与えられます。文字列 $s$ に少なくとも2回以上出現する文字がある限り、次のような操作を行います。

文字列 $s$ の中で位置 $i$ の文字が少なくとも2回出現するようなインデックス $i$ $(1 \leq i \leq |s|)$ を選び、位置 $i$ の文字を削除する、即ち、 $s$ を $s_1 s_2 \dots s_{i-1} s_{i+1} s_{i+2} \dots s_n$ に置換する

例えば、 $s=$ "codeforces"の場合、次のような一連の操作を行うことができます。

$i = 6$ $\Rightarrow$ $s=$ "codefrces"
$i = 1$ $\Rightarrow$ $s=$ "odefrces"
$i = 7$ $\Rightarrow$ $s=$ "odefrcs"

文字列 $s$ が与えられたとき、その文字列のすべての文字がユニーク*2になるような一連の操作を行った後に得られる、辞書順最大の文字列を求めて下さい。

長さ $n$ の文字列 $a$ が長さ $m$ の文字列 $b$ よりも辞書順で小さいのは、以下の場合です。

文字列 $a$ と $b$ の最初の $i-1$ 文字が同じで、文字列 $a$ の $i$ 文字目が文字列 $b$ の $i$ 文字目よりも小さいようなインデックス $i$ $(1 \leq i \leq \min(n,\,m))$ が存在する場合
または文字列 $a$ と $b$ の最初の $\min(n,\,m)$ 文字が同じで、 $n \lt m$ である場合

例えば、文字列 $a=$ "aezakmi"は文字列 $b=$ "aezus"よりも辞書順で小さいです。

入力

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

各テストケースは、小文字のラテン文字からなる文字列 $s$ $(1 \leq |s| \leq 2 \cdot 10^5)$ によって特徴づけられる。

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

出力

各テストケースについて、文字列の全ての文字がユニークになるような一連の操作を行った後に得られる、辞書順最大の文字列を出力せよ。

入出力例

6
codeforces
aezakmi
abacaba
convexhull
swflldjgpaxs
myneeocktxpqjpz

odfrces
ezakmi
cba
convexhul
wfldjgpaxs
myneocktxqjpz

*1:露[pəlʲɪˈkarp]、ポリカルプ、ポリカープ、Polycarp: 古希Πολύκαρπος/po.lý.kar.pos/、ポリュカルポスに由来する人名

*2:全ての文字が重複しない