Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
英大文字・英小文字からなる空でない文字列 S が与えられます。以下の条件が満たされているか判定してください。
- S の先頭の文字は大文字であり、それ以外の文字はすべて小文字である。
制約
- 1 \leq |S| \leq 100（|S| は文字列 S の長さ）
- S の各文字は英大文字または英小文字である。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
条件が満たされていれば Yes、そうでなければ No を出力せよ。
入力例 1
Capitalized
出力例 1
Yes
Capitalized の先頭の文字 C は大文字であり、それ以外の文字 apitalized はすべて小文字であるため、Yes を出力します。
入力例 2
AtCoder
出力例 2
No
AtCoder は先頭以外にも大文字 C を含むため、No を出力します。
入力例 3
yes
出力例 3
No
yes の先頭の文字 y は大文字でないため、No を出力します。
入力例 4
A
出力例 4
Yes
Score: 100 points
Problem Statement
You are given a non-empty string S consisting of uppercase and lowercase English letters. Determine whether the following condition is satisfied:
- The first character of S is uppercase, and all other characters are lowercase.
Constraints
- 1 \leq |S| \leq 100 (|S| is the length of the string S.)
- Each character of S is an uppercase or lowercase English letter.
Input
The input is given from Standard Input in the following format:
S
Output
If the condition is satisfied, print Yes; otherwise, print No.
Sample Input 1
Capitalized
Sample Output 1
Yes
The first character C of Capitalized is uppercase, and all other characters apitalized are lowercase, so you should print Yes.
Sample Input 2
AtCoder
Sample Output 2
No
AtCoder contains an uppercase letter C that is not at the beginning, so you should print No.
Sample Input 3
yes
Sample Output 3
No
The first character y of yes is not uppercase, so you should print No.
Sample Input 4
A
Sample Output 4
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
キーエンスでは、役割や年齢、立場の違いに関係なく「さん」付けして呼ぶという文化があります。 新入社員が社長を呼ぶときも「中田さん」と呼びます。
ある人の苗字と名前がそれぞれ文字列 S,T として与えられます。
苗字、スペース（ ）、敬称（san）をこの順に連結した文字列を出力してください。
制約
- S,T は以下の各条件を満たす文字列
- 長さ 1 以上 10 以下
- 先頭の文字は英大文字
- 先頭以外の文字は英小文字
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
苗字、スペース（ ）、敬称（san）をこの順に連結した文字列を出力せよ。
入力例 1
Takahashi Chokudai
出力例 1
Takahashi san
苗字（Takahashi）、スペース（ ）、敬称（san）をこの順に連結した文字列を出力します。
入力例 2
K Eyence
出力例 2
K san
Score : 100 points
Problem Statement
Keyence has a culture of addressing everyone with the honorific "san," regardless of their role, age, or position. Even a new employee would call the president "Nakata-san." [Translator's note: this is a bit unusual in Japan.]
You are given a person's surname and first name as strings S and T, respectively.
Print the concatenation of the surname, a space ( ), and the honorific (san) in this order.
Constraints
- Each of S and T is a string that satisfies the following conditions.
- The length is between 1 and 10, inclusive.
- The first character is an uppercase English letter.
- All characters except the first one are lowercase English letters.
Input
The input is given from Standard Input in the following format:
S T
Output
Print the concatenation of the surname, a space ( ), and the honorific (san) in this order.
Sample Input 1
Takahashi Chokudai
Sample Output 1
Takahashi san
Print the concatenation of the surname (Takahashi), a space ( ), and the honorific (san) in this order.
Sample Input 2
K Eyence
Sample Output 2
K san
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) 及び整数 L,R が与えられます。ここで L,R は L\leq R を満たします。
i=1,2,\ldots,N について以下の 2 つの条件を共に満たす整数 X_i を求めてください。なお、求める整数は常に一意に定まります。
- L\leq X_i \leq R
- L 以上 R 以下であるようなどの整数 Y についても |X_i - A_i| \leq |Y-A_i| を満たす
制約
- 1\leq N\leq 2\times 10^5
- 1\leq L\leq R \leq 10^9
- 1\leq A_i\leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L R A_1 \ldots A_N
出力
i=1,2,\ldots,N について X_i を空白区切りで出力せよ。
入力例 1
5 4 7 3 1 4 9 7
出力例 1
4 4 4 7 7
i=1 では、
- |4-3|=1
- |5-3|=2
- |6-3|=3
- |7-3|=4
より X_i = 4 です。
入力例 2
3 10 10 11 10 9
出力例 2
10 10 10
Score : 200 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.
For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.
- L\leq X_i \leq R.
- For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq L\leq R \leq 10^9
- 1\leq A_i\leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N L R A_1 \ldots A_N
Output
Print X_i for i=1,2,\ldots,N, separated by spaces.
Sample Input 1
5 4 7 3 1 4 9 7
Sample Output 1
4 4 4 7 7
For i=1:
- |4-3|=1
- |5-3|=2
- |6-3|=3
- |7-3|=4
Thus, X_i = 4.
Sample Input 2
3 10 10 11 10 9
Sample Output 2
10 10 10
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
無限に長いピアノの鍵盤があります。 この鍵盤内の連続する区間であって、白鍵 W 個と黒鍵 B 個からなるものは存在しますか？
文字列 wbwbwwbwbwbw を無限に繰り返してできる文字列を S とおきます。
S の部分文字列であって、W 個の w と B 個の b からなるものは存在しますか？
S の部分文字列とは
S の部分文字列とは、ある 2 つの正整数 l,r\ (l\leq r) に対して、S の l 文字目、l+1 文字目、\dots、r 文字目をこの順に繋げてできる文字列のことをいいます。制約
- W,B は整数
- 0\leq W,B \leq 100
- W+B \geq 1
入力
入力は以下の形式で標準入力から与えられる。
W B
出力
S の部分文字列であって、W 個の w と B 個の b からなるものが存在するならば Yes を、存在しないならば No を出力せよ。
入力例 1
3 2
出力例 1
Yes
S の最初の 15 文字は wbwbwwbwbwbwwbw であり、S の 11 文字目から 15 文字目までを取り出してできる文字列 bwwbw は 3 個の w と 2 個の b からなる部分文字列の一例です。
入力例 2
3 0
出力例 2
No
3 個の w と 0 個の b からなる文字列は www のみですが、これは S の部分文字列ではありません。
入力例 3
92 66
出力例 3
Yes
Score: 200 points
Problem Statement
There is an infinitely long piano keyboard. Is there a continuous segment within this keyboard that consists of W white keys and B black keys?
Let S be the string formed by infinitely repeating the string wbwbwwbwbwbw.
Is there a substring of S that consists of W occurrences of w and B occurrences of b?
What is a substring of S?
A substring of S is a string that can be formed by concatenating the l-th, (l+1)-th, \dots, r-th characters of S in this order for some two positive integers l and r (l\leq r).Constraints
- W and B are integers.
- 0\leq W,B \leq 100
- W+B \geq 1
Input
The input is given from Standard Input in the following format:
W B
Output
If there is a substring of S that consists of W occurrences of w and B occurrences of b, print Yes; otherwise, print No.
Sample Input 1
3 2
Sample Output 1
Yes
The first 15 characters of S are wbwbwwbwbwbwwbw. You can take the 11-th through 15-th characters to form the string bwwbw, which is a substring consisting of three occurrences of w and two occurrences of b.
Sample Input 2
3 0
Sample Output 2
No
The only string consisting of three occurrences of w and zero occurrences of b is www, which is not a substring of S.
Sample Input 3
92 66
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 本の導火線を一直線に接着したものがあります。左から i 本目の導火線は長さが A_i cm で、 1 秒あたり B_i cm の一定の速さで燃えます。
この導火線の左端と右端から同時に火をつけるとき、 2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i,B_i \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か（単位を除いて）出力せよ。
想定解答との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる。
入力例 1
3 1 1 2 1 3 1
出力例 1
3.000000000000000
着火前の導火線の左端から 3 cm の地点で 2 つの火がぶつかります。
入力例 2
3 1 3 2 2 3 1
出力例 2
3.833333333333333
入力例 3
5 3 9 1 2 4 6 1 5 5 3
出力例 3
8.916666666666668
Score : 300 points
Problem Statement
We have N fuses connected in series. The i-th fuse from the left has a length of A_i centimeters and burns at a constant speed of B_i centimeters per second.
Consider igniting this object from left and right ends simultaneously. Find the distance between the position where the two flames will meet and the left end of the object.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i,B_i \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print the distance between the position where the two flames will meet and the left end of the object, in centimeters (print just the number).
Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-5}.
Sample Input 1
3 1 1 2 1 3 1
Sample Output 1
3.000000000000000
The two flames will meet at 3 centimeters from the left end of the object.
Sample Input 2
3 1 3 2 2 3 1
Sample Output 2
3.833333333333333
Sample Input 3
5 3 9 1 2 4 6 1 5 5 3
Sample Output 3
8.916666666666668
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
AtCoder 王国の 1 週間は A+B 日からなり、1 日目から A 日目が休日で、A+1 日目から A+B 日目が平日です。
高橋くんは N 個の予定があり、i 番目の予定は今日から D_i 日後です。
高橋くんは今日が 1 週間の何日目かを忘れてしまいました。高橋くんの N 個の予定が全て休日である可能性があるかを判定してください。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq A,B\leq 10^9
- 1\leq D_1<D_2<\ldots<D_N\leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N A B D_1 D_2 \ldots D_N
出力
高橋くんの N 個の予定が全て休日である可能性がある場合は Yes を、そうでない場合は No を一行に出力せよ。
入力例 1
3 2 5 1 2 9
出力例 1
Yes
入力では 1 週間は 7 日からなり、1 日目から 2 日目が休日、3 日目から 7 日目が平日です。
今日が 1 週間の 7 日目だとします。このとき、1 日後は 1 週間の 1 日目、2 日後は 1 週間の 2 日目、9 日後は 1 週間の 2 日目となり、全ての予定が休日となります。そのため、高橋くんの N 個の予定が全て休日である可能性があります。
入力例 2
2 5 10 10 15
出力例 2
No
入力例 3
4 347 347 347 700 705 710
出力例 3
Yes
Score: 350 points
Problem Statement
In the Kingdom of AtCoder, a week consists of A+B days, with the first through A-th days being holidays and the (A+1)-th through (A+B)-th being weekdays.
Takahashi has N plans, and the i-th plan is scheduled D_i days later.
He has forgotten what day of the week it is today. Determine if it is possible for all of his N plans to be scheduled on holidays.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq A,B\leq 10^9
- 1\leq D_1<D_2<\ldots<D_N\leq 10^9
Input
The input is given from Standard Input in the following format:
N A B D_1 D_2 \ldots D_N
Output
Print Yes in a single line if it is possible for all of Takahashi's N plans to be scheduled on holidays, and No otherwise.
Sample Input 1
3 2 5 1 2 9
Sample Output 1
Yes
In this input, a week consists of seven days, with the first through second days being holidays and the third through seventh days being weekdays.
Let us assume today is the seventh day of the week. In this case, one day later would be the first day of the week, two days later would be the second day of the week, and nine days later would also be the second day of the week, making all plans scheduled on holidays. Therefore, it is possible for all of Takahashi's N plans to be scheduled on holidays.
Sample Input 2
2 5 10 10 15
Sample Output 2
No
Sample Input 3
4 347 347 347 700 705 710
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
整数 N が与えられるので、以下の条件を全て満たす最小の整数 X を求めてください。
- X は N 以上である。
- 非負整数 (a,b) の組であって、 X=a^3+a^2b+ab^2+b^3 を満たすようなものが存在する。
制約
- N は整数
- 0 \le N \le 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
9
出力例 1
15
9 \le X \le 14 であるようなどの整数 X についても、問題文中の条件を満たすような (a,b) は存在しません。
X=15 は (a,b)=(2,1) とすると問題文中の条件を満たします。
入力例 2
0
出力例 2
0
N 自身が条件を満たすこともあります。
入力例 3
999999999989449206
出力例 3
1000000000000000000
入出力が 32bit 整数型に収まらない場合があります。
Score : 400 points
Problem Statement
Given an integer N, find the smallest integer X that satisfies all of the conditions below.
- X is greater than or equal to N.
- There is a pair of non-negative integers (a, b) such that X=a^3+a^2b+ab^2+b^3.
Constraints
- N is an integer.
- 0 \le N \le 10^{18}
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
9
Sample Output 1
15
For any integer X such that 9 \le X \le 14, there is no (a, b) that satisfies the condition in the statement.
For X=15, (a,b)=(2,1) satisfies the condition.
Sample Input 2
0
Sample Output 2
0
N itself may satisfy the condition.
Sample Input 3
999999999989449206
Sample Output 3
1000000000000000000
Input and output may not fit into a 32-bit integer type.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
N 頂点 M 辺の単純無向グラフが与えられます。頂点は 1, \dots, N と番号付けられ、i \, (1 \leq i \leq M) 番目の辺は頂点 U_i, V_i を結んでいます。
それぞれの頂点を赤または青で塗る方法は全部で 2^N 通りあります。これらのうち、以下の条件を全て満たすものの総数を 998244353 で割った余りを求めてください。
- 赤く塗られた頂点がちょうど K 個ある
- 異なる色で塗られた頂点を結ぶ辺の本数は偶数である
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq K \leq N
- 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
- (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K U_1 V_1 \vdots U_M V_M
出力
答えを出力せよ。
入力例 1
4 4 2 1 2 1 3 2 3 3 4
出力例 1
2
以下の 2 通りが条件を満たします。
- 頂点 1, 2 を赤く、頂点 3, 4 を青く塗る。
- 頂点 3, 4 を赤く、頂点 1, 2 を青く塗る。
上記の塗り方について、異なる色で塗られた頂点を結ぶ辺は 2 番目の辺と 3 番目の辺です。
入力例 2
10 10 3 1 2 2 4 1 5 3 6 3 9 4 10 7 8 9 10 5 9 3 4
出力例 2
64
Score : 500 points
Problem Statement
You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq M) edge connects Vertices U_i and V_i.
There are 2^N ways to paint each vertex red or blue. Find the number, modulo 998244353, of such ways that satisfy all of the following conditions:
- There are exactly K vertices painted red.
- There is an even number of edges connecting vertices painted in different colors.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq K \leq N
- 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
- (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K U_1 V_1 \vdots U_M V_M
Output
Print the answer.
Sample Input 1
4 4 2 1 2 1 3 2 3 3 4
Sample Output 1
2
The following two ways satisfy the conditions.
- Paint Vertices 1 and 2 red and Vertices 3 and 4 blue.
- Paint Vertices 3 and 4 red and Vertices 1 and 2 blue.
In either of the ways above, the 2-nd and 3-rd edges connect vertices painted in different colors.
Sample Input 2
10 10 3 1 2 2 4 1 5 3 6 3 9 4 10 7 8 9 10 5 9 3 4
Sample Output 2
64
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
N+1 頂点の無向グラフが与えられます。
頂点には頂点 0 、頂点 1 、\ldots 、頂点 N と名前がついています。
i=1,2,\ldots,N について、頂点 0 と頂点 i を結ぶ重み A_i の無向辺があります。
また、i=1,2,\ldots,N について、頂点 i と頂点 i+1 を結ぶ重み B_i の無向辺があります。(ただし、頂点 N+1 は頂点 1 とみなします。)
上に述べた 2N 本の辺の他に辺はありません。
このグラフからいくつかの辺を削除して、グラフを二部グラフにします。
削除する辺の重みの総和の最小値はいくつですか？
制約
- 3 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
出力
答えを出力せよ。
入力例 1
5 31 4 159 2 65 5 5 5 5 10
出力例 1
16
頂点 0,2 を結ぶ辺(重み 4 )、頂点 0,4 を結ぶ辺(重み 2 )、頂点 1,5 を結ぶ辺(重み 10 )を削除するとグラフは二部グラフになります。
入力例 2
4 100 100 100 1000000000 1 2 3 4
出力例 2
10
Score : 500 points
Problem Statement
Given is an undirected graph with N+1 vertices.
The vertices are called Vertex 0, Vertex 1, \ldots, Vertex N.
For each i=1,2,\ldots,N, the graph has an undirected edge with a weight of A_i connecting Vertex 0 and Vertex i.
Additionally, for each i=1,2,\ldots,N, the graph has an undirected edge with a weight of B_i connecting Vertex i and Vertex i+1. (Here, Vertex N+1 stands for Vertex 1.)
The graph has no edge other than these 2N edges above.
Let us delete some of the edges from this graph so that the graph will be bipartite.
What is the minimum total weight of the edges that have to be deleted?
Constraints
- 3 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
Output
Print the answer.
Sample Input 1
5 31 4 159 2 65 5 5 5 5 10
Sample Output 1
16
Deleting the edge connecting Vertices 0,2 (weight: 4), the edge connecting Vertices 0,4 (weight: 2), and the edge connecting Vertices 1,5 (weight: 10) makes the graph bipartite.
Sample Input 2
4 100 100 100 1000000000 1 2 3 4
Sample Output 2
10