実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英小文字のみからなる文字列 S が与えられます。
S の各文字を英大文字に変換して得られる文字列 T を出力してください。
制約
- S は英小文字のみからなる、長さが 1 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
T を出力せよ。
入力例 1
abc
出力例 1
ABC
abc の各文字を英大文字に変換すると ABC になります。
入力例 2
a
出力例 2
A
入力例 3
abcdefghjiklnmoqprstvuwxyz
出力例 3
ABCDEFGHJIKLNMOQPRSTVUWXYZ
Score : 100 points
Problem Statement
You are given a string S consisting of lowercase English letters.
Uppercase each character of S and print the resulting string T.
Constraints
- S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Print T.
Sample Input 1
abc
Sample Output 1
ABC
Uppercase each character of abc, and you have ABC.
Sample Input 2
a
Sample Output 2
A
Sample Input 3
abcdefghjiklnmoqprstvuwxyz
Sample Output 3
ABCDEFGHJIKLNMOQPRSTVUWXYZ
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
0 以上 255 以下の整数 A,B が与えられます。 A \text{ xor }C=B となる 0 以上の整数 C を求めてください。
なお、そのような C はただ 1 つ存在し、0 以上 255 以下であることが証明されます。
\text{ xor } とは
整数 a, b のビットごとの排他的論理和 a \text{ xor } b は、以下のように定義されます。
- a \text{ xor } b を二進表記した際の 2^k (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 0\leq A,B \leq 255
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
入力例 1
3 6
出力例 1
5
3 は 二進表記で 11、5 は二進表記で 101 なので、これらの \text{xor} は二進表記で 110 であり、十進表記で 6 です。
このように、3 \text{ xor } 5 = 6 となるので、答えは 5 です。
入力例 2
10 12
出力例 2
6

Score : 100 points
Problem Statement
You are given integers A and B between 0 and 255 (inclusive). Find a non-negative integer C such that A \text{ xor }C=B.
It can be proved that there uniquely exists such C, and it will be between 0 and 255 (inclusive).
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of integers A and B, A\ \mathrm{XOR}\ B, is defined as follows:
- When A\ \mathrm{XOR}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
Constraints
- 0\leq A,B \leq 255
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B
Output
Print the answer.
Sample Input 1
3 6
Sample Output 1
5
When written in binary, 3 will be 11, and 5 will be 101. Thus, their \text{xor} will be 110 in binary, or 6 in decimal.
In short, 3 \text{ xor } 5 = 6, so the answer is 5.
Sample Input 2
10 12
Sample Output 2
6

実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N 人の人が総当り戦の試合をしました。
N 行 N 列からなる試合の結果の表 A が与えられます。A の i 行目 j 列目の要素を A_{i,j} と表します。
A_{i,j} は i=j のとき - であり、それ以外のとき W, L, D のいずれかです。
A_{i,j} が W, L, D であることは、人 i が人 j との試合に勝った、負けた、引き分けたことをそれぞれ表します。
与えられた表に矛盾があるかどうかを判定してください。
次のいずれかが成り立つとき、与えられた表には矛盾があるといいます。
- ある組 (i,j) が存在して、人 i が人 j に勝ったが、人 j が人 i に負けていない
- ある組 (i,j) が存在して、人 i が人 j に負けたが、人 j が人 i に勝っていない
- ある組 (i,j) が存在して、人 i が人 j に引き分けたが、人 j が人 i に引き分けていない
制約
- 2 \leq N \leq 1000
- A_{i,i} は
-である - i\neq j のとき、A_{i,j} は
W,L,Dのいずれかである
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}
出力
与えられた表に矛盾がないとき correct、矛盾があるとき incorrect と出力せよ。
入力例 1
4 -WWW L-DD LD-W LDW-
出力例 1
incorrect
人 3 が人 4 に勝ったにもかかわらず、人 4 も人 3 に勝ったことになっており、矛盾しています。
入力例 2
2 -D D-
出力例 2
correct
矛盾はありません。
Score : 200 points
Problem Statement
N players played a round-robin tournament.
You are given an N-by-N table A containing the results of the matches. Let A_{i,j} denote the element at the i-th row and j-th column of A.
A_{i,j} is - if i=j, and W, L, or D otherwise.
A_{i,j} is W if Player i beat Player j, L if Player i lost to Player j, and D if Player i drew with Player j.
Determine whether the given table is contradictory.
The table is said to be contradictory when some of the following holds:
- There is a pair (i,j) such that Player i beat Player j, but Player j did not lose to Player i;
- There is a pair (i,j) such that Player i lost to Player j, but Player j did not beat Player i;
- There is a pair (i,j) such that Player i drew with Player j, but Player j did not draw with Player i.
Constraints
- 2 \leq N \leq 1000
- A_{i,i} is
-. - A_{i,j} is
W,L, orD, for i\neq j.
Input
Input is given from Standard Input in the following format:
N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}
Output
If the given table is not contradictory, print correct; if it is contradictory, print incorrect.
Sample Input 1
4 -WWW L-DD LD-W LDW-
Sample Output 1
incorrect
Player 3 beat Player 4, while Player 4 also beat Player 3, which is contradictory.
Sample Input 2
2 -D D-
Sample Output 2
correct
There is no contradiction.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
I begin with T and end with T, and I am full of T. What am I?
文字列 t について、充填率を以下のように定義します。
- t の先頭と末尾の文字がともに
tであり、かつ |t| \geq 3 である場合: t に含まれるtの個数を x とすると、t の充填率は \displaystyle\frac{x-2}{|t|-2} である。ここで、|t| は t の長さを表す。 - そうでない場合: t の充填率は 0 である。
文字列 S が与えられます。S の部分文字列の充填率としてありうる最大値を求めてください。
部分文字列とは
S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、ab, bc, bcd は abcd の部分文字列ですが、ac, dc, e は abcd の部分文字列ではありません。
制約
- 1 \leq |S| \leq 100
- S は英小文字からなる文字列。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の部分文字列の充填率としてありうる最大値を出力せよ。
出力された値と真の値との絶対誤差が 10^{-9} 以下のとき、正答と判定される。
入力例 1
attitude
出力例 1
0.50000000000000000
ttit は S の部分文字列であり、その充填率は \displaystyle\frac{3-2}{4-2} = \frac{1}{2} です。
充填率が \frac{1}{2} より高い部分文字列は存在しないので、答えは \frac{1}{2} です。
入力例 2
ottottott
出力例 2
0.66666666666666667
ttottott は S の部分文字列であり、その充填率は \displaystyle\frac{6-2}{8-2} = \frac{2}{3} です。
充填率が \frac{2}{3} より高い部分文字列は存在しないので、答えは \frac{2}{3} です。
入力例 3
coffeecup
出力例 3
0.00000000000000000
ff は S の部分文字列であり、その充填率は 0 です。
充填率が 0 より高い部分文字列は存在しないので、答えは 0 です。
Score : 200 points
Problem Statement
I begin with T and end with T, and I am full of T. What am I?
For a string t, define the filling rate as follows:
- If the first and last characters of t are both
tand |t| \geq 3: Let x be the number oftin t. Then the filling rate of t is \displaystyle\frac{x-2}{|t|-2}, where |t| denotes the length of t. - Otherwise: the filling rate of t is 0.
You are given a string S. Find the maximum possible filling rate of a substring of S.
What is a substring?
A substring of S is a string obtained by removing zero or more characters from the beginning and the end of S. For example,ab, bc, and bcd are substrings of abcd, while ac, dc, and e are not substrings of abcd.
Constraints
- 1 \leq |S| \leq 100
- S is a string consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Print the maximum possible filling rate of a substring of S.
Your output will be judged as correct when the absolute error from the true value is at most 10^{-9}.
Sample Input 1
attitude
Sample Output 1
0.50000000000000000
ttit is a substring of S, and its filling rate is \displaystyle\frac{3-2}{4-2} = \frac{1}{2}.
There is no substring with a filling rate greater than \frac{1}{2}, so the answer is \frac{1}{2}.
Sample Input 2
ottottott
Sample Output 2
0.66666666666666667
ttottott is a substring of S, and its filling rate is \displaystyle\frac{6-2}{8-2} = \frac{2}{3}.
There is no substring with a filling rate greater than \frac{2}{3}, so the answer is \frac{2}{3}.
Sample Input 3
coffeecup
Sample Output 3
0.00000000000000000
ff is a substring of S, and its filling rate is 0.
There is no substring with a filling rate greater than 0, so the answer is 0.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, 2, \dots, N の番号が、辺には 1, 2, \dots, M の番号が付けられています。
辺 i \, (i = 1, 2, \dots, M) は頂点 u_i, v_i を結んでいます。
このグラフがパスグラフであるか判定してください。
単純無向グラフとは
単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。
パスグラフとは
頂点に 1, 2, \dots, N の番号が付けられたN 頂点のグラフがパスグラフであるとは、(1, 2, \dots, N) を並べ変えて得られる数列 (v_1, v_2, \dots, v_N) であって、以下の条件を満たすものが存在することをいいます。
制約
- 2 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
- 入力される値は全て整数
- 入力で与えられるグラフは単純
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
与えられたグラフがパスグラフなら Yes、そうでないなら No と出力せよ。
入力例 1
4 3 1 3 4 2 3 2
出力例 1
Yes
与えらえたグラフは下図のようであり、これはパスグラフです。

