問題文

4 種類の文字 U, T, P, C からなる長さ N の文字列 S が与えられます。

あなたは、次の操作を好きな回数行うことが出来ます。

• 整数 i, j \, (1 \leq i < j \leq N) を選ぶ。S の i 番目の文字と j 番目の文字を入れ替える。

文字列 S が以下の条件を満たすようにするために必要な操作回数の最小値を求めてください。

• S は連続部分文字列として UTPC を含む。

ただし、S は U, T, P, C をそれぞれ 1 つ以上含むことが保証されます。

制約

• 4 \leq N \leq 10000
• S は U, T, P, C からなる長さ N の文字列
• S は U, T, P, C をそれぞれ 1 つ以上含む

入力例 1

5
UTCUP

出力例 1

2

UTCUP \rightarrow UTPUC \rightarrow UTPCU のように 2 回操作を行うと、1 文字目から 4 文字目までが UTPC となるため、S が条件を満たします。

入力例 2

4
UTPC

出力例 2

0

最初から条件を満たす場合、0 を出力してください。

入力例 3

20
PTPUTPTUCPTUPTUPCTPC

出力例 3

1

問題文

長さ N の数列 A =(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N) が与えられます。

あなたは次の操作を 0 回以上好きな回数行うことができます。

• 整数 i\ (1 \le i \le N) を選ぶ。 A_i と B_i を入れ替える。

数列のスコアを \displaystyle\sum_{i=1}^N \sum_{j=1}^N \mathrm{min} (A_i,B_j) で定めます。

あなたの目標は操作後の数列のスコアを最大化することです。 スコアの最大値を達成するような操作後の数列を一つ出力してください。 そのような数列が複数存在する場合、どれを出力しても構いません。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 入力は全て整数
• 1 \le T \le 2 \times 10^5
• 1 \le N \le 2 \times 10^5
• 1 \le A_i , B_i \le 10^8
• ひとつの入力について、含まれるテストケースの N の総和は 2 \times 10^5 を超えない

入力例 1

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

出力例 1

4 2 6
1 5 3
1 2
2 1

1 つ目のケースでは、例えば i=1 とする操作と、 i=3 とする操作を行うことにより、スコアの最大値 22 を達成できます。

2 つ目のケースでは、例えば操作を行わないことにより、スコアの最大値 5 を達成できます。

問題文

赤いボールと青いボールがそれぞれ N 個あります。i 個目の赤いボールには整数 A_i が、i 個目の青いボールには整数 B_i が書かれています。

あなたは次の操作を 0 回以上 N 回以下の好きな回数行えます。

• 赤いボールと青いボールを 1 個ずつ選び、食べる。i 回目の操作では、食べたボールに書かれていた整数がそれぞれ X, Y であるとして、XY + C_i 点を得る。

獲得可能な合計点数の最大値を求めてください。

制約

• 入力は全て整数
• 1 \le N \le 2 \times 10^5
• |A_i|, |B_i| \le 10^6
• 1 \le C_i \le 10^{12}

部分点

• 1 \leq N \leq 1000 を満たすデータセットに正解した場合は 30 点が与えられる。

入力例 1

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

出力例 1

79

((-2) \times (-8) + 3) + (3 \times (-1) + 2) + (8 \times 7 + 5) = 79 点が獲得可能な合計点数の最大値です。

入力例 2

10
-809372 563575 -351229 -20556 -309920 85426 -952799 739479 -66554 -296504
735902 631932 -407775 895728 302156 -968417 -963982 -894325 -804784 78537
282707723857 731189330739 1910286918 339802329211 611404539679 296303238506 337317063340 503492686568 1614407806 11314313

出力例 2

6622583878238

問題文

以下の性質を持つ有向グラフを Chain Graph と呼ぶことにします。

• 相異なる頂点 i, j, k について、 i \rightarrow j と j \rightarrow k の辺があるとき、i \rightarrow k の辺も存在する。
• 無向グラフとしてみたときに、自己ループや多重辺が存在しない。

無向辺からなる N 頂点の完全グラフが与えられます。頂点には 1 から N の番号がついています。はじめ、N-1 本の辺が赤で塗られており、木をなしています。i 番目の赤色の辺は A_i と B_i を結ぶ辺です。残りの辺は白色です。

あなたは、以下の操作を順番に行い、グラフの辺の色と向きを定めます。

• 全ての白色の辺をそれぞれ赤色、または青色に塗る。
• 全ての赤色の辺、青色の辺それぞれに向きをつける。

