AtCoder Daily Training EASY 2026/08/10 18:00start

A - Count .

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字からなる文字列 S が与えられます。

ここで、英小文字に含まれるドットの個数を以下のようにして定めます。

英小文字が i または j であるとき : 1 個
英小文字が i, j のいずれでもないとき : 0 個

S のすべての文字に対するドットの個数の和を求めてください。

制約

S は長さ 1 以上 10 以下の英小文字からなる文字列

入力

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

出力

答えを出力せよ。

入力例 1

aiiaj

出力例 1

a, i, i, a, j に含まれるドットの個数はそれぞれ 0, 1, 1, 0, 1 です。

0 + 1 + 1 + 0 + 1 = 3 であるため、3 を出力します。

入力例 2

abcedfgh

出力例 2

入力例 3

jjjjjj

出力例 3

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters.

Here, we define the number of dots in a lowercase English letter as follows:

If the lowercase English letter is i or j: 1 dot
If the lowercase English letter is neither i nor j: 0 dots

Find the sum of the numbers of dots over all characters in S.

Constraints

S is a string consisting of lowercase English letters with length between 1 and 10, inclusive.

Input

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

Output

Print the answer.

Sample Input 1

aiiaj

Sample Output 1

The numbers of dots in a, i, i, a, j are 0, 1, 1, 0, 1, respectively.

We have 0 + 1 + 1 + 0 + 1 = 3, so print 3.

Sample Input 2

abcedfgh

Sample Output 2

Sample Input 3

jjjjjj

Sample Output 3

B - Count Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

文字列が N 個与えられます。

i 番目 (1\leq i\leq N) に与えられる文字列 S _ i は Takahashi か Aoki のどちらかと等しいです。

S _ i が Takahashi と等しい i がいくつあるか求めてください。

制約

1\leq N\leq 100
N は整数
S _ i は Takahashi か Aoki のいずれか (1\leq i\leq N)

入力

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

N
S _ 1
S _ 2
\vdots
S _ N

出力

S _ i が Takahashi と等しい i の個数を整数として一行に出力せよ。

入力例 1

3
Aoki
Takahashi
Takahashi

出力例 1

S _ 2,S _ 3 の 2 つが Takahashi と等しく、S _ 1 はそうではありません。

よって、2 を出力してください。

入力例 2

2
Aoki
Aoki

出力例 2

Takahashi と等しい S _ i が存在しないこともあります。

入力例 3

20
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi

出力例 3

Score : 100 points

Problem Statement

You are given N strings.

The i-th string S_i (1 \leq i \leq N) is either Takahashi or Aoki.

How many i are there such that S_i is equal to Takahashi?

Constraints

1 \leq N \leq 100
N is an integer.
Each S_i is Takahashi or Aoki. (1 \leq i \leq N)

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the count of i such that S_i is equal to Takahashi as an integer in a single line.

Sample Input 1

3
Aoki
Takahashi
Takahashi

Sample Output 1

S_2 and S_3 are equal to Takahashi, while S_1 is not.

Therefore, print 2.

Sample Input 2

2
Aoki
Aoki

Sample Output 2

It is possible that no S_i is equal to Takahashi.

Sample Input 3

20
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi

Sample Output 3

C - Piano 3

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は、横一列に並んだ 100 個の鍵盤からなるピアノを持っています。このピアノの左から i 個目の鍵盤のことを鍵盤 i と呼びます。

高橋君は今から N 回にわたってこのピアノの鍵盤を一つずつ押すことでとある曲を演奏します。 i 回目に押す鍵盤は鍵盤 A_i であり、それを押す手は S_i= L のとき左手、S_i= R のとき右手です。

演奏を始める前、高橋君は両手をそれぞれ好きな鍵盤の上に置くことができ、この時点での疲労度は 0 です。演奏中、片方の手を鍵盤 x の上から鍵盤 y の上へと動かすと疲労度が |y-x| 増加します（逆に、手の移動以外で疲労度が増加することはありません）。なお、ある手である鍵盤を押すためには、その手がその鍵盤の上に置かれている必要があります。

演奏が終了した時点での疲労度は最小でいくつになるか求めてください。

制約

1\leq N \leq 100
1\leq A_i \leq 100
N,A_i は整数
S_i は L または R

入力

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

出力

演奏が終了した時点での疲労度の最小値を出力せよ。

入力例 1

4
3 L
6 R
9 L
1 R

出力例 1

例えば以下のように演奏することができます。

最初、左手を鍵盤 3 の上に、右手を鍵盤 6 の上に置いておく。
左手で鍵盤 3 を押す。
右手で鍵盤 6 を押す。
左手を鍵盤 3 の上から鍵盤 9 の上へと動かす。疲労度が |9-3|=6 増加する。
右手を鍵盤 6 の上から鍵盤 1 の上へと動かす。疲労度が |1-6|=5 増加する。
左手で鍵盤 9 を押す。
右手で鍵盤 1 を押す。

