Educational Codeforces Round 123 問題文和訳

A. Doors and Keys / Двери и ключи
- 入力
- 出力
- 入出力例
- 注記
B. Anti-Fibonacci Permutation / Антифибоначчиевы перестановки
C. Increase Subarray Sums / Увеличь суммы подотрезков
- 入力
- 出力
- 入出力例
- 注記
D. Cross Coloring / Раскраска крестиками
E. Expand the Path / Расширь маршрут
- 入力
- 出力
- 入出力例
- 注記
F. Basis / Базис
- 入力
- 出力
- 入出力例
- 注記

A. Doors and Keys / Двери и ключи

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

騎士が細長い廊下の前に立っています。その反対側に姫が待っています。

廊下には、赤、緑、青の扉の3つの扉があります。扉は順々に並んでいますが、順番は違うものかもしれません。次の扉に進むためには、騎士はまず、先の扉を開かなければなりません。

それぞれの扉は、対応する色の鍵でのみ開けることができます。赤、緑、青の鍵の3つの鍵も廊下のどこかに置かれています。扉を開けるためには、騎士はまず、その色の鍵を拾う必要があります。

騎士は廊下の地図を所持しています。その地図は、6文字から成る文字列として記述することができます。

R, G, B: それぞれ赤、緑、青の扉を表す
r, g, b: それぞれ赤、緑、青の鍵を表す

この6文字はそれぞれちょうど1度ずつだけ文字列の中に現れます。

騎士は通路の前、即ち地図の左側に立っています。

廊下の地図が与えられたとき、騎士が全ての扉を開けて廊下の先にいる姫に会うことができるかどうかを判定して下さい。

入力

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

各テストケースは単一の文字列から成る。各文字はR, G, B(扉)、r, g, b(鍵)のいずれかで、それぞれちょうど一回ずつ現れる。

出力

各テストケースについて、騎士が全ての扉を開けることができる場合、YESを出力せよ。そうでない場合、NOを出力せよ。

入出力例

4
rgbBRG
RgbrBG
bBrRgG
rgRGBb

YES
NO
YES
NO

注記

1つ目のテストケースでは、騎士はまず全ての鍵を集め、そしてその鍵で全ての扉を開けます。

2つ目のテストケースでは、騎士の目の前に赤い扉がありますが、騎士はその扉用の鍵を持っていません。

3つ目のテストケースでは、それぞれの扉の前に鍵があるので、騎士は鍵を集めてすぐに使用することを3回行います。

4つ目のテストケースでは、騎士は青い扉を開けることができません。

B. Anti-Fibonacci Permutation / Антифибоначчиевы перестановки

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

長さ $n$ の順列 $p$ が、全ての $i$ $(3 \leq i \leq n)$ に対して条件 $p_{i-2} + p_{i-1} \neq p_i$ が成り立つとき、anti-Fibonacciと呼ぶことにします。順列とは、 $1$ から $n$ までの各整数をちょうど1回ずつ持つ、長さ $n$ の配列のことです。

与えられた数 $n$ に対して、長さ $n$ の相異なるanti-Fibonacci順列を出力して下さい。

入力

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

各テストケースの単一行には、単一の整数 $n$ $(3 \leq n \leq 50)$ が与えられる。

出力

各テストケースについて $n$ 行出力せよ。各行には長さ $n$ のanti-Fibonacci順列が含まれていなければならない。各テストケースにおいて、各順列を2回以上出力してはいけない。

答えが複数存在する場合、そのうちのいずれかを出力せよ。この問題の制約の下では，長さ $n$ の相異なるanti-Fibonacci順列を得ることが常に可能であることは証明できる。

入出力例

2
4
3

C. Increase Subarray Sums / Увеличь суммы подотрезков

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

$n$ 個の整数からなる配列 $a_1,\,a_2,\,\dots,\,a_n$ が与えられます。また、整数値 $x$ も与えられます。

$f(k)$ を、次の操作を行った後の $a$ の連続部分列の最大和とします: ちょうど $k$ 個の異なる位置の要素に $x$ を加える。空部分列も考慮し、その和は $0$ です。

部分列は、増加した要素全てを含む必要はないことに注意してください。

$0$ から $n$ までの全ての $k$ について、 $f(k)$ の最大値を独立に計算してください。

入力

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

テストケースの1行目には2個の整数 $n,\,x$ $(1 \leq n \leq 5000;$ $0 \leq x \leq 10^5)$ が与えられる、これらは配列の大きさと加算値である。

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

全てのテストケースでの $n$ の和は $5000$ を超えない。

出力

各テストケースについて $n+1$ 個の整数を出力せよ、それらはそれぞれ $0$ から $n$ までの全ての $k$ についての $f(k)$ の最大値である。

入出力例

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

10 12 14 16 18
0 4 4 5
4 6 6 7 7 7 7 8 8 8 8

注記

1つ目のテストケースでは、どの要素に $x$ を足すかは関係ありません。和が最大となる部分列は常に配列全体です。 $k$ 個の要素を $x$ だけ増やすと、 $k \cdot x$ が和に足されます。

