AtCoder Daily Training HARD 2024/05/15 16:00start

E - K Swap

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

長さ N の数列 A=(a_1,\ldots,a_N) があります。また、整数 K が与えられます。

あなたは次の操作を 0 回以上何度でも行えます。

1 \leq i \leq N-K を満たす整数 i を選び、a_i と a_{i+K} の値を入れ替える。

A を昇順に並べ替えることが出来るかどうかを判定してください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq K \leq N-1
1 \leq a_i \leq 10^9
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K
a_1 \ldots a_N

出力

A を昇順に並び替えることが出来るならば Yes と、出来ないならば No と出力せよ。

入力例 1

5 2
3 4 1 3 4

出力例 1

Yes

次のように操作をすることで A を昇順に並び替えることが出来ます。

i=1 とし、a_1 と a_3 の値を入れ替える。数列は (1,4,3,3,4) となる。
i=2 とし、a_2 と a_4 の値を入れ替える。数列は (1,3,3,4,4) となる。

入力例 2

5 3
3 4 1 3 4

出力例 2

No

入力例 3

7 5
1 2 3 4 5 5 10

出力例 3

Yes

操作を行う必要が無い場合もあります。

Score : 300 points

Problem Statement

We have a sequence of length N: A=(a_1,\ldots,a_N). Additionally, you are given an integer K.

You can perform the following operation zero or more times.

Choose an integer i such that 1 \leq i \leq N-K, then swap the values of a_i and a_{i+K}.

Determine whether it is possible to sort A in ascending order.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq K \leq N-1
1 \leq a_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
a_1 \ldots a_N

Output

If it is possible to sort A in ascending order, print Yes; otherwise, print No.

Sample Input 1

5 2
3 4 1 3 4

Sample Output 1

Yes

The following sequence of operations sorts A in ascending order.

Choose i=1 to swap the values of a_1 and a_3. A is now (1,4,3,3,4).
Choose i=2 to swap the values of a_2 and a_4. A is now (1,3,3,4,4).

Sample Input 2

5 3
3 4 1 3 4

Sample Output 2

No

Sample Input 3

7 5
1 2 3 4 5 5 10

Sample Output 3

Yes

No operations may be needed.

F - Coupon

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 個の商品があります。i = 1, 2, \ldots, N について、i 番目の商品の値段は A_i 円です。

高橋君は K 枚のクーポンを持っています。
1 枚のクーポンは 1 つの商品に対して使用することができ、1 つの商品に対してはクーポンを何枚でも（ 0 枚でもよい）使用することができます。値段が a 円の商品に対して k 枚のクーポンを使用すると、その商品を \max\lbrace a - kX, 0\rbrace 円で買うことができます。

高橋君がすべての商品を買うために支払う合計金額の最小値を出力してください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq K, X \leq 10^9
1 \leq A_i \leq 10^9
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K X
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

5 4 7
8 3 10 5 13

出力例 1

1 番目の商品に対してクーポン 1 枚、3 番目の商品に対してクーポン 1 枚、5 番目の商品に対してクーポン 2 枚を使用すると、

1 番目の商品を \max\lbrace A_1-X, 0 \rbrace = 1 円で買うことができ、
2 番目の商品を \max\lbrace A_2, 0 \rbrace = 3 円で買うことができ、
3 番目の商品を \max\lbrace A_3-X, 0 \rbrace = 3 円で買うことができ、
4 番目の商品を \max\lbrace A_4, 0 \rbrace = 5 円で買うことができ、
5 番目の商品を \max\lbrace A_5-2X, 0 \rbrace = 0 円で買うことができます。

よって、すべての商品を 1 + 3 + 3 + 5 + 0 = 12 円で買うことができ、これが最小です。

入力例 2

5 100 7
8 3 10 5 13

出力例 2

入力例 3

20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

出力例 3

Score : 300 points

Problem Statement

There are N items in a shop. For each i = 1, 2, \ldots, N, the price of the i-th item is A_i yen (the currency of Japan).