赤色、青色それぞれの辺のみからなるグラフが Chain Graph となるような操作後のグラフとしてありえるものの数を 998244353 で割ったあまりを求めてください。

制約

• 入力は全て整数
• 1 \le N \le 100
• 1 \le A_i, B_i \le N
• 与えられる赤色の辺からなるグラフは木である

入力例 1

3
1 2
2 3

出力例 1

10

以下の二つのグラフがありうるグラフの一例です。

入力例 2

5
1 2
1 3
2 4
5 2

出力例 2

1304

以下のようなグラフが考えられます。

入力例 3

10
1 2
1 3
4 2
2 5
3 6
6 7
8 7
9 5
5 10

出力例 3

793075136

答えを 998244353 で割った余りを出力してください。

問題文

座標平面上に N 個の点があります。i 個目の点は、座標 (x_i, y_i) に位置しており、その価値は c_i です。

あなたの仕事は、N 個の点からちょうど K 個の点を選ぶことです。その後、以下のように変数を定めます。

• X_{\max} \coloneqq 選んだ点の x 座標の最大値
• X_{\min} \coloneqq 選んだ点の x 座標の最小値
• Y_{\max} \coloneqq 選んだ点の y 座標の最大値
• Y_{\min} \coloneqq 選んだ点の y 座標の最小値
• S \coloneqq 選んだ点の価値の総和

点を選び終えた後、あなたは報酬として (X_{\max} - X_{\min}) + (Y_{\max} - Y_{\min}) + S 円を獲得することができます。最大で何円の報酬を獲得可能か求めてください。

制約

• 入力は全て整数
• 1 \le K \le N \le 2 \times 10^5
• 1 \le x_i, y_i \le 10^9
• 1 \le c_i \le 10^9

部分点

• 1 \le N \le 1000 を満たすデータセットに正解した場合は 30 点が与えられる。

入力例1

3 2
1 3 1
3 1 1
3 3 2

出力例1

6

1 個目の点と 2 個目の点を選ぶと、報酬の額は (3 - 1) + (3 - 1) + 2 = 6 で、 6 円となります。これよりも高い額は達成不可能なので、6 が答えです。

入力例2

12 5
79 29 4
47 96 11
31 100 13
89 67 13
28 45 9
66 70 12
18 12 9
21 57 14
67 17 6
91 12 9
79 11 8
67 50 6

出力例2

220

問題文

あなたは、魔物の群れに遭遇しました。魔物の群れは N 匹の魔物で構成されており、あなたの目の前に縦一列に並んでいます。前から i 番目の魔物の体力は h_i です。

あなたは、以下の 2 種類の攻撃を使い分けることによって、全ての魔物を倒すことにしました。

• 剣で攻撃する。一番前の生き残っている魔物に、その魔物の残りの体力と同じ分のダメージを与える。
• 槍で攻撃する。全ての生き残っている魔物に、 1 ダメージずつ与える。

体力が 0 となった魔物は消滅します。

あなたには、直属の上官が 2 人居ます。攻撃を行うたびに、その 1 回の攻撃で与えたダメージ量に応じて上官からボーナスとして勲章が与えられます。

1 人目の上官からは、魔物に与えたダメージの合計が k_1 以上であれば、赤い勲章が 1 つ与えられます。
2 人目の上官からは、魔物に与えたダメージの合計が k_2 以上であれば、青い勲章が 1 つ与えられます。

全ての魔物を消滅させたとき、持っている赤い勲章と青い勲章の合計個数としてあり得る最大値を求めてください。

制約

• 入力は全て整数
• 1 \le N \le 2 \times 10^5
• 1 \le k_1 \le k_2 \le 2 \times 10^5
• 1 \le h_i \le 2 \times 10^5

部分点

• k_1 = k_2 を満たすデータセットに正解した場合は 30 点が与えられる。

入力例 1

4 2 3
3 2 1 1

出力例 1

4

次のように攻撃を行えばよいです。

• 剣で攻撃する。3 ダメージを与え、赤い勲章と青い勲章が与えられる。
• 剣で攻撃する。2 ダメージを与え、赤い勲章が与えられる。
• 槍で攻撃する。2 ダメージを与え、赤い勲章が与えられる。

入力例 2

5 4 5
2 2 2 2 2

出力例 2

4

入力例 3

15 4 7
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9

出力例 3

16

問題文

あなたは H 行 W 列の行列を持っています。行列の i 行目、j 列目の成分は 1 桁の正整数 S_{i, j} です。