このとき、演奏が終了した時点での疲労度は 6+5=11 であり、これが最小です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 200 points

Problem Statement

Takahashi has a piano with 100 keys arranged in a row. The i-th key from the left is called key i.

He will play music by pressing N keys one by one. For the i-th press, he will press key A_i, using his left hand if S_i= L, and his right hand if S_i= R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key x to key y, the fatigue level increases by |y-x| (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

1 \leq N \leq 100
1 \leq A_i \leq 100
N and A_i are integers.
S_i is L or R.

Input

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

Output

Print the minimum fatigue level at the end of the performance.

Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

For example, the performance can be done as follows:

Initially, place the left hand on key 3 and the right hand on key 6.
Press key 3 with the left hand.
Press key 6 with the right hand.
Move the left hand from key 3 to key 9. The fatigue level increases by |9-3| = 6.
Move the right hand from key 6 to key 1. The fatigue level increases by |1-6| = 5.
Press key 9 with the left hand.
Press key 1 with the right hand.

In this case, the fatigue level at the end of the performance is 6+5 = 11, which is the minimum possible.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

D - Personnel Change

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君の勤めている会社には N 人の社員がおり、各社員には 1,2,\dots,N の社員番号が割り当てられています。社内には M 個の部門があり、部門 1,2,\dots,M と呼ばれています。

社員番号 i の社員は、今期は部門 A_i に所属しており、来期は部門 B_i に所属します。

部門 1,2,\dots,M それぞれに対して、来期の所属人数から今期の所属人数を引いた値を求めてください。

制約

1 \leq N \leq 100
1 \leq M \leq 100
1 \leq A_i \leq M
1 \leq B_i \leq M
入力はすべて整数

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

M 行出力せよ。j 行目には部門 j についての答えを出力せよ。

入力例 1

出力例 1

1
-1
-1
1

部門 1 について、今期は社員番号 1 の 1 人が所属し、来期は社員番号 2,3 の 2 人が所属します。
部門 2 について、今期は社員番号 2,4,5 の 3 人が所属し、来期は社員番号 1,4 の 2 人が所属します。
部門 3 について、今期は社員番号 3 の 1 人が所属し、来期は誰も所属しません。
部門 4 について、今期は誰も所属せず、来期は社員番号 5 の 1 人が所属します。

入力例 2

出力例 2

Score : 200 points

Problem Statement

The company where Takahashi works has N employees, each assigned an employee number from 1, 2, \dots, N. There are M departments in the company, called departments 1, 2, \dots, M.

Employee i belongs to department A_i this term and will belong to department B_i next term.

For each of departments 1, 2, \dots, M, find the number of members next term minus the number of members this term.

Constraints

1 \leq N \leq 100
1 \leq M \leq 100
1 \leq A_i \leq M
1 \leq B_i \leq M
All input values are integers.

Input

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

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Output M lines. The j-th line should contain the answer for department j.

Sample Input 1

Sample Output 1

1
-1
-1
1

For department 1: this term, one employee (employee number 1) belongs; next term, two employees (employee numbers 2, 3) belong.
For department 2: this term, three employees (employee numbers 2, 4, 5) belong; next term, two employees (employee numbers 1, 4) belong.
For department 3: this term, one employee (employee number 3) belongs; next term, no one belongs.
For department 4: this term, no one belongs; next term, one employee (employee number 5) belongs.

Sample Input 2

Sample Output 2

E - Swiss-System Tournament

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1 から 2N の番号がついた 2N 人でじゃんけん大会をします。

大会は M ラウンドからなり、各ラウンドは、全ての人が 1 度ずつ参加するような 1 対 1 の N 試合からなります。

i=0,1,\ldots,M について、i ラウンド目の終了時点での順位を次のように決めます。

i ラウンド目までの勝数が多い方が上位
i ラウンド目までの勝数が同じときは、番号が小さい方が上位

また、i=1,\ldots,M について、i ラウンド目の各試合の組み合わせを次のように決めます。

各 k=1,2,\ldots,N について、i-1 ラウンド目終了時点の順位が 2k-1 位の人と 2k 位の人が試合をする

各試合では、対戦する 2 人がそれぞれ 1 度だけ手を出し、勝ち・負け・引き分けのいずれかの結果が発生します。

未来予知ができる高橋君は、人 i が j ラウンド目の試合で出す手が A_{i,j} であることを知っています。
A_{i,j} は G, C, P のいずれかであり、それぞれグー、チョキ、パーを表します。

M ラウンド目終了時点の順位を求めてください。

じゃんけんのルール

じゃんけんの結果は、2 人の出した手に応じて次のように決まります。

一方がグーで他方がチョキのとき、グーを出した人が勝ち、チョキを出した人は負け
一方がチョキで他方がパーのとき、チョキを出した人が勝ち、パーを出した人は負け
一方がパーで他方がグーのとき、パーを出した人が勝ち、グーを出した人は負け
両者が同じ手を出したとき、引き分け

制約

1 \leq N \leq 50
1 \leq M \leq 100
A_{i,j} は G, C, P のいずれか

入力

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

N M
A_{1,1}A_{1,2}\ldots A_{1,M}
A_{2,1}A_{2,2}\ldots A_{2,M}
\vdots
A_{2N,1}A_{2N,2}\ldots A_{2N,M}

出力

2N 行出力せよ。

i 行目には、M ラウンド目終了時点での順位が i 位である人の番号を出力せよ。

入力例 1

2 3
GCP
PPP
CCC
PPC

出力例 1

1 ラウンド目では人 1 と 2、3 と 4 がそれぞれ試合をし、前者の試合は人 2 が、後者の試合は人 3 が勝ちます。
2 ラウンド目では人 2 と 3、1 と 4 がそれぞれ試合をし、前者の試合は人 3 が、後者の試合は人 1 が勝ちます。
3 ラウンド目では人 3 と 1、2 と 4 がそれぞれ試合をし、前者の試合は人 3 が、後者の試合は人 4 が勝ちます。
よって最終的な順位は、上位から順に人 3,1,2,4 となります。

入力例 2

2 2
GC
PG
CG
PP

出力例 2

1 ラウンド目では人 1 と 2、3 と 4 がそれぞれ試合をし、前者の試合は人 2 が、後者の試合は人 3 が勝ちます。
2 ラウンド目では人 2 と 3、1 と 4 がそれぞれ試合をし、前者の試合は引き分け、後者の試合は人 1 が勝ちます。
よって最終的な順位は、上位から順に人 1,2,3,4 となります。

Score : 300 points

Problem Statement

2N players, with ID numbers 1 through 2N, will participate in a rock-scissors-paper contest.

The contest has M rounds. Each round has N one-on-one matches, where each player plays in one of them.

For each i=0, 1, \ldots, M, the players' ranks at the end of the i-th round are determined as follows.

A player with more wins in the first i rounds ranks higher.
Ties are broken by ID numbers: a player with a smaller ID number ranks higher.

Additionally, for each i=1, \ldots, M, the matches in the i-th round are arranged as follows.

For each k=1, 2, \ldots, N, a match is played between the players who rank (2k-1)-th and 2k-th at the end of the (i-1)-th round.

In each match, the two players play a hand just once, resulting in one player's win and the other's loss, or a draw.

Takahashi, who can foresee the future, knows that Player i will play A_{i, j} in their match in the j-th round, where A_{i,j} is G, C, or P.
Here, G stands for rock, C stands for scissors, and P stands for paper. (These derive from Japanese.)

Find the players' ranks at the end of the M-th round.

Rules of rock-scissors-paper

The result of a rock-scissors-paper match is determined as follows, based on the hands played by the two players.

If one player plays rock (G) and the other plays scissors (C), the player playing rock (G) wins.
If one player plays scissors (C) and the other plays paper (P), the player playing scissors (C) wins.
If one player plays paper (P) and the other plays rock (G), the player playing paper (P) wins.
If the players play the same hand, the match is drawn.

Constraints

1 \leq N \leq 50
1 \leq M \leq 100
A_{i,j} is G, C, or P.

Input

Input is given from Standard Input in the following format:

N M
A_{1,1}A_{1,2}\ldots A_{1,M}
A_{2,1}A_{2,2}\ldots A_{2,M}
\vdots
A_{2N,1}A_{2N,2}\ldots A_{2N,M}

Output

Print 2N lines.

The i-th line should contain the ID number of the player who ranks i-th at the end of the M-th round.

Sample Input 1

2 3
GCP
PPP
CCC
PPC

Sample Output 1

In the first round, matches are played between Players 1 and 2, and between Players 3 and 4. Player 2 wins the former, and Player 3 wins the latter.
In the second round, matches are played between Players 2 and 3, and between Players 1 and 4. Player 3 wins the former, and Player 1 wins the latter.
In the third round, matches are played between Players 3 and 1, and between Players 2 and 4. Player 3 wins the former, and Player 4 wins the latter.
Therefore, in the end, the players are ranked in the following order: 3,1,2,4, from highest to lowest.

Sample Input 2

2 2
GC
PG
CG
PP

Sample Output 2

In the first round, matches are played between Players 1 and 2, and between Players 3 and 4. Player 2 wins the former, and Player 3 wins the latter.
In the second round, matches are played between Players 2 and 3, and between Players 1 and 4. The former is drawn, and Player 1 wins the latter.
Therefore, in the end, the players are ranked in the following order: 1,2,3,4, from highest to lowest.