Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
<
, =
, >
のみからなる文字列 S が与えられます。
S が 双方向矢印型 の文字列であるか判定してください。
ただし、文字列 S が双方向矢印型の文字列であるとは、
ある正整数 k が存在して、
S が 1 個の <
、k 個の =
、1 個の >
をこの順に連結した長さ (k+2) の文字列であることをいいます。
制約
- S は
<
,=
,>
のみからなる長さ 3 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S が 双方向矢印型 の文字列ならば Yes
を、そうでないならば No
を出力せよ。
入力例 1
<====>
出力例 1
Yes
<====>
は、1 個の <
、4 個の =
、1 個の >
をこの順に連結した文字列であり、双方向矢印型の文字列です。
よって、Yes
を出力します。
入力例 2
==>
出力例 2
No
==>
は双方向矢印型の文字列の条件をみたしていません。
よって、No
を出力します。
入力例 3
<>>
出力例 3
No
Scoring: 100 points
Problem Statement
You are given a string S consisting of <
, =
, and >
.
Determine whether S is a bidirectional arrow string.
A string S is a bidirectional arrow string if and only if there is a positive integer k such that S is a concatenation of one <
, k =
s, and one >
, in this order, with a length of (k+2).
Constraints
- S is a string of length between 3 and 100, inclusive, consisting of
<
,=
, and>
.
Input
The input is given from Standard Input in the following format:
S
Output
If S is a bidirectional arrow string, print Yes
; otherwise, print No
.
Sample Input 1
<====>
Sample Output 1
Yes
<====>
is a concatenation of one <
, four =
s, and one >
, in this order, so it is a bidirectional arrow string.
Hence, print Yes
.
Sample Input 2
==>
Sample Output 2
No
==>
does not meet the condition for a bidirectional arrow string.
Hence, print No
.
Sample Input 3
<>>
Sample Output 3
No
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
-10^{18} 以上 10^{18} 以下の整数 X が与えられるので、\left\lceil \dfrac{X}{10} \right\rceil を出力してください。
ここで、\left\lceil a \right\rceil は a 以上の整数のうち最小のものを意味します。
制約
- -10^{18} \leq X \leq 10^{18}
- X は整数
入力
入力は以下の形式で標準入力から与えられる。
X
出力
\left\lceil \dfrac{X}{10} \right\rceil を整数として出力せよ。
入力例 1
27
出力例 1
3
\frac{27}{10} = 2.7 以上の整数は 3, 4, 5, \dots です。この中で一番小さい整数は 3 なので、\left \lceil \frac{27}{10} \right \rceil = 3 となります。
入力例 2
-13
出力例 2
-1
\frac{-13}{10} = -1.3 以上の整数は、全ての正整数および 0, -1 です。この中で一番小さい整数は -1 なので、\left \lceil \frac{-13}{10} \right \rceil = -1 となります。
入力例 3
40
出力例 3
4
\frac{40}{10} = 4 以上の整数で一番小さい整数は 4 自身です。
入力例 4
-20
出力例 4
-2
入力例 5
123456789123456789
出力例 5
12345678912345679
Score: 200 points
Problem Statement
Given an integer X between -10^{18} and 10^{18}, inclusive, print \left\lceil \dfrac{X}{10} \right\rceil.
Here, \left\lceil a \right\rceil denotes the smallest integer not less than a.
Constraints
- -10^{18} \leq X \leq 10^{18}
- X is an integer.
Input
The input is given from Standard Input in the following format:
X
Output
Print \left\lceil \dfrac{X}{10} \right\rceil as an integer.
Sample Input 1
27
Sample Output 1
3
The integers not less than \frac{27}{10} = 2.7 are 3, 4, 5, \dots. Among these, the smallest is 3, so \left \lceil \frac{27}{10} \right \rceil = 3.
Sample Input 2
-13
Sample Output 2
-1
The integers not less than \frac{-13}{10} = -1.3 are all positive integers, 0, and -1. Among these, the smallest is -1, so \left \lceil \frac{-13}{10} \right \rceil = -1.
Sample Input 3
40
Sample Output 3
4
The smallest integer not less than \frac{40}{10} = 4 is 4 itself.
Sample Input 4
-20
Sample Output 4
-2
Sample Input 5
123456789123456789
Sample Output 5
12345678912345679
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 350 点
問題文
文字列 S が与えられます。次の操作を ちょうど 1 回 行った後の文字列としてあり得るものがいくつあるか求めてください。
- S の長さを N とする。 1\leq i<j\leq N をみたす整数の組 (i,j) を選び、S の i 文字目と j 文字目を入れ替える。
なお、この問題の制約下で操作を必ず行うことができることが証明できます。
制約
- S は英小文字からなる長さ 2 以上 10^6 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S に対して問題文中の操作をちょうど 1 回行った後の文字列としてあり得るものの個数を出力せよ。
入力例 1
abc
出力例 1
3
S の長さは 3 であるため、1\leq i<j\leq 3 をみたす整数の組 (i,j) としては、 (1,2), (1,3), (2,3) の 3 通りが考えられます。
- S の 1 文字目と 2 文字目を入れ替えた時、S は
bac
となります。 - S の 1 文字目と 3 文字目を入れ替えた時、S は
cba
となります。 - S の 2 文字目と 3 文字目を入れ替えた時、S は
acb
となります。
よって、abc
に対して操作を行った後の文字列としては、bac
, cba
, acb
の 3 つがあり得るため、3 を出力します。
入力例 2
aaaaa
出力例 2
1
どの 2 つの文字を入れ替えても S は aaaaa
のままです。よって、操作後の文字列としてあり得るものは 1 つです。
Points: 350 points
Problem Statement
You are given a string S. Find the number of strings that can result from performing the following operation exactly once.
- Let N be the length of S. Choose a pair of integers (i,j) such that 1\leq i<j\leq N and swap the i-th and j-th characters of S.
It can be proved that you can always perform it under the constraints of this problem.
Constraints
- S is a string of length between 2 and 10^6, inclusive, consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Print the number of strings that can result from performing the operation in the problem statement exactly once on S.
Sample Input 1
abc
Sample Output 1
3
The length of S is 3, so 1\leq i<j\leq 3 is satisfied by three pairs of integers (i,j): (1,2), (1,3), and (2,3).
- Swapping the 1-st and 2-nd characters of S results in S being
bac
. - Swapping the 1-st and 3-rd characters of S results in S being
cba
. - Swapping the 2-nd and 3-rd characters of S results in S being
acb
.
Therefore, the operation on abc
results in one of the three strings: bac
, cba
, and acb
, so print 3.
Sample Input 2
aaaaa
Sample Output 2
1
Swapping any two characters results in S remaining aaaaa
. Thus, only one string can result from the operation.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 450 点
問題文
一辺の長さが 1 のマスからなる H 行 W 列のマス目と、N 枚のタイルがあります。
i (1\leq i\leq N) 枚目のタイルは A_i\times B_i の長方形です。
以下の条件をすべてみたすようにタイルをマス目に置くことができるか判定してください。
- 全てのマスがちょうど 1 枚のタイルで覆われている。
- 使用されないタイルがあっても良い。
- 使用するタイルは 回転したり裏返したりして置かれていても良い。ただし、各タイルはマスの線に合わせてマス目からはみ出ることがないように置かれていなければならない。
制約
- 1\leq N\leq 7
- 1 \leq H,W \leq 10
- 1\leq A_i,B_i\leq 10
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N H W A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
問題文中の条件をみたすようにタイルをマス目に置くことができるならば Yes
を、そうでないならば No
を出力せよ。
入力例 1
5 5 5 1 1 3 3 4 4 2 3 2 5
出力例 1
Yes
2,4,5 枚目のタイルを使用して次のように置くと、マス目の各マスをちょうど 1 枚のタイルで覆うことができます。
よって、Yes
を出力します。
入力例 2
1 1 2 2 3
出力例 2
No
マス目からはみ出さないようにタイルを置くことはできません。
よって、No
を出力します。
入力例 3
1 2 2 1 1
出力例 3
No
全てのマスを覆うようにタイルを置くことができません。
よって、No
を出力します。
入力例 4
5 3 3 1 1 2 2 2 2 2 2 2 2
出力例 4
No
全てのマスはちょうど 1 枚のタイルで覆われている必要があることに注意してください。
Score: 450 points
Problem Statement
There is a grid of H rows and W columns, each cell having a side length of 1, and we have N tiles.
The i-th tile (1\leq i\leq N) is a rectangle of size A_i\times B_i.
Determine whether it is possible to place the tiles on the grid so that all of the following conditions are satisfied:
- Every cell is covered by exactly one tile.
- It is fine to have unused tiles.
- The tiles may be rotated or flipped when placed. However, each tile must be aligned with the edges of the cells without extending outside the grid.
Constraints
- 1\leq N\leq 7
- 1 \leq H,W \leq 10
- 1\leq A_i,B_i\leq 10
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H W A_1 B_1 A_2 B_2 \ldots A_N B_N
Output
If it is possible to place the tiles on the grid so that all of the conditions in the problem statement are satisfied, print Yes
; otherwise, print No
.
Sample Input 1
5 5 5 1 1 3 3 4 4 2 3 2 5
Sample Output 1
Yes
Placing the 2-nd, 4-th, and 5-th tiles as shown below covers every cell of the grid by exactly one tile.
Hence, print Yes
.
Sample Input 2
1 1 2 2 3
Sample Output 2
No
It is impossible to place the tile without letting it extend outside the grid.
Hence, print No
.
Sample Input 3
1 2 2 1 1
Sample Output 3
No
It is impossible to cover all cells with the tile.
Hence, print No
.
Sample Input 4
5 3 3 1 1 2 2 2 2 2 2 2 2
Sample Output 4
No
Note that each cell must be covered by exactly one tile.
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 525 点
問題文
N 個のボールが左右一列に並んでいます。
左から i (1\leq i\leq N) 番目のボールは色 C_i で、価値は V_i です。
高橋君はこの列から ちょうど K 個のボールを取り除いたうえで、 残ったボールを元の順番で並べたときに同じ色のボールが隣り合わないようにしたいと考えています。 また、その条件のもとで、列に残ったボールの価値の総和をなるべく大きくしたいと考えています。
高橋君が、残ったボールの列において同じ色のボールが隣り合わないように K 個のボールを取り除くことができるか判定し、 できる場合は列に残ったボールの価値の総和としてあり得る最大の値を求めてください。
制約
- 1\leq K<N\leq 2\times 10^5
- K\leq 500
- 1\leq C_i\leq N
- 1\leq V_i\leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K C_1 V_1 C_2 V_2 \vdots C_N V_N
出力
高橋君が同じ色のボールが隣り合わないようにK 個のボールを取り除くことができる場合は、 列に残ったボールの価値の総和としてあり得る最大値を整数で出力せよ。 できない場合は、-1 を出力せよ。
入力例 1
5 2 1 1 3 5 3 3 1 4 1 2
出力例 1
10
左から、3,5 番目のボールを取り除くと、残ったボールは左から順に色 1,3,1 であるため、
どの隣り合う 2 つのボールの色も異なり、条件をみたしています。
このとき、列に残ったボールの価値の和は V_1+V_2+V_4=1+5+4=10 です。
他にも 5 つのボールから 2 つのボールを取り除く方法であって、同じ色のボールが隣り合わないようにできるものは存在しますが、
3,5 番目のボールを取り除いた時に残ったボールの価値の和は最大となります。
よって、10 を出力します。
入力例 2
3 1 1 10 1 10 1 10
出力例 2
-1
どのようにボールを 1 つ取り除いても色 1 のボールが隣り合ってしまいます。
よって、 -1 を出力します。
入力例 3
3 1 1 1 2 2 3 3
出力例 3
5
必ずちょうど K 個のボールを取り除く必要があることに注意してください。
Score: 525 points
Problem Statement
There are N balls lined up in a row.
The i-th ball from the left is of color C_i and has a value of V_i.
Takahashi wants to remove exactly K balls from this row so that no two adjacent balls have the same color when arranging the remaining balls without changing the order. Additionally, under that condition, he wants to maximize the total value of the balls remaining in the row.
Determine if Takahashi can remove K balls so that no two adjacent balls in the remaining row have the same color. If it is possible, find the maximum possible total value of the remaining balls.
Constraints
- 1\leq K<N\leq 2\times 10^5
- K\leq 500
- 1\leq C_i\leq N
- 1\leq V_i\leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K C_1 V_1 C_2 V_2 \vdots C_N V_N
Output
If Takahashi can remove K balls so that no two adjacent balls in the remaining row have the same color, print the maximum possible total value of the remaining balls as an integer. Otherwise, print -1.
Sample Input 1
5 2 1 1 3 5 3 3 1 4 1 2
Sample Output 1
10
After removing the 3-rd and 5-th balls from the left, the remaining balls are of colors 1, 3, 1 from left to right, so no two adjacent balls have the same color, satisfying the condition.
The total value of the remaining balls is V_1+V_2+V_4=1+5+4=10.
There are other ways to remove two balls from the five balls so that no two adjacent balls have the same color, but the total value of the remaining balls is maximized when removing the 3-rd and 5-th balls.
Hence, print 10.
Sample Input 2
3 1 1 10 1 10 1 10
Sample Output 2
-1
No matter how you remove one ball, balls of color 1 will end up next to each other.
Hence, print -1.
Sample Input 3
3 1 1 1 2 2 3 3
Sample Output 3
5
Note that exactly K balls must be removed.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
頂点に 1 から N の、辺に 1 から M の番号がついた N 頂点 M 辺の単純グラフがあります。辺 i は頂点 u_i と頂点 v_i を結んでいます。
各頂点にはランプが 1 個ずつ載っています。はじめ、全てのランプは消えています。
以下の操作を 0 回以上 M 回以下行うことで、ランプがちょうど K 個ついた状態にできるかどうかを判定してください。
- 辺を 1 本選ぶ。辺の両端点を u, v とする。u, v に載っているランプの状態を反転させる。つまり、ランプがついていたら消して、消えていたらつける。
また、ちょうど K 個のランプがついた状態にすることが可能な場合は、そのような操作の手順を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq \min\left( 2 \times 10^5, \frac{N(N-1)}{2} \right)
- 0 \leq K \leq N
- 1 \leq u_i \lt v_i \leq N
- 入力で与えられるグラフは単純
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
ちょうど K 個のランプがついた状態にすることが不可能な場合は No
を出力せよ。
可能な場合はまず Yes
を出力して、その後に操作の手順を以下の形式で出力せよ。
X e_1 e_2 \dots e_X
ここで、X は操作回数を、e_i は i 番目の操作で選ぶ辺の番号を意味する。これらは次を満たす必要がある。
- 0 \leq X \leq M
- 1 \leq e_i \leq M
条件を満たす操作の手順が複数ある場合は、どれを出力しても正解とみなされる。
入力例 1
5 5 4 1 2 1 3 2 4 3 5 1 5
出力例 1
Yes 3 3 4 5
出力例に従って操作を行うと次のようになります。
- 辺 3 を選ぶ。頂点 2 と頂点 4 に載っているランプをつける。
- 辺 4 を選ぶ。頂点 3 と頂点 5 に載っているランプをつける。
- 辺 5 を選ぶ。頂点 1 に載っているランプをつけて、頂点 5 に載っているランプを消す。
操作を全て終了した時点で頂点 1,2,3,4 に載っているランプがついています。よってこの操作の手順は条件を満たしています。
条件を満たす操作の手順としては他に X = 4, (e_1,e_2,e_3,e_4) = (3,4,3,1) などが挙げられます。(同じ辺を 2 回以上選んでもよいです。)
入力例 2
5 5 5 1 2 1 3 2 4 3 5 1 5
出力例 2
No
入力例 3
10 10 6 2 5 2 6 3 5 3 8 4 6 4 8 5 9 6 7 6 10 7 9
出力例 3
Yes 3 10 9 6
Score: 550 points
Problem Statement
There is a simple graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertices u_i and v_i.
Each vertex has one lamp on it. Initially, all the lamps are off.
Determine whether it is possible to turn exactly K lamps on by performing the following operation between 0 and M times, inclusive.
- Choose one edge. Let u and v be the endpoints of the edge. Toggle the states of the lamps on u and v. That is, if the lamp is on, turn it off, and vice versa.
If it is possible to turn exactly K lamps on, print a sequence of operations that achieves this state.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq \min\left( 2 \times 10^5, \frac{N(N-1)}{2} \right)
- 0 \leq K \leq N
- 1 \leq u_i < v_i \leq N
- The given graph is simple.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M K u_1 v_1 u_2 v_2 \vdots u_M v_M
Output
If it is impossible to turn exactly K lamps on, print No
.
Otherwise, first print Yes
, and then print a sequence of operations in the following format:
X e_1 e_2 \dots e_X
Here, X is the number of operations, and e_i is the number of the edge chosen in the i-th operation. These must satisfy the following:
- 0 \leq X \leq M
- 1 \leq e_i \leq M
If multiple sequences of operations satisfy the conditions, any of them will be considered correct.
Sample Input 1
5 5 4 1 2 1 3 2 4 3 5 1 5
Sample Output 1
Yes 3 3 4 5
If we operate according to the sample output, it will go as follows:
- Choose edge 3. Turn on the lamps on vertex 2 and vertex 4.
- Choose edge 4. Turn on the lamps on vertex 3 and vertex 5.
- Choose edge 5. Turn on the lamp on vertex 1 and turn off the lamp on vertex 5.
After completing all operations, the lamps on vertices 1, 2, 3, and 4 are on. Therefore, this sequence of operations satisfies the conditions.
Other possible sequences of operations that satisfy the conditions include X = 4, (e_1,e_2,e_3,e_4) = (3,4,3,1). (It is allowed to choose the same edge more than once.)
Sample Input 2
5 5 5 1 2 1 3 2 4 3 5 1 5
Sample Output 2
No
Sample Input 3
10 10 6 2 5 2 6 3 5 3 8 4 6 4 8 5 9 6 7 6 10 7 9
Sample Output 3
Yes 3 10 9 6
Time Limit: 12 sec / Memory Limit: 1024 MB
配点 : 675 点
問題文
マス 0, マス 1, \dots, マス N の N+1 個のマスからなるスゴロクがあります。
また、1 以上 K 以下の整数が等確率で出るサイコロがあります。
はじめ、あなたはマス 0 にいます。あなたはマス N に着くまで次の操作を繰り返します。
- サイコロを振る。今いるマスを x 、サイコロで出た整数を y としてマス \min(N, x + y) に移動する。
ちょうど i 回の操作によってマス N に着く確率を P_i とします。P_1, P_2, \dots, P_N を \text{mod }998244353 で計算してください。
確率 \text{mod }998244353 とは
求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。制約
- 1 \leq K \leq N \leq 2 \times 10^5
- N, K は整数
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
N 行出力せよ。i 行目には P_i を \text{mod }998244353 で出力せよ。
入力例 1
3 2
出力例 1
0 249561089 748683265
例えば、ちょうど 2 回の操作でマス N に辿り着くのは以下の整数がサイコロで出たときです。
- 1 回目の操作で 1 が出て、2 回目の操作で 2 が出る
- 1 回目の操作で 2 が出て、2 回目の操作で 1 が出る
- 1 回目の操作で 2 が出て、2 回目の操作で 2 が出る
よって P_2 = \left( \frac{1}{2} \times \frac{1}{2} \right) \times 3 = \frac{3}{4} です。249561089 \times 4 \equiv 3 \pmod{998244353} なので 249561089 を P_2 として出力します。
入力例 2
5 5
出力例 2
598946612 479157290 463185380 682000542 771443236
入力例 3
10 6
出力例 3
0 166374059 207967574 610038216 177927813 630578223 902091444 412046453 481340945 404612686
Score: 675 points
Problem Statement
There is a board game with N+1 squares: square 0, square 1, \dots, square N.
You have a die (dice) that rolls an integer between 1 and K, inclusive, with equal probability for each outcome.
You start on square 0. You repeat the following operation until you reach square N:
- Roll the dice. Let x be the current square and y be the rolled number, then move to square \min(N, x + y).
Let P_i be the probability of reaching square N after exactly i operations. Calculate P_1, P_2, \dots, P_N modulo 998244353.
What is probability modulo 998244353?
It can be proved that the sought probabilities will always be rational numbers. Under the constraints of this problem, it can also be proved that when expressing the values as \frac{P}{Q} using two coprime integers P and Q, there is exactly one integer R satisfying R \times Q \equiv P\pmod{998244353} and 0 \leq R < 998244353. Find this R.Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- N and K are integers.
Input
The input is given from Standard Input in the following format:
N K
Output
Print N lines. The i-th line should contain P_i modulo 998244353.
Sample Input 1
3 2
Sample Output 1
0 249561089 748683265
For example, you reach square N after exactly two operations when the die rolls the following numbers:
- A 1 on the first operation, and a 2 on the second operation.
- A 2 on the first operation, and a 1 on the second operation.
- A 2 on the first operation, and a 2 on the second operation.
Therefore, P_2 = \left( \frac{1}{2} \times \frac{1}{2} \right) \times 3 = \frac{3}{4}. We have 249561089 \times 4 \equiv 3 \pmod{998244353}, so print 249561089 for P_2.
Sample Input 2
5 5
Sample Output 2
598946612 479157290 463185380 682000542 771443236
Sample Input 3
10 6
Sample Output 3
0 166374059 207967574 610038216 177927813 630578223 902091444 412046453 481340945 404612686