入力例 2
2 0
出力例 2
No
与えらえたグラフは下図のようであり、これはパスグラフではありません。

入力例 3
5 5 1 2 2 3 3 4 4 5 5 1
出力例 3
No
与えらえたグラフは下図のようであり、これはパスグラフではありません。

Score : 300 points
Problem Statement
You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.
Determine if this graph is a path graph.
What is a simple undirected graph?
A simple undirected graph is a graph without self-loops or multiple edges whose edges do not have a direction.
What is a path graph?
A graph with N vertices numbered 1, 2, \dots, N is said to be a path graph if and only if there is a sequence (v_1, v_2, \dots, v_N) that is a permutation of (1, 2, \dots, N) and satisfies the following conditions:
Constraints
- 2 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
- All values in the input are integers.
- The graph given in the input is simple.
Input
The input is given from Standard Input in the following format:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
Output
Print Yes if the given graph is a path graph; print No otherwise.
Sample Input 1
4 3 1 3 4 2 3 2
Sample Output 1
Yes
Illustrated below is the given graph, which is a path graph.

Sample Input 2
2 0
Sample Output 2
No
Illustrated below is the given graph, which is not a path graph.

Sample Input 3
5 5 1 2 2 3 3 4 4 5 5 1
Sample Output 3
No
Illustrated below is the given graph, which is not a path graph.
