AtCoder Daily Training MEDIUM 2025/01/16 18:30start

C - Unvarnished Report

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

配点 : 200 点

問題文

キーエンスでは良いことも悪いこともありのままに報告するという文化があります。
そこで、報告内容が元の文章のありのままであるかを確認したいです。

英小文字のみからなる文字列 S, T が与えられます。
S と T が等しいならば 0 を、そうでないならば異なっている文字のうち先頭のものが何文字目かを出力してください。
ただし、S,T の一方にのみ i 文字目が存在するときも、i 文字目は異なっているとみなすものとします。

より厳密には、S と T が等しくないならば次の条件のうちいずれかをみたす最小の整数 i を出力してください。

1\leq i\leq |S| かつ 1\leq i\leq |T| かつ S_i\neq T_i
|S|< i\leq |T|
|T|< i\leq |S|

ただし、|S|,|T| でそれぞれ S,T の長さを、S_i,T_i でそれぞれ S,T の i 文字目を表します。

制約

S,T は英小文字のみからなる長さ 1 以上 100 以下の文字列

入力

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

S
T

出力

S と T が等しいならば 0 を、そうでないならば異なっている文字のうち先頭のものが何文字目かを出力せよ。

入力例 1

abcde
abedc

出力例 1

S=abcde, T=abedc です。
S と T は 1,2 文字目は等しく、3 文字目が異なるため、 3 を出力します。

入力例 2

abcde
abcdefg

出力例 2

S=abcde, T=abcdefg です。
S と T は 5 文字目まで等しく、T にのみ 6 文字目が存在するため、6 を出力します。

入力例 3

keyence
keyence

出力例 3

S と T は等しいため、 0 を出力します。

Score : 200 points

Problem Statement

KEYENCE has a culture of reporting things as they are, whether good or bad.
So we want to check whether the reported content is exactly the same as the original text.

You are given two strings S and T, consisting of lowercase English letters.
If S and T are equal, print 0; otherwise, print the position of the first character where they differ.
Here, if the i-th character exists in only one of S and T, consider that the i-th characters are different.

More precisely, if S and T are not equal, print the smallest integer i satisfying one of the following conditions:

1\leq i\leq |S|, 1\leq i\leq |T|, and S_i\neq T_i.
|S| < i \leq |T|.
|T| < i \leq |S|.

Here, |S| and |T| denote the lengths of S and T, respectively, and S_i and T_i denote the i-th characters of S and T, respectively.

Constraints

S and T are strings of length between 1 and 100, inclusive, consisting of lowercase English letters.

Input

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

S
T

Output

If S and T are equal, print 0; otherwise, print the position of the first character where they differ.

Sample Input 1

abcde
abedc

Sample Output 1

We have S= abcde and T= abedc.
S and T have the same first and second characters, but differ at the third character, so print 3.

Sample Input 2

abcde
abcdefg

Sample Output 2

We have S= abcde and T= abcdefg.
S and T are equal up to the fifth character, but only T has a sixth character, so print 6.

Sample Input 3

keyence
keyence

Sample Output 3

S and T are equal, so print 0.

D - Spot the Difference

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

配点 : 150 点

問題文

縦 N マス、横 N マスのグリッドが 2 個与えられます。それぞれグリッド A, グリッド B と呼びます。
グリッドの各マスには英小文字が書かれています。
グリッド A の上から i 行目、左から j 列目に書かれている文字は A_{i, j} です。
グリッド B の上から i 行目、左から j 列目に書かれている文字は B_{i, j} です。

2 つのグリッドは 1 ヵ所だけ書かれている文字が異なります。すなわち、A_{i, j} \neq B_{i, j} である N 以下の正整数の組 (i, j) はちょうど 1 個存在します。この (i, j) を求めてください。

制約

1 \leq N \leq 100
A_{i, j}, B_{i, j} は全て英小文字
A_{i, j} \neq B_{i, j} である (i, j) がちょうど 1 個存在する

入力

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}
B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

出力

A_{i, j} \neq B_{i, j} である N 以下の正整数の組を (i, j) とする。この時、(i, j) を以下の形式で出力せよ。

i j

入力例 1

3
abc
def
ghi
abc
bef
ghi

出力例 1

2 1