あなたは次の 2 種類の操作を好きな順序で、合計 H + W - 2 回行えます。

• 隣接する 2 行 (i, i + 1 行目) を選び、2 行の成分の総和の点数を得る。そして、2 行を圧縮する。すなわち、(存在すれば) i - 1 行目以前、i 行目と i + 1 行目の行ベクトルとしての和、(存在すれば) i + 2 行目以降、をこの順に縦に連結したものに行列全体を置き換える。この操作は、行列が 2 行以上である場合に行える。
• 隣接する 2 列 (j, j + 1 列目) を選び、2 列の成分の総和の点数を得る。そして、2 列を圧縮する。すなわち、(存在すれば) j - 1 列目以前、j 列目と j + 1 列目の列ベクトルとしての和、(存在すれば) j + 2 列目以降、をこの順に横に連結したものに行列全体を置き換える。この操作は、行列が 2 列以上である場合に行える。

獲得可能な合計点数の最大値を求めてください。

制約

• 入力は全て整数
• 1 \le H, W \le 3000
• 1 \le S_{i, j} \le 9

部分点

• 1 \leq H, W \leq 200 を満たすデータセットに正解した場合は 30 点が与えられる。

入力例 1

3 3
314
159
265

出力例 1

130

順に、 2, 3 列目、2, 3 行目、1, 2 行目、1, 2 列目、と選ぶのが最適な方法の一つです。このとき、 30 + 28 + 36 + 36 = 130 点が得られます。行列は以下のように変化していきます。

$$ \begin{bmatrix} 3 & 1 & 4 \\ 1 & 5 & 9 \\ 2 & 6 & 5 \end{bmatrix} \to \begin{bmatrix} 3 & 5 \\ 1 & 14 \\ 2 & 11 \end{bmatrix} \to \begin{bmatrix} 3 & 5 \\ 3 & 25 \end{bmatrix} \to \begin{bmatrix} 6 & 30 \end{bmatrix} \to \begin{bmatrix} 36 \end{bmatrix} $$

入力例 2

10 8
82974679
74744362
34499984
86891758
56419363
76176864
78392791
71539599
44588446
71227999

出力例 2

4555

問題文

数列内の隣接する二項の差の絶対値が全て 1 であるとき、その数列を 良い数列 と呼ぶことにします。

良い数列 X のスコアを次のように定めます。

• X_{i} - X_{i-1} = 1 となる全ての i について X_i をかけあわせた値
• そのような i が存在しない場合は 1

長さが N 、初項が A、 末項が B であるような 良い数列 全てに対するスコアの総和を 998244353 で割った余りを出力してください。

制約

• 入力は全て整数
• 2 \leq N \leq 2 \times 10^{7}
• 0 \leq A,B \leq 2 \times 10^{7}

入力例 1

3 0 2

出力例 1

2

条件を満たす良い数列は (0, 1, 2) のみであり、この数列のスコアは 1 \times 2=2 である。

入力例 2

5 0 2

出力例 2

12

条件を満たす良い数列は (0, 1, 2, 3, 2), (0, 1, 2, 1, 2), (0, 1, 0, 1, 2), (0, -1, 0, 1, 2) の 4 種類であり、 それぞれの数列のスコアは 6, 4, 2, 0 である。

入力例 3

1877 4 12

出力例 3

672408519

問題文

1 から M までの数が一つずつ書かれた M 枚のカードからなる山札が N 個あります。 i 個目の山札の上から j 枚目には、 a_{i, j} が書かれています。

あなたはこれらの山札に対して、以下の 2 種類の操作をそれぞれ好きな順に何度でも行うことができます。

• 操作 1：山札を 1 つ選び、一番上のカードを、同じ山札の一番下に移動させる。
• 操作 2：N 個の山札の一番上のカードに書かれている数が全て同じなら、それらを全て取って食べる。

全てのカードを食べるために必要な操作 1 の回数の最小値はいくつですか？

制約

• 入力は全て整数
• 1 \le N \le 2 \times 10^5
• 1 \le M \le 22
• 1 \leq a_{i, j} \leq M
• a_{i, j} \neq a_{i, k} (j \neq k)

部分点

• 1 \le M \le 16 を満たすデータセットに正解した場合は 30 点が与えられる。

入力例 1

4 3
2 3 1
1 2 3
2 1 3
3 2 1

出力例 1

4

次のように操作を行えばよいです。

