Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
高橋君はとあるWebサービスに会員登録しようとしています。
まずIDを S として登録しようとしました。しかし、このIDは既に他のユーザーによって使用されていました。
そこで、高橋君は S の末尾に 1 文字追加した文字列をIDとして登録することを考えました。
高橋君は新しくIDを T として登録しようとしています。これが前述の条件を満たすか判定してください。
制約
- S, T は英小文字列
- 1 \leq |S| \leq 10
- |T| = |S| + 1
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
T が問の条件を満たすならば Yes
と、そうでないならば No
と出力せよ。
入力例 1
chokudai chokudaiz
出力例 1
Yes
chokudaiz
は chokudai
の末尾に z
を追加して得られる文字列です。
入力例 2
snuke snekee
出力例 2
No
snekee
は snuke
の末尾に英小文字を 1 文字追加して得られる文字列ではありません。
入力例 3
a aa
出力例 3
Yes
Score : 100 points
Problem Statement
Takahashi wants to be a member of some web service.
He tried to register himself with the ID S, which turned out to be already used by another user.
Thus, he decides to register using a string obtained by appending one character at the end of S as his ID.
He is now trying to register with the ID T. Determine whether this string satisfies the property above.
Constraints
- S and T are strings consisting of lowercase English letters.
- 1 \leq |S| \leq 10
- |T| = |S| + 1
Input
Input is given from Standard Input in the following format:
S T
Output
If T satisfies the property in Problem Statement, print Yes
; otherwise, print No
.
Sample Input 1
chokudai chokudaiz
Sample Output 1
Yes
chokudaiz
can be obtained by appending z
at the end of chokudai
.
Sample Input 2
snuke snekee
Sample Output 2
No
snekee
cannot be obtained by appending one character at the end of snuke
.
Sample Input 3
a aa
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
1 が書かれたカードが A 枚、0 が書かれたカードが B 枚、 -1 が書かれたカードが C 枚あります。
これらのカードから、ちょうど K 枚を選んで取るとき、取ったカードに書かれた数の和として、 ありうる値の最大値はいくつですか。
制約
- 入力は全て整数である。
- 0 \leq A, B, C
- 1 \leq K \leq A + B + C \leq 2 \times 10^9
入力
入力は以下の形式で標準入力から与えられる。
A B C K
出力
和としてありうる値の最大値を出力せよ。
入力例 1
2 1 1 3
出力例 1
2
1 が書かれたカードを 2 枚、0 が書かれたカードを 1 枚取ることを考えます。 このときカードに書かれた数の和は 2 になり、和としてありうる値の最大値になります。
入力例 2
1 2 3 4
出力例 2
0
入力例 3
2000000000 0 0 2000000000
出力例 3
2000000000
Score : 200 points
Problem Statement
We have A cards, each of which has an integer 1 written on it. Similarly, we also have B cards with 0s and C cards with -1s.
We will pick up K among these cards. What is the maximum possible sum of the numbers written on the cards chosen?
Constraints
- All values in input are integers.
- 0 \leq A, B, C
- 1 \leq K \leq A + B + C \leq 2 \times 10^9
Input
Input is given from Standard Input in the following format:
A B C K
Output
Print the maximum possible sum of the numbers written on the cards chosen.
Sample Input 1
2 1 1 3
Sample Output 1
2
Consider picking up two cards with 1s and one card with a 0. In this case, the sum of the numbers written on the cards is 2, which is the maximum possible value.
Sample Input 2
1 2 3 4
Sample Output 2
0
Sample Input 3
2000000000 0 0 2000000000
Sample Output 3
2000000000
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
競技プログラミングを始めた高橋くんは、学びたいアルゴリズムが M 個あります。 最初、各アルゴリズムの理解度は 0 です。
高橋くんが書店に行くと、N 冊の参考書が売っていました。i 番目の参考書 (1\leq i\leq N) は C_i 円で売られていて、購入して読むことで、各 j (1\leq j\leq M) について j 番目のアルゴリズムの理解度が A_{i,j} 上がります。 また、それ以外の方法で理解度を上げることはできません。
高橋くんの目標は M 個すべてのアルゴリズムの理解度を X 以上にすることです。高橋くんが目標を達成することが可能か判定し、可能な場合は目標を達成するのに必要な金額の最小値を計算してください。
制約
- 入力はすべて整数
- 1\leq N, M\leq 12
- 1\leq X\leq 10^5
- 1\leq C_i \leq 10^5
- 0\leq A_{i, j} \leq 10^5
入力
入力は以下の形式で標準入力から与えられる。
N M X C_1 A_{1,1} A_{1,2} \cdots A_{1,M} C_2 A_{2,1} A_{2,2} \cdots A_{2,M} \vdots C_N A_{N,1} A_{N,2} \cdots A_{N,M}
出力
高橋くんが目標を達成できないならば -1
を、
そうでなければ目標を達成するのに必要な金額の最小値を出力せよ。
入力例 1
3 3 10 60 2 2 4 70 8 7 9 50 2 3 9
出力例 1
120
2, 3 番目の参考書を購入すると 120 円ですべてのアルゴリズムの理解度を 10 以上にすることができ、これが最小値です。
入力例 2
3 3 10 100 3 1 4 100 1 5 9 100 2 6 5
出力例 2
-1
すべての参考書を購入しても 1 つ目のアルゴリズムの理解度が 10 に達しません。
入力例 3
8 5 22 100 3 7 5 3 1 164 4 5 2 7 8 334 7 2 7 2 9 234 4 7 2 8 2 541 5 4 3 3 6 235 4 8 6 9 7 394 3 6 1 6 2 872 8 4 3 7 2
出力例 3
1067
Score : 300 points
Problem
Takahashi, who is a novice in competitive programming, wants to learn M algorithms. Initially, his understanding level of each of the M algorithms is 0.
Takahashi is visiting a bookstore, where he finds N books on algorithms. The i-th book (1\leq i\leq N) is sold for C_i yen (the currency of Japan). If he buys and reads it, his understanding level of the j-th algorithm will increase by A_{i,j} for each j (1\leq j\leq M). There is no other way to increase the understanding levels of the algorithms.
Takahashi's objective is to make his understanding levels of all the M algorithms X or higher. Determine whether this objective is achievable. If it is achievable, find the minimum amount of money needed to achieve it.
Constraints
- All values in input are integers.
- 1\leq N, M\leq 12
- 1\leq X\leq 10^5
- 1\leq C_i \leq 10^5
- 0\leq A_{i, j} \leq 10^5
Input
Input is given from Standard Input in the following format:
N M X C_1 A_{1,1} A_{1,2} \cdots A_{1,M} C_2 A_{2,1} A_{2,2} \cdots A_{2,M} \vdots C_N A_{N,1} A_{N,2} \cdots A_{N,M}
Output
If the objective is not achievable, print -1
; otherwise, print the minimum amount of money needed to achieve it.
Sample Input 1
3 3 10 60 2 2 4 70 8 7 9 50 2 3 9
Sample Output 1
120
Buying the second and third books makes his understanding levels of all the algorithms 10 or higher, at the minimum cost possible.
Sample Input 2
3 3 10 100 3 1 4 100 1 5 9 100 2 6 5
Sample Output 2
-1
Buying all the books is still not enough to make his understanding levels of all the algorithms 10 or higher.
Sample Input 3
8 5 22 100 3 7 5 3 1 164 4 5 2 7 8 334 7 2 7 2 9 234 4 7 2 8 2 541 5 4 3 3 6 235 4 8 6 9 7 394 3 6 1 6 2 872 8 4 3 7 2
Sample Output 3
1067
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 400 点
問題文
高橋王国には N 個の町があります。町は 1 から N まで番号が振られています。
それぞれの町にはテレポーターが 1 台ずつ設置されています。町 i (1 \leq i \leq N) のテレポーターの転送先は町 A_i です。
高橋王は正の整数 K が好きです。わがままな高橋王は、町 1 から出発してテレポーターをちょうど K 回使うと、どの町に到着するかが知りたいです。
高橋王のために、これを求めるプログラムを作成してください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 1 \leq K \leq 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
町 1 から出発してテレポーターをちょうど K 回使ったとき到着する町の番号を出力せよ。
入力例 1
4 5 3 2 4 1
出力例 1
4
町 1 から出発してテレポーターを 5 回使うと、1 \to 3 \to 4 \to 1 \to 3 \to 4 と移動します。
入力例 2
6 727202214173249351 6 5 2 5 3 2
出力例 2
2
Score: 400 points
Problem Statement
The Kingdom of Takahashi has N towns, numbered 1 through N.
There is one teleporter in each town. The teleporter in Town i (1 \leq i \leq N) sends you to Town A_i.
Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there.
Help the king by writing a program that answers this question.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 1 \leq K \leq 10^{18}
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the integer representing the town the king will be in if he starts at Town 1 and uses a teleporter exactly K times from there.
Sample Input 1
4 5 3 2 4 1
Sample Output 1
4
If we start at Town 1 and use the teleporter 5 times, our travel will be as follows: 1 \to 3 \to 4 \to 1 \to 3 \to 4.
Sample Input 2
6 727202214173249351 6 5 2 5 3 2
Sample Output 2
2
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個のブロックが横一列に並んでいます。このブロック列に色を塗ります。
2 つのブロック列の塗り方が異なるとは、あるブロックが存在して、そのブロックが異なる色で塗られていることと定義します。
次の条件を満たすブロック列の塗り方が何通りあるか求めてください。
- 各ブロックを色 1 から色 M までのいずれか一色で塗る。使わない色があってもよい。
- 隣り合うブロックの組であって同じ色で塗られている組は、 K 組以下である。
ただし、答えは非常に大きくなる場合があるので、 998244353 で割った余りを出力してください。
制約
- 入力は全て整数
- 1 \leq N, M \leq 2 \times 10^5
- 0 \leq K \leq N - 1
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを出力せよ。
入力例 1
3 2 1
出力例 1
6
ブロック列の塗り方を色を書き並べた文字列で表すと、条件を満たすブロック列の色の塗り方は、112
, 121
, 122
, 211
, 212
, 221
です。
入力例 2
100 100 0
出力例 2
73074801
入力例 3
60522 114575 7559
出力例 3
479519525
Score : 500 points
Problem Statement
There are N blocks arranged in a row. Let us paint these blocks.
We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.
Find the number of ways to paint the blocks under the following conditions:
- For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.
- There may be at most K pairs of adjacent blocks that are painted in the same color.
Since the count may be enormous, print it modulo 998244353.
Constraints
- All values in input are integers.
- 1 \leq N, M \leq 2 \times 10^5
- 0 \leq K \leq N - 1
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
3 2 1
Sample Output 1
6
The following ways to paint the blocks satisfy the conditions: 112
, 121
, 122
, 211
, 212
, and 221
. Here, digits represent the colors of the blocks.
Sample Input 2
100 100 0
Sample Output 2
73074801
Sample Input 3
60522 114575 7559
Sample Output 3
479519525
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
以下のいずれかの条件を満たす文字列を括弧列と定義します。
- 空文字列
- ある括弧列 A が存在して、
(
, A,)
をこの順に連結した文字列 - ある空でない括弧列 A, B が存在して、A, B をこの順に連結した文字列
N 個の文字列 S_i が与えられます。S_i 全てを好きな順序で連結するとき、括弧列を構成することはできますか。
制約
- 1 \leq N \leq 10^6
- S_i の文字列長の合計は 10^6 以下
- S_i は
(
,)
のみからなる空でない文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 : S_N
出力
S_i を任意の順序で連結するとき、括弧列を構成できるなら Yes
、できないなら No
を出力せよ。
入力例 1
2 ) (()
出力例 1
Yes
(()
, )
の順に連結すると括弧列になります。
入力例 2
2 )( ()
出力例 2
No
入力例 3
4 ((())) (((((( )))))) ()()()
出力例 3
Yes
入力例 4
3 ((( ) )
出力例 4
No
Score : 600 points
Problem Statement
A bracket sequence is a string that is one of the following:
- An empty string;
- The concatenation of
(
, A, and)
in this order, for some bracket sequence A ; - The concatenation of A and B in this order, for some non-empty bracket sequences A and B /
Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?
Constraints
- 1 \leq N \leq 10^6
- The total length of the strings S_i is at most 10^6.
- S_i is a non-empty string consisting of
(
and)
.
Input
Input is given from Standard Input in the following format:
N S_1 : S_N
Output
If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes
; otherwise, print No
.
Sample Input 1
2 ) (()
Sample Output 1
Yes
Concatenating (()
and )
in this order forms a bracket sequence.
Sample Input 2
2 )( ()
Sample Output 2
No
Sample Input 3
4 ((())) (((((( )))))) ()()()
Sample Output 3
Yes
Sample Input 4
3 ((( ) )
Sample Output 4
No