AtCoder Daily Training MEDIUM 2025/10/14 15:30start

C - カップリング選抜

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

アイドルグループ Bit♡Beat では、新曲のカップリングとしてメンバーの中から 2 人のユニット（選抜）を組むことになりました。

グループには N 人のメンバーがおり、それぞれのメンバーにスキル値が定まっています。 i 人目のメンバー (1\le i\le N) のスキル値は A_i です。

プロデューサーであるあなたは、スキル値の合計が ちょうど S になるような 2 人のメンバーの選び方を探しています。

スキル値の合計がちょうど S になるような 2 人のメンバーの選び方が何通りあるか求めてください。

制約

2\le N\le 5\times 10^5
1\le S \le 10^9
1\le A_i\le 10^9
入力される値は全て整数

入力

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

N S
A_1 A_2 \ldots A_N

出力

スキル値の合計がちょうど S になるような 2 人のメンバーの選び方が何通りあるか出力せよ。

入力例 1

5 11
5 6 9 2 2

出力例 1

1 人目と 2 人目がユニットを組むと、スキル値の合計は 5+6=11 となります。

このほかにも、 3 人目と 4 人目、3 人目と 5 人目がユニットを組んでも条件を満たします。

条件を満たす 2 人のメンバーの選び方は 3 通りであるため、 3 を出力してください。

入力例 2

10 1000000000
1 1 1 1 1 1 1 1 1 1

出力例 2

条件を満たす 2 人のメンバーの選び方が存在しない場合もあります。

入力例 3

6 14
7 7 7 7 7 7

出力例 3

入力例 4

15 8
3 4 10 9 1 1 1 7 8 9 9 3 8 9 7

出力例 4

D - cat

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

英小文字からなる N 個の文字列 S_1, S_2, \ldots, S_N が与えられます。ここで、文字列の長さはそれぞれ相異なります。

これらの文字列を長さの昇順に並べ替え、この順に結合して得られる文字列を求めてください。

制約

2 \leq N \leq 50
N は整数
S_i は長さ 1 以上 50 以下の英小文字からなる文字列
i \neq j のとき S_i と S_j の長さは異なる

入力

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

N
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。

入力例 1

3
tc
oder
a

出力例 1

atcoder

( tc, oder, a ) を文字列の長さの昇順に並べ替えると ( a, tc, oder ) となります。これらの文字列を順に結合すると文字列 atcoder が得られます。

入力例 2

4
cat
enate
on
c

出力例 2

concatenate

Score : 200 points

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N, each consisting of lowercase English letters. The lengths of these strings are all distinct.

Sort these strings in ascending order of length, and then concatenate them in that order to form a single string.

Constraints

2 \leq N \leq 50
N is an integer.
Each S_i is a string consisting of lowercase English letters with length between 1 and 50, inclusive.
If i \neq j, the length of S_i is different from the length of S_j.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the answer.

Sample Input 1

3
tc
oder
a

Sample Output 1

atcoder

When we sort (tc, oder, a) in ascending order of length, we get (a, tc, oder). Concatenating them in this order yields the string atcoder.

Sample Input 2

4
cat
enate
on
c

Sample Output 2

concatenate

E - 1111gal password

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

整数 N が与えられるので、以下の条件を全て満たす整数 X の個数を 998244353 で割った余りを求めてください。

N 桁の正整数である。
X の各桁を上の位から順に X_1,X_2,\dots,X_N とする。このとき以下の条件を全て満たす。
- 全ての整数 1 \le i \le N に対して、 1 \le X_i \le 9
- 全ての整数 1 \le i \le N-1 に対して、 |X_i-X_{i+1}| \le 1

制約

N は整数
2 \le N \le 10^6

入力

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

出力

答えを整数として出力せよ。

入力例 1

出力例 1

4 桁の整数として、例えば 1111,1234,7878,6545 が問題文中の条件を満たします。

入力例 2

出力例 2

入力例 3

出力例 3

248860093

998244353 で割った余りを求めることに注意してください。

Score : 300 points

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

X is an N-digit positive integer.
Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
- 1 \le X_i \le 9 for all integers 1 \le i \le N;
- |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

N is an integer.
2 \le N \le 10^6

Input

Input is given from Standard Input in the following format:

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

F - Neo-lexicographic Ordering

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

AtCoder 王国を治める高橋君は、英小文字のアルファベット順を変更することにしました。

新たなアルファベット順はa , b , \ldots, z を並べ替えて得られる文字列 X を用いて表されます。X の i \, (1 \leq i \leq 26) 文字目は、新たな順番において i 番目に小さい英小文字を表します。

AtCoder 王国には N 人の国民がおり、それぞれの国民の名前は S_1, S_2, \dots, S_N です。ここで、S_i \, (1 \leq i \leq N) は英小文字からなります。
これらの名前を、高橋君の定めたアルファベット順に基づく辞書順に従って並べ替えてください。

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 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 と決定して、アルゴリズムを終了します。

制約

X は a , b , \ldots, z を並べ替えて得られる
2 \leq N \leq 50000
N は整数
1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)
S_i は英小文字からなる (1 \leq i \leq N)
S_i \neq S_j (1 \leq i \lt j \leq N)

入力

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

X
N
S_1
S_2
\vdots
S_N

出力

N 行出力せよ。i \, (1 \leq i \leq N) 行目には、高橋君の定めたアルファベット順に基づく辞書順に従って国民の名前を並べ替えたとき、i 番目に小さいものを出力すること。

入力例 1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

出力例 1

bzz
bzy
abx
caa