• 山札 2 に対して操作 1 を行う。
• 山札 4 に対して操作 1 を行う。
• 操作 2 を行う。（全ての山札の一番上のカードは 2 である。）
• 山札 1 に対して操作 1 を行う。
• 山札 2 に対して操作 1 を行う。
• 操作 2 を行う。（全ての山札の一番上のカードは 1 である。）
• 操作 2 を行う。（全ての山札の一番上のカードは 3 である。）

入力例 2

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

出力例 2

35

問題文

マコトくんは以下の問題を考えました。

An Interval Scheduling Problem

N 個の区間 [L_i,R_i] が与えられます。以下の条件を満たすように選択できる区間の個数の最大値を求めてください。

• 選択した区間のうちどの二つも、共通部分を持たない。

制約

• 数列 L と R の中には、 1 から 2N までの整数がちょうど 1 回ずつ出現する
• L_i < R_i ( 1 \leq i \leq N)

この問題は典型的すぎたので、数え上げが大好きなテルオくんは以下のように問題を作り替えました。

Interval Scheduling Problems

整数 N が与えられます。An Interval Scheduling Problem の制約を満たす入力全てに対する解の総和を 998244353 で割った余りを出力してください。

Interval Scheduling Problems を解いてください。

制約

• 1 \leq N \leq 2\times 10^5

部分点

この問題には複数の部分点が設定されている。

• 1 \le N \le 50 を満たすデータセットに正解した場合は 10 点が与えられる。
• 1 \le N \le 3000 を満たすデータセットに正解した場合は 30 点が与えられる。

入力例1

2

出力例1

8

An Interval Scheduling Problem の入力として考えられるものは、以下の 6 通りです。

• L=(1,2), R=(3,4)
• L=(1,2), R=(4,3)
• L=(1,3), R=(2,4)
• L=(2,1), R=(3,4)
• L=(2,1), R=(4,3)
• L=(3,1), R=(4,2)

上記 6 通りの入力に対する An Interval Scheduling Problem の答えは 1,1,2,1,1,2 なので、Interval Scheduling Problems の答えは 1+1+2+1+1+2 を 998244353 で割った余りの 8 となります。

入力例 2

4

出力例 2

4944

このテストケースは 10 点分の部分点に含まれます。

入力例 3

2021

出力例 3

383310824

このテストケースは 30 点分の部分点に含まれます。

入力例 4

100000

出力例 4

143469183

このテストケースは部分点に含まれません。

問題文

P を素数 998244353 とします。 多項式 f(x) に対して次の一連の操作を定めます。

1. f(x) と (1 + x^k)g(x) の各次数の係数を P で割った余りが等しくなるような正の整数 k と有限次の多項式 g(x)\neq 0 を選択する。
2. その後、f(x) を上記の g(x) に置き換えて 2^k のスコアを得る。

ある多項式に対して、この操作を好きな回数行って得られるスコアの総和の最大値を多項式の 美しさ と定めます。

数列 A=(A_0,\ldots,A_{N - 1}) と Q 個のクエリが与えられます。

i 番目のクエリでは整数 l_i,r_i が与えられるので、多項式 \displaystyle f(x) = \sum_{j=0}^{r_i - l_i}A_{j + l_i}x^{j} の 美しさ を P で割った余りを求めてください。

ただし、操作における g(x) の係数は 998244353 未満の非負整数に限ります。(13:10 追記)

制約

• 入力は全て整数
• 2\leq N \leq 2000
• 1\leq Q \leq 2000
• 0\leq A_i < P
• 0\leq l_i < r_i \leq N - 1

入力例 1

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

出力例 1

4
6
0

1つめのクエリについて、f(x) = (1 + 2x + x^2) になりますが、 k = 1 を二回選択するのが最善です。

2つめのクエリについて、f(x) = (1 + x + x^2 + x^3)となりますが、 一回目の操作でk = 1、二回目の操作でk = 2 を選択するのが最善です。

3つめのクエリについて、f(x) = (1 + x + x^2)となりますが、一回も操作を行えません。

入力例 2

11 2
1 1 0 0 0 0 0 0 0 1 1
0 10
4 5

出力例 2

514
0

1つめのクエリでは、f(x) = (1 + x + x^9 + x^{10}) の美しさを計算し、2つめのクエリでは、f(x) = 0 の美しさを計算します。

問題文

縦 H 行、横 W 列のグリッド状の迷路があります。 各マスには S , G , # , . のいずれかの文字が書かれています。i 行目 j 列目のマスに書かれている文字は c_{i,j} です。# と書かれたマスは壁になっており、そうでないマスは壁ではありません。 また、S と G は 1 つずつで、上下左右に隣接していないことが保証されます。