Takahashi has K coupons.
Each coupon can be used on one item. You can use any number of coupons, possibly zero, on the same item. Using k coupons on an item with a price of a yen allows you to buy it for \max\lbrace a - kX, 0\rbrace yen.

Print the minimum amount of money Takahashi needs to buy all the items.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq K, X \leq 10^9
1 \leq A_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K X
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

5 4 7
8 3 10 5 13

Sample Output 1

By using 1 coupon on the 1-st item, 1 coupon on the 3-rd item, and 2 coupons on the 5-th item, Takahashi can:

buy the 1-st item for \max\lbrace A_1-X, 0 \rbrace = 1 yen,
buy the 2-nd item for \max\lbrace A_2, 0 \rbrace = 3 yen,
buy the 3-rd item for \max\lbrace A_3-X, 0 \rbrace = 3 yen,
buy the 4-th item for \max\lbrace A_4, 0 \rbrace = 5 yen,
buy the 5-th item for \max\lbrace A_5-2X, 0 \rbrace = 0 yen,

for a total of 1 + 3 + 3 + 5 + 0 = 12 yen, which is the minimum possible.

Sample Input 2

5 100 7
8 3 10 5 13

Sample Output 2

Sample Input 3

20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

Sample Output 3

G - Match or Not

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

英小文字と ? からなる文字列 S,T が与えられます。ここで、|S| \gt |T| が成り立ちます(文字列 X に対し、 |X| で X の長さを表します)。

また、|X|=|Y| を満たす文字列 X,Y は、次の条件を満たすとき及びそのときに限りマッチするといいます。

X,Y に含まれる ? をそれぞれ独立に好きな英小文字に置き換えることで X と Y を一致させることができる

x=0,1,\ldots,|T| に対して次の問題を解いてください。

S の先頭の x 文字と末尾の |T|-x 文字を順番を保ったまま連結することで得られる長さ |T| の文字列を S' とする。S' と T がマッチするならば Yes と、そうでなければ No と出力せよ。

制約

S,T は英小文字と ? からなる文字列
1 \leq |T| \lt |S| \leq 3 \times 10^5

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

|T|+1 行出力せよ。
i 行目には x=i-1 に対する出力をせよ。

入力例 1

a?c
b?

出力例 1

Yes
No
No

x=0 の場合、S' は ?c となります。ここで、S' の 1 文字目の ? を b に、T の 2 文字目の ? を c に置き換えることで S' と T を一致させることができるため、S' と T はマッチします。このため、1 行目の出力は Yes です。
x=1,2 の場合は S' はそれぞれ ac、a? であり、T とマッチしません。このため、2,3 行目の出力は No です。

入力例 2

atcoder
?????

出力例 2

Yes
Yes
Yes
Yes
Yes
Yes

入力例 3

beginner
contest

出力例 3

No
No
No
No
No
No
No
No

Score : 400 points

Problem Statement

You are given strings S and T consisting of lowercase English letters and ?. Here, |S| \gt |T| holds (for a string X, |X| denotes the length of X).

Two strings X and Y such that |X|=|Y| is said to match if and only if:

one can make X equal Y by replacing each ? in X and Y with any English letter independently.

Solve the following problem for each x=0,1,\ldots,|T|:

Let S' be the string of length |T| obtained by concatenating the first x characters and the last (|T|-x) characters of S without changing the order. Print Yes if S' and T match, and No otherwise.

Constraints

S and T are strings consisting of lowercase English letters and ?.
1 \leq |T| \lt |S| \leq 3 \times 10^5

Input

The input is given from Standard Input in the following format:

S
T

Output

Print (|T|+1) lines.
The i-th line should contain the answer for x=i-1.

Sample Input 1

a?c
b?

Sample Output 1

Yes
No
No