高橋君が新たに設定したアルファベット順において、b は a より小さく、z は y より小さいです。そのため、国民の名前を辞書順に並べ替えると、小さい順に bzz , bzy , abx , caa となります。

入力例 2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

出力例 2

b
a
ac
ab
abc

Score : 300 points

Problem Statement

Takahashi, who governs the Kingdom of AtCoder, has decided to change the alphabetical order of English lowercase letters.

The new alphabetical order is represented by a string X, which is a permutation of a, b, \ldots, z. The i-th character of X (1 \leq i \leq 26) would be the i-th smallest English lowercase letter in the new order.

The kingdom has N citizens, whose names are S_1, S_2, \dots, S_N, where each S_i (1 \leq i \leq N) consists of lowercase English letters.
Sort these names lexicographically according to the alphabetical order decided by Takahashi.

What is the lexicographical order?

Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.

Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

Constraints

X is a permutation of a, b, \ldots, z.
2 \leq N \leq 50000
N is an integer.
1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)
S_i consists of lowercase English letters. (1 \leq i \leq N)
S_i \neq S_j (1 \leq i \lt j \leq N)

Input

Input is given from Standard Input in the following format:

X
N
S_1
S_2
\vdots
S_N

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain the i-th smallest name when the citizens' names are sorted according to the alphabetical order decided by Takahashi.

Sample Input 1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

Sample Output 1

bzz
bzy
abx
caa

In the new alphabetical order set by Takahashi, b is smaller than a and z is smaller than y. Thus, sorting the citizens' names lexicographically would result in bzz, bzy, abx, caa in ascending order.

Sample Input 2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

Sample Output 2

b
a
ac
ab
abc

G - XNOR Operation

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 425 点

問題文

この問題は G 問題の部分問題です。

0 と 1 からなる空でない文字列 S が次の条件を満たす時、S を美しい文字列と呼びます。

(条件) 次の一連の操作を S の長さが 1 になるまで行い、S に残った唯一の文字を 1 にすることができる。
1. 1 \leq i \leq |S| - 1 を満たす整数 i を自由に選ぶ。
2. 整数 x を次のように定義する。
  - S_i = 0 かつ S_{i+1}= 0 である場合、x = 1 とする。
  - S_i = 0 かつ S_{i+1}= 1 である場合、x = 0 とする。
  - S_i = 1 かつ S_{i+1}= 0 である場合、x = 0 とする。
  - S_i = 1 かつ S_{i+1}= 1 である場合、x = 1 とする。
3. S_i と S_{i+1} を取り除き、それらがあった場所に x を数字とみなしたものを 1 個挿入する。
  例えば S= 10101 に対して i=2 を選んで操作を行った場合、操作後の文字列は 1001 になる。

0 と 1 からなる長さ N の文字列 T があります。
T の部分文字列である美しい文字列の個数を求めてください。ただし、2 つの部分文字列が文字列として同じでも、取り出す位置が異なるならば別々に数えます。

部分文字列とは

S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、10 は 101 の部分文字列ですが、11 は 101 の部分文字列ではありません。

制約

1 \leq N \leq 2 \times 10^5
N は整数
T は 0 と 1 からなる長さ N の文字列

入力

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

N
T

出力

T の部分文字列である美しい文字列の個数を出力せよ。

入力例 1

3
110

出力例 1

T の 1 文字目から 2 文字目までを取り出してできる文字列 11 は美しい文字列です。なぜならば、i=1 として操作を行うと、操作後の文字列は 1 になるからです。
T の部分文字列である美しい文字列は次の 3 個です。

T の 1 文字目を取り出してできる文字列 1
T の 2 文字目を取り出してできる文字列 1
T の 1 文字目から 2 文字目までを取り出してできる文字列 11

入力例 2

4
0000

出力例 2

入力例 3

30
011011100101110111100010011010

出力例 3

Score : 425 points

Problem Statement

This problem is a subproblem of Problem G.

A non-empty string S consisting of 0 and 1 is called a beautiful string when it satisfies the following condition:

(Condition) You can perform the following sequence of operations until the length of S becomes 1 and make the only character remaining in S be 1.
1. Choose any integer i satisfying 1 \leq i \leq |S| - 1.
2. Define an integer x as follows:
  - If S_i = 0 and S_{i+1} = 0, let x = 1.
  - If S_i = 0 and S_{i+1} = 1, let x = 0.
  - If S_i = 1 and S_{i+1} = 0, let x = 0.
  - If S_i = 1 and S_{i+1} = 1, let x = 1.
3. Remove S_i and S_{i+1}, and insert the digit corresponding to x in their place.
  For example, if S= 10101 and you choose i=2, the string after the operation is 1001.

You are given a string T of length N consisting of 0 and 1.
Find the number of beautiful strings that are substrings of T. Even if two substrings are identical as strings, count them separately if they are taken from different positions.

What are substrings?

A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, 10 is a substring of 101, but 11 is not a substring of 101.

Constraints

1 \leq N \leq 2 \times 10^5
N is an integer.
T is a string of length N consisting of 0 and 1.

Input

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

N
T

Output

Print the number of beautiful strings that are substrings of T.

Sample Input 1

3
110

Sample Output 1

The string 11 obtained by taking the 1st through 2nd characters of T is a beautiful string, because if you choose i=1 and perform the operation, the string becomes 1. The beautiful strings that are substrings of T are the following three strings:

The string 1 obtained by taking the 1st character of T.
The string 1 obtained by taking the 2nd character of T.
The string 11 obtained by taking the 1st through 2nd characters of T.

Sample Input 2

4
0000

Sample Output 2

Sample Input 3

30
011011100101110111100010011010