迷路が次の条件を満たす時、到達可能な状態 と呼ぶことにします。

• S と書かれたマスから、G と書かれたマスに、上下左右に隣接する壁でないマス (つまり # と書かれてないマス) のみを通って到達できる。

  ただし、迷路の外に出るような移動はできない。

最初、迷路は 到達可能な状態 であることが保証されます。

Alice と Bob がこの迷路を使ってゲームをします。 Alice が先手で、交互に以下の操作を行います。

• . と書かれたマスを 1 つ選び、 # と書かれたマスに変更する。

先に自分の操作終了時に、迷路が 到達可能な状態 でなくなったプレイヤーの勝利となります。 本問題の制約下で与えられる迷路では、必ず勝者が決定することが証明できます。 二人が最適に行動した場合、どちらが勝つか求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \le T \le 50
• 2 \le H,W \le 100
• 迷路に含まれる文字は、S, G, ., # のいずれか
• S と G は 1 つずつ含まれ、上下左右に隣接していない
• 与えられる迷路は 到達可能な状態 である

入力例 1

2
2 2
S.
.G
2 3
#G#
S.#

出力例 1

Bob
Alice

1つめのケースでは、Aliceが選べるマスは右上か左下の2通りですが、どちらを選んでも次にBobがもう一方の . であるマスを選択してBobが勝ちます。

2つめのケースでは、Aliceが2行目の . を # に変えてAliceの勝利となります。

問題文

あなたの前に鍵のかかった扉が一つあります。鍵屋さんは N 個の鍵を所有しており、その中にちょうど一つだけ正しい鍵が存在します。 i 番目の鍵が正しい鍵である確率は p_i %であることが分かっています。

扉は建付けが悪く、正しい鍵を選んでも扉が開くとは限りません。 i 番目の鍵を用いて扉を開こうとした場合、扉が開く確率は以下の通りです。

• i 番目の鍵が正しい鍵である場合： q_i % の確率で扉が開く。複数回開こうとした場合は独立に判定される。
• i 番目の鍵が正しい鍵でない場合：扉は開かない 。

あなたは 最初 K 円持っています。 扉が開くか、所持金が 0 円になるまで、以下の操作を行います。

• 鍵屋さんに 1 円支払う。鍵屋さんから鍵を一つ選んで借りて、扉を一回開こうとする。 その後、鍵を返す。

制約

• 入力は全て整数
• 1 \le N,K \le 100
• 1 \le p_i ,q_i \le 100
• p_i の総和は 100

入力例 1

2 2
50 50
50 50

出力例 1

0.25

所持金が 1 円以上残っていて、扉が開いていないならば、 1 番目の鍵 を選ぶという戦略を考えます。確率 25 % で 1 円残り、確率 75 % で 0 円になります。残金の期待値は 0.25 円ですが、実はこれが期待値の最大値です。

入力例 2

1 2
100
100

出力例 2

1

1 番目の鍵を選べばよいです。

入力例 3

10 20
10 10 10 20 6 5 4 8 12 15
10 20 30 40 50 60 70 80 90 10

出力例 3

8.2045400000000000031

問題文

N 頂点の木の辺の列 E = \left(\left(X_1, Y_1\right), \ldots, \left(X_{N-1}, Y_{N-1}\right) \right) から以下のような手順で生成される順列を f(E) とします。

1. 順列 Q = (1, \ldots, N) を準備する。
2. i = 1, \ldots, N - 1 の順に Q の X_i 番目と Y_i 番目の要素を入れ替える。
3. 最終的な Q を f(E) とする。

\left(1, \ldots, N \right) の順列 P と M 個の辺 (A_i, B_i) が与えられます。M 個の辺をすべて含み、木をなすような辺の列 E であって、f(E) = P を満たすものがあるかを判定し、存在する場合は一つ出力してください。複数存在する場合はどれを出力しても構いません。

M 個の辺からなるグラフは自己ループや閉路を持たないことが保証されます。

制約

• 入力は全て整数
• 1 \le N \le 2 \times 10^5
• 0 \le M \le N - 1
• 1 \le P_i \le N
• P は \left(1, \ldots, N \right) の順列
• 1 \le A_i, B_i \le N
• A_i \neq B_i
• (A_i, B_i) からなるグラフは閉路や多重辺をもたない

入力例 1

3 1
2 3 1
3 2

出力例 1

Yes
1 2
2 3

数列は (1, 2, 3) \rightarrow (2, 1, 3) \rightarrow (2, 3, 1) と変化します。