Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
N 個の箱が横一列に並んでいます。 最初、左から i 番目の箱には a_i 個のキャンディが入っています。
すぬけ君は次の操作を好きな回数だけ行うことができます。
- キャンディが 1 個以上入っている箱をひとつ選び、その箱のキャンディを 1 個食べる。
すぬけ君の目標は次の通りです。
- どの隣り合う 2 つの箱を見ても、それらの箱に入っているキャンディの個数の総和が x 以下である。
目標を達成するために必要な操作回数の最小値を求めてください。
制約
- 2 ≤ N ≤ 10^5
- 0 ≤ a_i ≤ 10^9
- 0 ≤ x ≤ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N x a_1 a_2 ... a_N
出力
目標を達成するために必要な操作回数の最小値を出力せよ。
入力例 1
3 3 2 2 2
出力例 1
1
2 番目の箱のキャンディを 1 個食べればよいです。 すると、各箱のキャンディの個数は (2, 1, 2) となります。
入力例 2
6 1 1 6 1 2 0 4
出力例 2
11
たとえば、2 番目の箱のキャンディを 6 個食べ、4 番目の箱のキャンディを 2 個食べ、6 番目の箱のキャンディを 3 個食べればよいです。
すると、各箱キャンディの個数は (1, 0, 1, 0, 0, 1) となります。
入力例 3
5 9 3 1 4 1 5
出力例 3
0
最初から目標が達成されているので、操作を行う必要はありません。
入力例 4
2 0 5 5
出力例 4
10
すべてのキャンディを食べなければなりません。
Score : 300 points
Problem Statement
There are N boxes arranged in a row. Initially, the i-th box from the left contains a_i candies.
Snuke can perform the following operation any number of times:
- Choose a box containing at least one candy, and eat one of the candies in the chosen box.
His objective is as follows:
- Any two neighboring boxes contain at most x candies in total.
Find the minimum number of operations required to achieve the objective.
Constraints
- 2 ≤ N ≤ 10^5
- 0 ≤ a_i ≤ 10^9
- 0 ≤ x ≤ 10^9
Input
The input is given from Standard Input in the following format:
N x a_1 a_2 ... a_N
Output
Print the minimum number of operations required to achieve the objective.
Sample Input 1
3 3 2 2 2
Sample Output 1
1
Eat one candy in the second box. Then, the number of candies in each box becomes (2, 1, 2).
Sample Input 2
6 1 1 6 1 2 0 4
Sample Output 2
11
For example, eat six candies in the second box, two in the fourth box, and three in the sixth box. Then, the number of candies in each box becomes (1, 0, 1, 0, 0, 1).
Sample Input 3
5 9 3 1 4 1 5
Sample Output 3
0
The objective is already achieved without performing operations.
Sample Input 4
2 0 5 5
Sample Output 4
10
All the candies need to be eaten.
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
長さ 3 以上の文字列 s があります。 s の中に同一の文字が隣り合う箇所はありません。
高橋君と青木君がゲームで勝負します。 二人は交互に次の操作を行います。 高橋君が先手です。
- s から両端以外の文字をひとつ取り除く。 ただし、その文字を取り除くことで、s の中に同一の文字が隣り合う箇所ができる場合、その文字を取り除くことはできない。
先に操作を行えなくなった人が負けです。 二人が最適に行動したとき、どちらが勝つかを判定してください。
制約
- 3 ≤ |s| ≤ 10^5
- s は英小文字のみからなる。
- s の中に同一の文字が隣り合う箇所はない。
入力
入力は以下の形式で標準入力から与えられる。
s
出力
先手の高橋君が勝つならば First を、後手の青木君が勝つならば Second を出力せよ。
入力例 1
aba
出力例 1
Second
先手の高橋君は操作を行うことができません。
なぜならば、s から両端以外の文字の b を取り除くと、s は aa となって a が隣り合うからです。
入力例 2
abc
出力例 2
First
先手の高橋君が s から b を取り除くと、s は ac となります。
すると、後手の青木君は操作を行うことができません。
なぜならば、s には両端以外の文字が存在しないからです。
入力例 3
abcab
出力例 3
First
Score : 500 points
Problem Statement
There is a string s of length 3 or greater. No two neighboring characters in s are equal.
Takahashi and Aoki will play a game against each other. The two players alternately performs the following operation, Takahashi going first:
- Remove one of the characters in s, excluding both ends. However, a character cannot be removed if removal of the character would result in two neighboring equal characters in s.
The player who becomes unable to perform the operation, loses the game. Determine which player will win when the two play optimally.
Constraints
- 3 ≤ |s| ≤ 10^5
- s consists of lowercase English letters.
- No two neighboring characters in s are equal.
Input
The input is given from Standard Input in the following format:
s
Output
If Takahashi will win, print First. If Aoki will win, print Second.
Sample Input 1
aba
Sample Output 1
Second
Takahashi, who goes first, cannot perform the operation, since removal of the b, which is the only character not at either ends of s, would result in s becoming aa, with two as neighboring.
Sample Input 2
abc
Sample Output 2
First
When Takahashi removes b from s, it becomes ac.
Then, Aoki cannot perform the operation, since there is no character in s, excluding both ends.
Sample Input 3
abcab
Sample Output 3
First
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 600 点
問題文
xy 平面があります。 すぬけ君は座標 (x_s, y_s) から座標 (x_t, y_t) まで移動しようとしています。 すぬけ君は好きな向きへ速さ 1 で動くことができます。 なお、すぬけ君は大きさのない点と見なすことにします。
平面上には N 個の円形のバリアが張ってあります。 i 番目のバリアは中心が (x_i, y_i) で半径が r_i です。 バリアは互いに重なっていたり、互いを含んでいたりすることがあります。
平面上の各座標について、その座標がどのバリアの内部にも含まれない場合、その座標には宇宙線が降り注いでいます。
すぬけ君は移動中にできるだけ宇宙線を浴びたくないので、宇宙線を浴びる時間が最小になるように移動します。 すぬけ君が移動中に宇宙線を浴びる時間の最小値を求めてください。
制約
- 入力はすべて整数である。
- -10^9 ≤ x_s, y_s, x_t, y_t ≤ 10^9
- (x_s, y_s) ≠ (x_t, y_t)
- 1≤N≤1,000
- -10^9 ≤ x_i, y_i ≤ 10^9
- 1 ≤ r_i ≤ 10^9
入力
入力は以下の形式で標準入力から与えられる。
x_s y_s x_t y_t N x_1 y_1 r_1 x_2 y_2 r_2 : x_N y_N r_N
出力
すぬけ君が移動中に宇宙線を浴びる時間の最小値を出力せよ。 絶対誤差または相対誤差が 10^{-9} 以下ならば正解となる。
入力例 1
-2 -2 2 2 1 0 0 1
出力例 1
3.6568542495
たとえば、図のように移動すればよいです。
入力例 2
-2 0 2 0 2 -1 0 2 1 0 2
出力例 2
0.0000000000
たとえば、図のように移動すればよいです。
入力例 3
4 -2 -2 4 3 0 0 2 4 0 1 0 4 1
出力例 3
4.0000000000
たとえば、図のように移動すればよいです。
Score : 600 points
Problem Statement
On the xy-plane, Snuke is going to travel from the point (x_s, y_s) to the point (x_t, y_t). He can move in arbitrary directions with speed 1. Here, we will consider him as a point without size.
There are N circular barriers deployed on the plane. The center and the radius of the i-th barrier are (x_i, y_i) and r_i, respectively. The barriers may overlap or contain each other.
A point on the plane is exposed to cosmic rays if the point is not within any of the barriers.
Snuke wants to avoid exposure to cosmic rays as much as possible during the travel. Find the minimum possible duration of time he is exposed to cosmic rays during the travel.
Constraints
- All input values are integers.
- -10^9 ≤ x_s, y_s, x_t, y_t ≤ 10^9
- (x_s, y_s) ≠ (x_t, y_t)
- 1≤N≤1,000
- -10^9 ≤ x_i, y_i ≤ 10^9
- 1 ≤ r_i ≤ 10^9
Input
The input is given from Standard Input in the following format:
x_s y_s x_t y_t N x_1 y_1 r_1 x_2 y_2 r_2 : x_N y_N r_N
Output
Print the minimum possible duration of time Snuke is exposed to cosmic rays during the travel. The output is considered correct if the absolute or relative error is at most 10^{-9}.
Sample Input 1
-2 -2 2 2 1 0 0 1
Sample Output 1
3.6568542495
An optimal route is as follows:
Sample Input 2
-2 0 2 0 2 -1 0 2 1 0 2
Sample Output 2
0.0000000000
An optimal route is as follows:
Sample Input 3
4 -2 -2 4 3 0 0 2 4 0 1 0 4 1
Sample Output 3
4.0000000000
An optimal route is as follows:
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1000 点
問題文
高橋君と青木君が協力して数列を作ることになりました。
まず、高橋君が次の条件をすべて満たす数列 a を用意します。
- a は長さ N である。
- a の各要素は 1 以上 K 以下の整数である。
- a は回文である。 すなわち、a を逆順にした数列は元の a と一致する。
次に、青木君が次の操作を好きな回数だけ繰り返します。
- a の先頭要素を末尾へ移動する。
以上の手続きにより、最終的な a が得られます。
最終的な a として考えられるものは何通りあるでしょうか？ 10^9+7 で割った余りを求めてください。
制約
- 1≤N≤10^9
- 1≤K≤10^9
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
最終的な a として考えられるものは何通りあるか？ 10^9+7 で割った余りを出力せよ。
入力例 1
4 2
出力例 1
6
次の 6 通りです。
- (1, 1, 1, 1)
- (1, 1, 2, 2)
- (1, 2, 2, 1)
- (2, 2, 1, 1)
- (2, 1, 1, 2)
- (2, 2, 2, 2)
入力例 2
1 10
出力例 2
10
入力例 3
6 3
出力例 3
75
入力例 4
1000000000 1000000000
出力例 4
875699961
Score : 1000 points
Problem Statement
Takahashi and Aoki are going to together construct a sequence of integers.
First, Takahashi will provide a sequence of integers a, satisfying all of the following conditions:
- The length of a is N.
- Each element in a is an integer between 1 and K, inclusive.
- a is a palindrome, that is, reversing the order of elements in a will result in the same sequence as the original.
Then, Aoki will perform the following operation an arbitrary number of times:
- Move the first element in a to the end of a.
How many sequences a can be obtained after this procedure, modulo 10^9+7?
Constraints
- 1≤N≤10^9
- 1≤K≤10^9
Input
The input is given from Standard Input in the following format:
N K
Output
Print the number of the sequences a that can be obtained after the procedure, modulo 10^9+7.
Sample Input 1
4 2
Sample Output 1
6
The following six sequences can be obtained:
- (1, 1, 1, 1)
- (1, 1, 2, 2)
- (1, 2, 2, 1)
- (2, 2, 1, 1)
- (2, 1, 1, 2)
- (2, 2, 2, 2)
Sample Input 2
1 10
Sample Output 2
10
Sample Input 3
6 3
Sample Output 3
75
Sample Input 4
1000000000 1000000000
Sample Output 4
875699961