A_{2, 1} = d、B_{2, 1} = b なので A_{2, 1} \neq B_{2, 1} が成り立つため、(i, j) = (2, 1) は問題文の条件を満たします。

入力例 2

1
f
q

出力例 2

1 1

入力例 3

10
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehfk
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehok
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj

出力例 3

5 9

Score: 150 points

Problem Statement

You are given two grids, each with N rows and N columns, referred to as grid A and grid B.
Each cell in the grids contains a lowercase English letter.
The character at the i-th row and j-th column of grid A is A_{i, j}.
The character at the i-th row and j-th column of grid B is B_{i, j}.

The two grids differ in exactly one cell. That is, there exists exactly one pair (i, j) of positive integers not greater than N such that A_{i, j} \neq B_{i, j}. Find this (i, j).

Constraints

1 \leq N \leq 100
A_{i, j} and B_{i, j} are all lowercase English letters.
There exists exactly one pair (i, j) such that A_{i, j} \neq B_{i, j}.

Input

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}
B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

Output

Let (i, j) be the pair of positive integers not greater than N such that A_{i, j} \neq B_{i, j}. Print (i, j) in the following format:

i j

Sample Input 1

3
abc
def
ghi
abc
bef
ghi

Sample Output 1

2 1

From A_{2, 1} = d and B_{2, 1} = b, we have A_{2, 1} \neq B_{2, 1}, so (i, j) = (2, 1) satisfies the condition in the problem statement.

Sample Input 2

1
f
q

Sample Output 2

1 1

Sample Input 3

10
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehfk
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehok
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj

Sample Output 3

5 9

E - Sort

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

配点 : 300 点

問題文

(1,2,\ldots,N) の並び替えである数列 A=(A_1,\ldots,A_N) が与えられます。
次の操作を 0 回以上 N-1 回以下行うことで、A を (1,2,\ldots,N) にしてください。

操作：1\leq i < j \leq N を満たす整数の組 (i,j) を自由に選ぶ。A の i 番目と j 番目の要素を入れ替える。

なお、制約の条件下で必ず A を (1,2,\ldots,N) にできることが証明できます。

制約

2 \leq N \leq 2\times 10^5
(A_1,\ldots,A_N) は (1,2,\ldots,N) の並び替えである
入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

操作回数を K として、K+1 行出力せよ。
1 行目には K を出力せよ。
l+1 行目 (1\leq l \leq K) には l 回目の操作で選ぶ整数 i,j を空白区切りで出力せよ。
問題文中の条件を満たすどのような出力も正解とみなされる。

入力例 1

5
3 4 1 2 5

出力例 1

2
1 3
2 4

操作により数列は次のように変化します。

最初 A=(3,4,1,2,5) である。
1 回目の操作で 1 番目の要素と 3 番目の要素を入れ替える。A=(1,4,3,2,5) になる。
2 回目の操作で 2 番目の要素と 4 番目の要素を入れ替える。A=(1,2,3,4,5) になる。

この他、次のような出力でも正解とみなされます。

入力例 2

4
1 2 3 4

出力例 2

入力例 3

3
3 1 2

出力例 3

2
1 2
2 3

Score: 300 points

Problem Statement

You are given a permutation A=(A_1,\ldots,A_N) of (1,2,\ldots,N).
Transform A into (1,2,\ldots,N) by performing the following operation between 0 and N-1 times, inclusive:

Operation: Choose any pair of integers (i,j) such that 1\leq i < j \leq N. Swap the elements at the i-th and j-th positions of A.

It can be proved that under the given constraints, it is always possible to transform A into (1,2,\ldots,N).

Constraints

2 \leq N \leq 2\times 10^5
(A_1,\ldots,A_N) is a permutation of (1,2,\ldots,N).
All input values are integers.

Input

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

N
A_1 \ldots A_N

Output

Let K be the number of operations. Print K+1 lines.
The first line should contain K.
The (l+1)-th line (1\leq l \leq K) should contain the integers i and j chosen for the l-th operation, separated by a space.
Any output that satisfies the conditions in the problem statement will be considered correct.

Sample Input 1

5
3 4 1 2 5

Sample Output 1

2
1 3
2 4

The operations change the sequence as follows:

