A - First Grid

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

配点 : 100 点

問題文

縦 2 行、横 2 列のグリッド(各マスが正方形のマス目)があります。
このグリッドは、各マスが黒か白であり、少なくとも 2 つの黒マスを含みます。
各マスの色の情報は文字列 S_1,S_2 として、以下の形式で与えられます。

  • 文字列 S_i の j 文字目が # であれば上から i マス目、左から j マス目は黒
  • 文字列 S_i の j 文字目が . であれば上から i マス目、左から j マス目は白

2 つの異なる黒マス同士が辺で接している時、またその時に限りそれら 2 つの黒マスは直接行き来できます。
黒マスのみをいくつか通ることによって、どの 2 つの黒マス同士も(直接または間接的に)行き来できるかどうか判定してください。

制約

  • S_1,S_2 は # または . からなる 2 文字の文字列
  • S_1,S_2 に # が合計で 2 つ以上含まれる

入力

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

S_1
S_2

出力

どの 2 つの黒マス同士も行き来できるなら Yes 、そうでないなら No と出力せよ。

入力例 1

##
.#

出力例 1

Yes

左上の黒マスと右上の黒マス、右上の黒マスと右下の黒マスを直接行き来することができます。
これらの移動を用いてどの黒マスからどの黒マスへも行き来できるので、答えは Yes となります。

入力例 2

.#
#.

出力例 2

No

右上の黒マスと左下の黒マスを行き来することはできません。答えは No となります。

Score : 100 points

Problem Statement

We have a grid with 2 horizontal rows and 2 vertical columns.
Each of the squares is black or white, and there are at least 2 black squares.
The colors of the squares are given to you as strings S_1 and S_2, as follows.

  • If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left is black.
  • If the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is white.

You can travel between two different black squares if and only if they share a side.
Determine whether it is possible to travel from every black square to every black square (directly or indirectly) by only passing black squares.

Constraints

  • Each of S_1 and S_2 is a string with two characters consisting of # and ..
  • S_1 and S_2 have two or more #s in total.

Input

Input is given from Standard Input in the following format:

S_1
S_2

Output

If it is possible to travel from every black square to every black square, print Yes; otherwise, print No.

Sample Input 1

##
.#

Sample Output 1

Yes

It is possible to directly travel between the top-left and top-right black squares and between top-right and bottom-right squares.
These two moves enable us to travel from every black square to every black square, so the answer is Yes.

Sample Input 2

.#
#.

Sample Output 2

No

It is impossible to travel between the top-right and bottom-left black squares, so the answer is No.
B - Legendary Players

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

配点 : 100 点

問題文

AtCoder では、レーティング上位 10 人のハンドルネームには金色の冠が、上位 1 人のハンドルネームには白金色の冠が表示されます。

このコンテストが開始した時点で、アルゴリズム部門での上位 10 人に入っているプレイヤーのハンドルネームとレーティングは以下のようになっています。

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

上記のプレイヤーのハンドルネーム S が与えられるので、その人のレーティングを出力してください。

制約

  • S はアルゴリズム部門でレーティング上位 10 人に入っているプレイヤーのハンドルネームのいずれかと等しい。

入力

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

S

出力

対応するプレイヤーのレーティングを 1 行で出力せよ。

入力例 1

tourist

出力例 1

3858

このコンテストが開始した時点において、 tourist さんのアルゴリズム部門のレーティングは 3858 です。

入力例 2

semiexp

出力例 2

3481

このコンテストが開始した時点において、 semiexp さんのアルゴリズム部門のレーティングは 3481 です。

Score : 100 points

Problem Statement

In AtCoder, the top 10 rated players' usernames are displayed with a gold crown, and the top-rated player's username is displayed with a platinum crown.

At the start of this contest, the usernames and ratings of the top 10 rated players in the algorithm category are as follows:

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

You are given the username S of one of these players. Print that player's rating.

Constraints

  • S is equal to one of the usernames of the top 10 rated players in the algorithm category.

Input

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

S

Output

Print the rating of the corresponding player in one line.

Sample Input 1

tourist

Sample Output 1

3858

At the start of this contest, the rating of tourist in the algorithm category is 3858.

Sample Input 2

semiexp

Sample Output 2

3481

At the start of this contest, the rating of semiexp in the algorithm category is 3481.
C - Matrix Transposition

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

配点 : 200 点

問題文

H 行 W 列の行列 A が与えられます。
A の上から i 行目、左から j 列目の要素は A_{i,j} です。

ここで、W 行 H 列の行列 B を、上から i 行目、左から j 列目の要素が A_{j,i} と一致するような行列として定めます。
すなわち、B は A の転置行列です。

B を出力してください。

制約

  • 1\leq H,W \leq 10^5
  • H \times W \leq 10^5
  • 1 \leq A_{i,j} \leq 10^9
  • 入力は全て整数である

入力

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

H W
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}

出力

B を以下の形式で出力せよ。 

B_{1,1} B_{1,2} \ldots B_{1,H}
B_{2,1} B_{2,2} \ldots B_{2,H}
\vdots
B_{W,1} B_{W,2} \ldots B_{W,H}

入力例 1

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

出力例 1

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

たとえば A_{2,1}=4 なので、転置行列 B の上から 1 行目、左から 2 列目の要素は 4 になります。

入力例 2