When x=0, S' equals ?c. Here, we can replace the 1-st character of S', ?, with b and the 2-nd character of T, ?, with c to make S' equal T, so S' and T match. Thus, Yes should be printed in the first line.
When x=1 and 2, respectively, S' is ac and a?, neither of which matches with T. Thus, No should be printed in the second and third lines.

Sample Input 2

atcoder
?????

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes

Sample Input 3

beginner
contest

Sample Output 3

No
No
No
No
No
No
No
No

H - Christmas Color Grid 1

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 450 点

問題文

この問題は問題 G と似た設定です。問題文の相違点を赤字で示します。

H 行 W 列のグリッドがあり、グリッドの各マスは赤色あるいは緑色に塗られています。

グリッドの上から i 行目、左から j 列目のマスをマス (i,j) と表記します。

マス (i,j) の色は文字 S_{i,j} で表され、S_{i,j} = . のときマス (i,j) は赤色、S_{i,j} = # のときマス (i,j) は緑色に塗られています。

グリッドにおいて、緑色に塗られたマスを頂点集合、隣り合った 2 つの緑色のマスを結ぶ辺全体を辺集合としたグラフにおける連結成分の個数を 緑の連結成分数 と呼びます。ただし、2 つのマス (x,y) と (x',y') が隣り合っているとは、|x-x'| + |y-y'| = 1 であることを指します。

赤色に塗られたマスを一様ランダムに 1 つ選び、緑色に塗り替えたとき、塗り替え後のグリッドの緑の連結成分数の期待値を \text{mod } 998244353 で出力してください。

「期待値を \text{mod } 998244353 で出力」とは

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、 R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ 1 つ存在することが証明できます。この R を出力してください。

制約

1 \leq H,W \leq 1000
S_{i,j} = . または S_{i,j} = #
S_{i,j} = . なる (i,j) が存在する。

入力

入力は以下の形式で標準入力から与えられる。

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

出力

答えを出力せよ。

入力例 1

3 3
##.
#.#
#..

出力例 1

499122178

マス (1,3) を緑色に塗り替えたとき、緑の連結成分数は 1 となります。

マス (2,2) を緑色に塗り替えたとき、緑の連結成分数は 1 となります。

マス (3,2) を緑色に塗り替えたとき、緑の連結成分数は 2 となります。

マス (3,3) を緑色に塗り替えたとき、緑の連結成分数は 2 となります。

よって、赤色に塗られたマスを一様ランダムに 1 つ選び、緑色に塗り替えた後の緑の連結成分数の期待値は (1+1+2+2)/4 = 3/2 となります。

入力例 2

4 5
..#..
.###.
#####
..#..

出力例 2

598946613

入力例 3

3 4
#...
.#.#
..##

出力例 3

285212675

Score : 450 points

Problem Statement

This problem has a similar setting to Problem G. Differences in the problem statement are indicated in red.

There is a grid with H rows and W columns, where each cell is painted red or green.

Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.

The color of cell (i,j) is represented by the character S_{i,j}, where S_{i,j} = . means cell (i,j) is red, and S_{i,j} = # means cell (i,j) is green.

The number of green connected components in the grid is the number of connected components in the graph with the vertex set being the green cells and the edge set being the edges connecting two adjacent green cells. Here, two cells (x,y) and (x',y') are considered adjacent when |x-x'| + |y-y'| = 1.

Consider choosing one red cell uniformly at random and repainting it green. Print the expected value of the number of green connected components in the grid after repainting, modulo 998244353.

What does "print the expected value modulo 998244353" mean?

It can be proved that the sought expected value is always rational. Furthermore, the constraints of this problem guarantee that if that value is expressed as \frac{P}{Q} using two coprime integers P and Q, there is exactly one integer R such that R \times Q \equiv P \pmod{998244353} and 0 \leq R < 998244353. Print this R.

Constraints

1 \leq H,W \leq 1000
S_{i,j} = . or S_{i,j} = #.
There is at least one (i,j) such that S_{i,j} = ..

Input

The input is given from Standard Input in the following format:

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