Initially, A=(3,4,1,2,5).
The first operation swaps the first and third elements, making A=(1,4,3,2,5).
The second operation swaps the second and fourth elements, making A=(1,2,3,4,5).

Other outputs such as the following are also considered correct:

Sample Input 2

4
1 2 3 4

Sample Output 2

Sample Input 3

3
3 1 2

Sample Output 3

2
1 2
2 3

F - Extra Character

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

配点 : 300 点

問題文

文字列 S,T が与えられます。S は英小文字からなり、T は S に英小文字を 1 つ挿入して作られたことがわかっています。

挿入された文字は T の先頭から何番目の文字であるか求めてください。
複数の候補が考えられる場合はいずれか 1 つを求めてください。

制約

1 \leq |S| \leq 5\times 10^5
S は英小文字からなる
T は S に英小文字を 1 つ挿入して作られた文字列である

入力

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

S
T

出力

答えを出力せよ。なお、答えが複数考えられる場合はどれを出力しても正解となる。

入力例 1

atcoder
atcorder

出力例 1

T の先頭から 5 番目の文字 r が挿入された文字です。

入力例 2

million
milllion

出力例 2

T の先頭から 3,4,5 番目の文字のいずれかが挿入された文字です。
よって、3,4,5 のいずれかを出力すると正解となります。

入力例 3

vvwvw
vvvwvw

出力例 3

Score : 300 points

Problem Statement

You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.

Find the position of the inserted character in T.
If there are multiple candidates, find any of them.

Constraints

1 \leq |S| \leq 5\times 10^5
S consists of lowercase English letters.
T is obtained by inserting a lowercase English letter into S.

Input

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

S
T

Output

Print an integer i, representing that the inserted character is the i-th character from the beginning of T. If there are multiple possible answers, printing any of them is accepted.

Sample Input 1

atcoder
atcorder

Sample Output 1

The 5-th character from the beginning of T, r, is inserted.

Sample Input 2

million
milllion

Sample Output 2

One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.

Sample Input 3

vvwvw
vvvwvw

Sample Output 3

G - LR insertion

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

配点 : 400 点

問題文

1 個の 0 のみからなる数列 A=(0) があります。
また、L と R のみからなる長さ N の文字列 S=s_1s_2\ldots s_N が与えられます。

i=1,2,\ldots ,N の順番で、次の操作を行います。

s_i が L のとき、A 内にある i-1 のすぐ左に i を挿入する
s_i が R のとき、A 内にある i-1 のすぐ右に i を挿入する

最終的な A を求めてください。

制約

1\leq N \leq 5\times 10^5
N は整数である
|S| = N
s_i は L か R のいずれかである

入力

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

N
S

出力

最終的な A を空白区切りで出力せよ。

入力例 1

5
LRRLR

出力例 1

1 2 4 5 3 0

はじめ、A=(0) です。
s_1 が L なので、A=(1,0) となります。
s_2 が R なので、A=(1,2,0) となります。
s_3 が R なので、A=(1,2,3,0) となります。
s_4 が L なので、A=(1,2,4,3,0) となります。
s_5 が R なので、A=(1,2,4,5,3,0) となります。

入力例 2

7
LLLLLLL

出力例 2

7 6 5 4 3 2 1 0

Score : 400 points

Problem Statement

There is a sequence that contains one 0, A=(0).
Additionally, you are given a string of length N, S=s_1s_2\ldots s_N, consisting of L and R.

For each i=1, 2, \ldots, N in this order, the following will be done.

If s_i is L, insert i to the immediate left of i-1 in A.
If s_i is R, insert i to the immediate right of i-1 in A.

Find the final contents of A.

Constraints

1\leq N \leq 5\times 10^5
N is an integer.
|S| = N
s_i is L or R.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the final contents of A, separated by spaces.

Sample Input 1

5
LRRLR

Sample Output 1

1 2 4 5 3 0

Initially, A=(0).
S_1 is L, which makes it A=(1,0).
S_2 is R, which makes it A=(1,2,0).
S_3 is R, which makes it A=(1,2,3,0).
S_4 is L, which makes it A=(1,2,4,3,0).
S_5 is R, which makes it A=(1,2,4,5,3,0).

Sample Input 2

7
LLLLLLL

Sample Output 2

7 6 5 4 3 2 1 0