Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
高橋君は青木君と待ち合わせをしています。
待ち合わせ場所は高橋君の家から D メートル離れた地点であり、待ち合わせの時刻は T 分後です。
高橋君は今から家を出発し、分速 S メートルで待ち合わせ場所までまっすぐ移動します。
待ち合わせに間に合うでしょうか？
制約
- 1 \leq D \leq 10000
- 1 \leq T \leq 10000
- 1 \leq S \leq 10000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
D T S
出力
高橋君が待ち合わせ時刻までに待ち合わせ場所に到着するならば Yes、そうでないなら No を出力せよ。
入力例 1
1000 15 80
出力例 1
Yes
高橋君から待ち合わせ場所までの距離 1000 メートルを分速 80 メートルで移動すると 12.5 分かかります。待ち合わせ時刻は 15 分後なので間に合います。
入力例 2
2000 20 100
出力例 2
Yes
高橋君から待ち合わせ場所までの距離 2000 メートルを分速 100 メートルで移動すると 20 分かかります。待ち合わせ時刻は 20 分後なのでちょうど間に合います。
入力例 3
10000 1 1
出力例 3
No
間に合いません。
Score : 100 points
Problem Statement
Takahashi is meeting up with Aoki.
They have planned to meet at a place that is D meters away from Takahashi's house in T minutes from now.
Takahashi will leave his house now and go straight to the place at a speed of S meters per minute.
Will he arrive in time?
Constraints
- 1 \leq D \leq 10000
- 1 \leq T \leq 10000
- 1 \leq S \leq 10000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
D T S
Output
If Takahashi will reach the place in time, print Yes; otherwise, print No.
Sample Input 1
1000 15 80
Sample Output 1
Yes
It takes 12.5 minutes to go 1000 meters to the place at a speed of 80 meters per minute. They have planned to meet in 15 minutes so he will arrive in time.
Sample Input 2
2000 20 100
Sample Output 2
Yes
It takes 20 minutes to go 2000 meters to the place at a speed of 100 meters per minute. They have planned to meet in 20 minutes so he will arrive just on time.
Sample Input 3
10000 1 1
Sample Output 3
No
He will be late.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
2 つの文字列 S, T が与えられます。
T が S の部分文字列となるように、S のいくつかの文字を書き換えます。
少なくとも何文字書き換える必要がありますか？
ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。
制約
- S,T は 1 文字以上 1000 文字以下
- T の長さは S の長さ以下
- S,T は 英小文字のみを含む
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S を書き換える文字数の最小値を出力せよ。
入力例 1
cabacc abc
出力例 1
1
例えば S の 4 文字目の a を c に書き換えることで、S の 2～4 文字目が T と一致します。
S 自身は T を部分文字列に持たないので、この 1 文字を書き換えるのが最小です。
入力例 2
codeforces atcoder
出力例 2
6
Score : 200 points
Problem Statement
Given are two strings S and T.
Let us change some of the characters in S so that T will be a substring of S.
At least how many characters do we need to change?
Here, a substring is a consecutive subsequence. For example, xxx is a substring of yxxxy, but not a substring of xxyxx.
Constraints
- The lengths of S and T are each at least 1 and at most 1000.
- The length of T is at most that of S.
- S and T consist of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S T
Output
Print the minimum number of characters in S that need to be changed.
Sample Input 1
cabacc abc
Sample Output 1
1
For example, changing the fourth character a in S to c will match the second through fourth characters in S to T.
Since S itself does not have T as its substring, this number of changes - one - is the minimum needed.
Sample Input 2
codeforces atcoder
Sample Output 2
6
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 個の整数 A_1,\ldots,A_N が与えられます。
1\leq i < j \leq N を満たす全ての組 (i,j) についての A_i \times A_j の和を \bmod (10^9+7) で求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- 0 \leq A_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} A_i A_j を \bmod (10^9+7) で出力せよ。
入力例 1
3 1 2 3
出力例 1
11
1 \times 2 + 1 \times 3 + 2 \times 3 = 11 です。
入力例 2
4 141421356 17320508 22360679 244949
出力例 2
437235829
Score : 300 points
Problem Statement
Given are N integers A_1,\ldots,A_N.
Find the sum of A_i \times A_j over all pairs (i,j) such that 1\leq i < j \leq N, modulo (10^9+7).
Constraints
- 2 \leq N \leq 2\times 10^5
- 0 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} A_i A_j, modulo (10^9+7).
Sample Input 1
3 1 2 3
Sample Output 1
11
We have 1 \times 2 + 1 \times 3 + 2 \times 3 = 11.
Sample Input 2
4 141421356 17320508 22360679 244949
Sample Output 2
437235829
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
人 1 から 人 N までの N 人の人がいます。
「人 A_i と人 B_i は友達である」という情報が M 個与えられます。同じ情報が複数回与えられることもあります。
X と Y が友達、かつ、Y と Z が友達ならば、X と Z も友達です。また、M 個の情報から導くことができない友達関係は存在しません。
悪の高橋君は、この N 人をいくつかのグループに分け、全ての人について「同じグループの中に友達がいない」という状況を作ろうとしています。
最小でいくつのグループに分ければ良いでしょうか？
制約
- 2 \leq N \leq 2\times 10^5
- 0 \leq M \leq 2\times 10^5
- 1\leq A_i,B_i\leq N
- A_i \neq B_i
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 \vdots A_M B_M
出力
答えを出力せよ。
入力例 1
5 3 1 2 3 4 5 1
出力例 1
3
例えば \{1,3\},\{2,4\},\{5\} という 3 つのグループに分けることで目的を達成できます。
入力例 2
4 10 1 2 2 1 1 2 2 1 1 2 1 3 1 4 2 3 2 4 3 4
出力例 2
4
入力例 3
10 4 3 1 4 1 5 9 2 6
出力例 3
3
Score : 400 points
Problem Statement
There are N persons called Person 1 through Person N.
You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.
If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.
Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.
At least how many groups does he need to make?
Constraints
- 2 \leq N \leq 2\times 10^5
- 0 \leq M \leq 2\times 10^5
- 1\leq A_i,B_i\leq N
- A_i \neq B_i
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 \vdots A_M B_M
Output
Print the answer.
Sample Input 1
5 3 1 2 3 4 5 1
Sample Output 1
3
Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.
Sample Input 2
4 10 1 2 2 1 1 2 2 1 1 2 1 3 1 4 2 3 2 4 3 4
Sample Output 2
4
Sample Input 3
10 4 3 1 4 1 5 9 2 6
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個の整数があります。i 番目の数は A_i です。
「全ての 1\leq i < j \leq N について、GCD(A_i,A_j)=1」が成り立つとき、\{A_i\} は pairwise coprime であるといいます。
\{A_i\} が pairwise coprime ではなく、かつ、GCD(A_1,\ldots,A_N)=1 であるとき、\{A_i\} は setwise coprime であるといいます。
\{A_i\} が pairwise coprime、setwise coprime、そのどちらでもない、のいずれであるか判定してください。
ただし GCD(\ldots) は最大公約数を表します。
制約
- 2 \leq N \leq 10^6
- 1 \leq A_i\leq 10^6
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
\{A_i\} が pairwise coprime ならば pairwise coprime、setwise coprime ならば setwise coprime、そのどちらでもなければ not coprime と出力せよ。
入力例 1
3 3 4 5
出力例 1
pairwise coprime
GCD(3,4)=GCD(3,5)=GCD(4,5)=1 なので pairwise coprime です。
入力例 2
3 6 10 15
出力例 2
setwise coprime
GCD(6,10)=2 なので pairwise coprime ではありませんが、GCD(6,10,15)=1 なので setwise coprime です。
入力例 3
3 6 10 16
出力例 3
not coprime
GCD(6,10,16)=2 なので、pairwise coprime でも setwise coprime でもありません。
Score : 500 points
Problem Statement
We have N integers. The i-th number is A_i.
\{A_i\} is said to be pairwise coprime when GCD(A_i,A_j)=1 holds for every pair (i, j) such that 1\leq i < j \leq N.
\{A_i\} is said to be setwise coprime when \{A_i\} is not pairwise coprime but GCD(A_1,\ldots,A_N)=1.
Determine if \{A_i\} is pairwise coprime, setwise coprime, or neither.
Here, GCD(\ldots) denotes greatest common divisor.
Constraints
- 2 \leq N \leq 10^6
- 1 \leq A_i\leq 10^6
Input
Input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
If \{A_i\} is pairwise coprime, print pairwise coprime; if \{A_i\} is setwise coprime, print setwise coprime; if neither, print not coprime.
Sample Input 1
3 3 4 5
Sample Output 1
pairwise coprime
GCD(3,4)=GCD(3,5)=GCD(4,5)=1, so they are pairwise coprime.
Sample Input 2
3 6 10 15
Sample Output 2
setwise coprime
Since GCD(6,10)=2, they are not pairwise coprime. However, since GCD(6,10,15)=1, they are setwise coprime.
Sample Input 3
3 6 10 16
Sample Output 3
not coprime
GCD(6,10,16)=2, so they are neither pairwise coprime nor setwise coprime.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
縦 H+1 マス横 W マスのマス目があります。
あなたは一番上のいずれかのマスから始めて右か下に一マス移動することを繰り返します。ただし、1 以上 H 以下のそれぞれの整数 i について、グリッドの上から i マス目の左から A_i マス目、A_i + 1 マス目、\ldots、B_i マス目のマスからは下に移動することができません。
1 以上 H 以下のそれぞれの整数 k について、上から k+1 マス目のいずれかのマス目まで移動するための最小の移動回数を求めてください。(出発するマスは各場合について個別に選ぶことができます。) 一番上のどのマスから始めても上から k+1 マス目のいずれのマス目にも移動できない場合、代わりに -1 を出力してください。
制約
- 1 \leq H,W \leq 2\times 10^5
- 1 \leq A_i \leq B_i \leq W
入力
入力は以下の形式で標準入力から与えられる。
H W A_1 B_1 A_2 B_2 : A_H B_H
出力
H 行出力せよ。i 行目には、k=i のときの答えを出力せよ。
入力例 1
4 4 2 4 1 1 2 3 2 4
出力例 1
1 3 6 -1
上から i マス目、左から j マス目のマスをマス (i,j) とします。
k=1 のとき、マス (1,1) → (2,1) のように 1 回で移動できます。
k=2 のとき、マス (1,1) → (2,1) → (2,2) → (3,2) のように 3 回で移動できます。
k=3 のとき、マス (1,1) → (2,1) → (2,2) → (3,2) → (3,3) → (3,4) → (4,4) のように 6 回で移動できます。
k=4 のとき、上から 5 マス目のマスに移動する方法はありません。
Score : 600 points
Problem Statement
There is a grid of squares with H+1 horizontal rows and W vertical columns.
You will start at one of the squares in the top row and repeat moving one square right or down. However, for each integer i from 1 through H, you cannot move down from the A_i-th, (A_i + 1)-th, \ldots, B_i-th squares from the left in the i-th row from the top.
For each integer k from 1 through H, find the minimum number of moves needed to reach one of the squares in the (k+1)-th row from the top. (The starting square can be chosen individually for each case.) If, starting from any square in the top row, none of the squares in the (k+1)-th row can be reached, print -1 instead.
Constraints
- 1 \leq H,W \leq 2\times 10^5
- 1 \leq A_i \leq B_i \leq W
Input
Input is given from Standard Input in the following format:
H W A_1 B_1 A_2 B_2 : A_H B_H
Output
Print H lines. The i-th line should contain the answer for the case k=i.
Sample Input 1
4 4 2 4 1 1 2 3 2 4
Sample Output 1
1 3 6 -1
Let (i,j) denote the square at the i-th row from the top and j-th column from the left.
For k=1, we need one move such as (1,1) → (2,1).
For k=2, we need three moves such as (1,1) → (2,1) → (2,2) → (3,2).
For k=3, we need six moves such as (1,1) → (2,1) → (2,2) → (3,2) → (3,3) → (3,4) → (4,4).
For k=4, it is impossible to reach any square in the fifth row from the top.