2つ目のテストケースでは、

$k = 0$ では、空部分列が最適である。
$k = 1$ では、位置 $3$ の要素を増やすのが最適である。最適和は部分列 $[3,\,3]$ *1 の $-1 + 5 = 4$ となる。
$k = 2$ では、位置 $3$ と他の1つの位置の要素を増やすのが最適である。最適和は部分列 $[3,\,3]$ の $4$ のままである。
$k = 3$ では、全ての要素を増やさなければならない。最適和は部分列 $[1,\,3]$ の $(-2 + 5) + (-7 + 5) + (-1 + 5) = 5$ となる。

D. Cross Coloring / Раскраска крестиками

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

$n \times m$ のマス目( $n$ 行 $m$ 列)で表すことができる1枚のシートがあります。初期状態では全てのセルは白です。

このシートに対して $q$ 回操作を行いました。そのうちの $i$ 番目の操作は次のように表されます。

$x_i$ $y_i$ : 白でない $k$ 色のうち1色を選び、行 $x_1$ 全体と列 $y_i$ 全体をその色で塗る。操作の前に着色されていたかどうかに関係なく、各セルに新しい色が適用される。

$q$ 回の操作を全て適用した後のシートを彩色と呼びます。異なる色に着色されたセルが少なくとも一つ存在したとき、2つの彩色は異なるといいます。

彩色は何通り存在しますか? 数をmodulo $998\,244\,353$ で出力して下さい。

入力

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

テストケースの1行目には4個の整数 $n,\,m,\,k,\,q$ $(1 \leq n,\,m,\,k,\,q \leq 2 \cdot 10^5)$ が与えられる、これらはシートの大きさ、白以外の色数、操作回数である。

続く $q$ 行の $i$ 行目には $i$ 番目の操作についての記述が与えられる。2個の整数 $x_i,\,y_i$ $(1 \leq x_i \leq n;$ $1 \leq y_i \leq m)$ で、それぞれ操作を適応する行と列である。

全てのテストケースでの $q$ の和は $2 \cdot 10^5$ を超えない。

出力

各テストケースについて単一の整数を出力せよ、その数とは彩色数のmodulo $998\,244\,353$ である。

入出力例

3
4

E. Expand the Path / Расширь маршрут

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

大きさ $n \times n$ のグリッドが与えられます。行は上から順に $1$ から $n$ まで、列は左から順に $1$ から $n$ までの番号が振られています。

ロボットがセル $(1,\,1)$ に配置されています。ロボットは次の2種類の移動を行うことができます。

D: 下に1セル移動
R: 右に1セル移動

ロボットはグリッドの外に出ることはできません。

一連の動き $s$ が与えられます、これはロボットの初期経路です。この経路でロボットがグリッドの外に進むことはありません。

これに対して、任意回数修正を加えることができます(0個の場合も可)。1回の修正では、一連の中の動きの1つを複製することができます。即ち、DをDDに、RをRRに置き換えます。

そのセルを通り、グリッドの外に進むことのないような修正後の経路が存在するようなセルの個数を数えて下さい。

入力

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

各テストケースの1行目には単一の整数 $n$ $(2 \leq n \leq 10^8)$ が与えられる、これはグリッドの行や列の数である。

各テストケースの2行目には文字DとRのみから成る、空でない文字列 $s$ が与えられる、これは初期経路である。この経路でロボットがグリッドの外に進むことはない。

全てのテストケースでの文字列 $s$ の長さの和は $2 \cdot 10^5$ を超えない。

出力

各テストケースについて単一の整数を出力せよ、その数とは、そのセルを通り、グリッドの外に進むことのないような修正後の経路が存在するようなセルの個数である。

入出力例

3
4
RD
5
DRDRDRDR
3
D

13
9
3

注記

1つ目のテストケースでは、次のような修正経路を考えれば十分です。

RD $\rightarrow$ RRD $\rightarrow$ RRRD $\rightarrow$ RRRDD $\rightarrow$ RRRDDD: この経路ではセル $(1,\,1),$ $(1,\,2),$ $(1,\,3),$ $(1,\,4),$ $(2,\,4),$ $(3,\,4),$ $(4,\,4)$ を訪れる
RD $\rightarrow$ RRD $\rightarrow$ RRRD $\rightarrow$ RRDDD: この経路ではセル $(1,\,1),$ $(1,\,2),$ $(1,\,3),$ $(2,\,3),$ $(3,\,3),$ $(4,\,3)$ を訪れる
RD $\rightarrow$ RDD $\rightarrow$ RDDD: この経路ではセル $(1,\,1),$ $(1,\,2),$ $(2,\,2),$ $(3,\,2),$ $(4,\,2)$ を訪れる

従って、1回以上の修正後の経路で訪れるセルは $(1,\,1),$ $(1,\,2),$ $(1,\,3),$ $(1,\,4),$ $(2,\,2),$ $(2,\,3),$ $(2,\,4),$ $(3,\,2),$ $(3,\,3),$ $(3,\,4),$ $(4,\,1),$ $(4,\,3),$ $(4,\,4)$ です。