Output

Print the answer.

Sample Input 1

3 3
##.
#.#
#..

Sample Output 1

499122178

If cell (1,3) is repainted green, the number of green connected components becomes 1.

If cell (2,2) is repainted green, the number of green connected components becomes 1.

If cell (3,2) is repainted green, the number of green connected components becomes 2.

If cell (3,3) is repainted green, the number of green connected components becomes 2.

Therefore, the expected value of the number of green connected components after choosing one red cell uniformly at random and repainting it green is (1+1+2+2)/4 = 3/2.

Sample Input 2

4 5
..#..
.###.
#####
..#..

Sample Output 2

598946613

Sample Input 3

3 4
#...
.#.#
..##

Sample Output 3

285212675

I - Two Strings

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

長さ N の英小文字からなる文字列 S,T が与えられます。

文字列 X と整数 i に対し、f(X,i) を X に対して以下の操作を i 回行い得られる文字列とします。

X の先頭の文字を削除し、同じ文字を X の末尾に挿入する。

0 \le i,j \le N-1 を満たす正整数の組 (i,j) のうち、辞書順で f(S,i) が f(T,j) より小さいか同じであるものの個数を求めてください。

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 S, T の大小を判定するアルゴリズムを以下に説明します。

以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

S, T のうち長さが大きくない方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、S_j が T_j よりアルファベット順で小さい場合は S \lt T 、そうでない場合は S \gt T と決定して、アルゴリズムを終了します。
S_i \neq T_i である i が存在しない場合、S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

1 \le N \le 2 \times 10^5
S,T は英小文字からなる長さ N の文字列
N は整数

入力

入力は以下の形式で標準入力から与えられる。

N
S
T

出力

答えを出力せよ。

入力例 1

3
adb
cab

出力例 1

条件を満たす (i,j) の組は (0,0),(0,2),(2,0),(2,2) の 4 個があります。

(i,j)=(1,2) は、f(S,i)=dba,f(T,j)=bca であるため条件を満たしません。

入力例 2

10
wsiuhwijsl
pwqoketvun

出力例 2

Score : 500 points

Problem Statement

You are given strings S and T of length N each, consisting of lowercase English letters.

For a string X and an integer i, let f(X,i) be the string obtained by performing on X the following operation i times:

Remove the first character of X and append the same character to the end of X.

Find the number of integer pairs (i,j) satisfying 0 \le i,j \le N-1 such that f(S,i) is lexicographically smaller than or equal to f(T,j).

What is the lexicographical order?

Simply put, the lexicographical order is the order in which the words are arranged in a dictionary. Let us define it formally by describing an algorithm of finding the ordering of two distinct strings S and T consisting of lowercase English letters.

Here, we denote "the i-th character of a string S" by S_i. Also, we write S \lt T and S \gt T if S is lexicographically smaller and larger than T, respectively.

Let L be the smallest of the lengths of S and T. For i=1,2,\dots,L, we check if S_i equals T_i.
If there is an i such that S_i \neq T_i, let j be the smallest such i. Comparing S_j and T_j, we terminate the algorithm by determining that S \lt T if S_j is smaller than T_j in the alphabetical order, and that S \gt T otherwise.
If there is no i such that S_i \neq T_i, comparing the lengths of S and T, we terminate the algorithm by determining that S \lt T if S is shorter than T, and that S \gt T otherwise.

Constraints

1 \le N \le 2 \times 10^5
S and T are strings of length N each, consisting of lowercase English letters.
N is an integer.

Input

The input is given from Standard Input in the following format:

N
S
T

Output

Print the answer.

Sample Input 1

3
adb
cab

Sample Output 1

There are 4 pairs of (i, j) satisfying the conditions: (0,0),(0,2),(2,0), and (2,2).

(i,j)=(1,2) does not satisfy the conditions because f(S,i)=dba and f(T,j)=bca.

Sample Input 2

10
wsiuhwijsl
pwqoketvun