2 2
1000000000 1000000000
1000000000 1000000000

出力例 2

1000000000 1000000000
1000000000 1000000000

Score : 200 points

Problem Statement

You are given an H-by-W matrix A.
The element at the i-th row from the top and j-th column from the left of A is A_{i,j}.

Let B be a W-by-H matrix whose element at the i-th row from the top and j-th column from the left equals A_{j, i}.
That is, B is the transpose of A.

Print B.

Constraints

  • 1\leq H,W \leq 10^5
  • H \times W \leq 10^5
  • 1 \leq A_{i,j} \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}

Output

Print B in the following format:

B_{1,1} B_{1,2} \ldots B_{1,H}
B_{2,1} B_{2,2} \ldots B_{2,H}
\vdots
B_{W,1} B_{W,2} \ldots B_{W,H}

Sample Input 1

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

Sample Output 1

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

For example, we have A_{2,1}=4, so the element at the 1-st row from the top and 2-nd column from the left of the transpose B is 4.

Sample Input 2

2 2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

1000000000 1000000000
1000000000 1000000000
D - mpp

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

配点 : 200 点

問題文

英小文字からなる文字列 S が与えられます。 S の中で出現回数が最も多い文字をすべて取り除き、残った文字を元の順序を保ったまま連結して出力してください。

なお、出現回数が最大の文字が複数種類ある場合は、そのすべてを取り除いてください。

制約

  • 1 \le |S| \le 100
  • S は英小文字からなる文字列である

入力

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

S

出力

答えを出力せよ。

入力例 1

mississippi

出力例 1

mpp

mississippi に最も多く出現する文字は s と i でともに 4 回出現します。s と i をすべて取り除いた文字列は mpp となります。

入力例 2

atcoder

出力例 2














入力例 3
beginner












出力例 3
bgir







Score : 200 points







Problem Statement
You are given a string S consisting of lowercase English letters. Remove all occurrences of the most frequent character(s) in S, then output the remaining characters concatenated in their original order.


If there are multiple characters with the maximum frequency, remove all of them.











Constraints
    

  • 1 \le |S| \le 100
    • 

  • S is a string consisting of lowercase English letters.
    • 
















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


S












Output
Output the answer.















Sample Input 1
mississippi












Sample Output 1
mpp



The most frequent characters in mississippi are s and i, each appearing four times. Removing all occurrences of s and i yields the string mpp.













Sample Input 2
atcoder












Sample Output 2













Sample Input 3
beginner












Sample Output 3
bgir







			


			
		

	
		

		

			E - Not All Covered
			

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


			

				


配点 : 300 点







問題文
AtCoder 王国には 1 から N まで番号がつけられた N 個の城壁があります。また、 M 個の砲台があります。


砲台 i は L_i 以上 R_i 以下の番号の城壁を守っています。


ある砲台を破壊すると、その砲台が守っていた城壁はその砲台により守られなくなります。


どの砲台にも守られていない城壁が存在する状態にするためには、最小で何個の砲台を破壊する必要がありますか？











制約
    

  • 1 \leq N \leq 10^6
    • 

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

  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
    • 

  • 入力はすべて整数
    • 
















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


N M
L_1 R_1
L_2 R_2
 \vdots 
L_M R_M












出力
砲台に守られていない城壁が存在する状態にするために破壊する必要がある砲台の個数の最小値を出力せよ。















入力例 1
10 4
1 6
4 5
5 10
7 10












出力例 1
1



砲台 1 を破壊するとどの砲台も城壁 3 を守っていない状態になります。
また、砲台を 1 個も破壊しなければ全ての城壁がどれかの砲台に守られている状態になります。
そのため、1 を出力します。













入力例 2
5 2
1 2
3 4












出力例 2
0



どの砲台も城壁 5 を守っていないため、砲台を 1 個も破壊しないでも砲台に守られていない城壁が存在する状態になります。そのため、0 を出力します。













入力例 3
5 10
2 5
1 5
1 2
2 4
2 2
5 5
2 4
1 2
2 2
2 3












出力例 3
3







Score : 300 points







Problem Statement
In the AtCoder Kingdom, there are N castle walls numbered from 1 through N. There are also M turrets.


Turret i guards castle walls numbered from L_i through R_i.


When a turret is destroyed, the castle walls that were guarded by that turret are no longer guarded by that turret.


What is the minimum number of turrets that need to be destroyed so that at least one castle wall is not guarded by any turret?











Constraints
    

  • 1 \leq N \leq 10^6
    • 

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

  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
    • 

  • All input values are integers.
    • 
















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


N M
L_1 R_1
L_2 R_2
 \vdots 
L_M R_M












Output
Output the minimum number of turrets that need to be destroyed so that at least one castle wall is not guarded by any turret.















Sample Input 1
10 4
1 6
4 5
5 10
7 10












Sample Output 1
1



If turret 1 is destroyed, no turret guards castle wall 3.
Also, if no turrets are destroyed, all castle walls are guarded by some turret.
Therefore, output 1.













Sample Input 2
5 2
1 2
3 4












Sample Output 2
0



Since no turret guards castle wall 5, there already exists a castle wall not guarded by any turret without destroying any turrets. Therefore, output 0.













Sample Input 3
5 10
2 5
1 5
1 2
2 4
2 2
5 5
2 4
1 2
2 2
2 3












Sample Output 3
3