2つ目のテストケースでは、ロボットがグリッドの外に進まない修正経路はありません。そのため、訪れるセルは経路DRDRDRで訪れるもののみです。

3つ目のテストケースでは、1回以上の修正後の経路で訪れるセルは $(1,\,1),$ $(2,\,1),$ $(3,\,1)$ です。

以下は、全てのテストケースでのセルです。
f:id:Flkanjin:20220223142014p:plain

F. Basis / Базис

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

整数配列 $a$ に対して、その要素数を $|a|$ と定義します。

2つの関数を導入します。

$F(a,\,k)$ *2 は整数配列 $a$ と正整数 $k$ を受け取る関数で、この関数の計算結果は $a$ の各要素をその要素のちょうど $k$ 回のコピーで置き換えることによって得られる配列の最初の $|a|$ 個の要素を含む配列である。
例えば、 $F([2,\,2,\,1,\,3,\,5,\,6,\,8],\,2)$ は次のように計算する。まず、配列の各要素をその2回のコピーで置き換え、 $[2,\,2,\,2,\,2,\,1,\,1,\,3,\,3,\,5,\,5,\,6,\,6,\,8,\,8]$ を得る。そして、得られた配列の最初の $7$ 要素を取り出し、関数の計算結果は $[2,\,2,\,2,\,2,\,1,\,1,\,3]$ となる。
$G(a,\,x,\,y)$ は整数配列 $a$ と異なる2個の正整数 $x,\,y$ を受け取る関数である。この関数の計算結果は $x$ に等しい全ての要素を $y$ に置き換え、 $y$ に等しい全ての要素を $x$ に置き換えた配列 $a$ である。
例えば、 $G([1,\,1,\,2,\,3,\,5],\,3,\,1) = [3,\,3,\,2,\,1,\,5]$ である。

次のいずれかを満たす場合、配列 $a$ は $b$ の親であるといいます。

$F(a,\,k) = b$ であるような正整数 $k$ が存在する
$G(a,\,x,\,y) = b$ であるような異なる2個の正整数 $x,\,y$ が存在する

$c_0$ が $a$ であり $c_m$ が $b$ であり、各 $i \in [1,\,m]$ について $c_{i-1}$ が $c_i$ の親であるような有限配列 $c_0,\,c_1,\,\dots,\,c_m$ $(m \geq 0)$ が存在するとき、配列 $a$ は配列 $b$ の祖先といいます。

さて、問題そのものについてです。

2個の整数 $n,\,k$ が与えられています。次の条件を満たす配列の列 $s_1,\,s_2,\,\dots,\,s_m$ を作ることが目標です。

各配列 $s_i$ はちょうど $n$ 個の要素を含み，全要素は $1$ から $k$ までの整数である
ちょうど $n$ 個の $1$ から $k$ までの整数から成る配列 $a$ それぞれに対して、この列には、 $a$ の祖先であるような少なくとも1つの配列 $s_i$ を含む

このような列に含まれる配列の最小個数を出力して下さい。

入力

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

出力

1つの整数を出力せよ、条件を満たす配列の最小個数である。答えが大きくなる可能性があるため、modulo $998244353$ で出力せよ。

入出力例

3 2

4 10

13 37

27643508

1337 42

211887828

198756 123456

159489391

123456 198756

460526614

注記

1つ目の入出力例を分析しましょう。

1つ目の入出力例で考えられる答えの1つは、列 $[[2,\,1,\,2],\,[1,\,2,\,2]]$ です。 $1$ から $2$ までの要素からなる大きさ $3$ の配列はすべてこの列内に祖先を持ちます。

配列 $[1,\,1,\,1]$ の場合、祖先は $[1,\,2,\,2]$ である: $F([1,\,2,\,2],\,13) = [1,\,1,\,1]$
配列 $[1,\,1,\,2]$ の場合、祖先は $[1,\,2,\,2]$ である: $F([1,\,2,\,2],\,2) = [1,\,1,\,2]$
配列 $[1,\,2,\,1]$ の場合、祖先は $[2,\,1,\,2]$ である: $G([2,\,1,\,2],\,2,\,1) = [1,\,2,\,1]$
配列 $[1,\,2,\,2]$ の場合、祖先は $[1,\,2,\,2]$ である
配列 $[2,\,1,\,1]$ の場合、祖先は $[1,\,2,\,2]$ である: $G([1,\,2,\,2],\,1,\,2) = [2,\,1,\,1]$
配列 $[2,\,1,\,2]$ の場合、祖先は $[2,\,1,\,2]$ である
配列 $[2,\,2,\,1]$ の場合、祖先は $[2,\,1,\,2]$ である: $F([2,\,1,\,2],\,2) = [2,\,2,\,1]$
配列 $[2,\,2,\,2]$ の場合、祖先は $[1,\,2,\,2]$ である: $G(F([1,\,2,\,2],\,4),\,1,\,2) = G([1,\,1,\,1],\,1,\,2) = [2,\,2,\,2]$

*1:配列の添え字の範囲を表す

*2:ここでの k は入力の k とは別個である