Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
縦 2 行、横 2 列のグリッド(各マスが正方形のマス目)があります。
このグリッドは、各マスが黒か白であり、少なくとも 2 つの黒マスを含みます。
各マスの色の情報は文字列 S_1,S_2 として、以下の形式で与えられます。
- 文字列 S_i の j 文字目が
#
であれば上から i マス目、左から j マス目は黒 - 文字列 S_i の j 文字目が
.
であれば上から i マス目、左から j マス目は白
2 つの異なる黒マス同士が辺で接している時、またその時に限りそれら 2 つの黒マスは直接行き来できます。
黒マスのみをいくつか通ることによって、どの 2 つの黒マス同士も(直接または間接的に)行き来できるかどうか判定してください。
制約
- S_1,S_2 は
#
または.
からなる 2 文字の文字列 - S_1,S_2 に
#
が合計で 2 つ以上含まれる
入力
入力は以下の形式で標準入力から与えられる。
S_1 S_2
出力
どの 2 つの黒マス同士も行き来できるなら Yes
、そうでないなら No
と出力せよ。
入力例 1
## .#
出力例 1
Yes
左上の黒マスと右上の黒マス、右上の黒マスと右下の黒マスを直接行き来することができます。
これらの移動を用いてどの黒マスからどの黒マスへも行き来できるので、答えは Yes
となります。
入力例 2
.# #.
出力例 2
No
右上の黒マスと左下の黒マスを行き来することはできません。答えは No
となります。
Score : 100 points
Problem Statement
We have a grid with 2 horizontal rows and 2 vertical columns.
Each of the squares is black or white, and there are at least 2 black squares.
The colors of the squares are given to you as strings S_1 and S_2, as follows.
- If the j-th character of S_i is
#
, the square at the i-th row from the top and j-th column from the left is black. - If the j-th character of S_i is
.
, the square at the i-th row from the top and j-th column from the left is white.
You can travel between two different black squares if and only if they share a side.
Determine whether it is possible to travel from every black square to every black square (directly or indirectly) by only passing black squares.
Constraints
- Each of S_1 and S_2 is a string with two characters consisting of
#
and.
. - S_1 and S_2 have two or more
#
s in total.
Input
Input is given from Standard Input in the following format:
S_1 S_2
Output
If it is possible to travel from every black square to every black square, print Yes
; otherwise, print No
.
Sample Input 1
## .#
Sample Output 1
Yes
It is possible to directly travel between the top-left and top-right black squares and between top-right and bottom-right squares.
These two moves enable us to travel from every black square to every black square, so the answer is Yes
.
Sample Input 2
.# #.
Sample Output 2
No
It is impossible to travel between the top-right and bottom-left black squares, so the answer is No
.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
正整数 A,B が与えられます。
A+B を(十進法で)計算する時、繰り上がりが生じないなら Easy
、生じるなら Hard
と出力してください。
制約
- A,B は整数
- 1 \le A,B \le 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
繰り上がりが生じないなら Easy
、生じるなら Hard
と出力せよ。
入力例 1
229 390
出力例 1
Hard
229+390 を計算する際、十の位から百の位へと繰り上がりが発生します。よって、答えは Hard
です。
入力例 2
123456789 9876543210
出力例 2
Easy
繰り上がりは発生しません。答えは Easy
です。
また、入力が 32bit 整数に収まらないこともあります。
Score : 200 points
Problem Statement
You are given positive integers A and B.
Let us calculate A+B (in decimal). If it does not involve a carry, print Easy
; if it does, print Hard
.
Constraints
- A and B are integers.
- 1 \le A,B \le 10^{18}
Input
Input is given from Standard Input in the following format:
A B
Output
If the calculation does not involve a carry, print Easy
; if it does, print Hard
.
Sample Input 1
229 390
Sample Output 1
Hard
When calculating 229+390, we have a carry from the tens digit to the hundreds digit, so the answer is Hard
.
Sample Input 2
123456789 9876543210
Sample Output 2
Easy
We do not have a carry here; the answer is Easy
.
Note that the input may not fit into a 32-bit integer.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
ピザ屋で働く高橋くんは、まかないとして美味しいチーズピザを作ることにしました。
今、高橋くんの目の前に N 種類のチーズがあります。
i 種類目のチーズは 1 [g] あたりのおいしさが A_i で、 B_i [g] あります。
ピザのおいしさは、ピザに乗せたチーズのおいしさの総和で決まります。
但し、チーズを使いすぎると怒られてしまうため、乗せたチーズの重さは合計で W [g] 以下である必要があります。
この条件のもとで、可能なピザのおいしさの最大値を求めてください。
制約
- 入力は全て整数
- 1 \le N \le 3 \times 10^5
- 1 \le W \le 3 \times 10^8
- 1 \le A_i \le 10^9
- 1 \le B_i \le 1000
入力
入力は以下の形式で標準入力から与えられる。
N W A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを整数として出力せよ。
入力例 1
3 5 3 1 4 2 2 3
出力例 1
15
1 種類目のチーズを 1 [g] 、 2 種類目のチーズを 2 [g] 、 3 種類目のチーズを 2 [g] 乗せるのが最適です。
このとき、ピザのおいしさは 15 となります。
入力例 2
4 100 6 2 1 5 3 9 8 7
出力例 2
100
チーズの重量の総和が W [g] に満たないケースもあります。
入力例 3
10 3141 314944731 649 140276783 228 578012421 809 878510647 519 925326537 943 337666726 611 879137070 306 87808915 39 756059990 244 228622672 291
出力例 3
2357689932073
Score : 300 points
Problem Statement
Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is A_i per gram, and B_i grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.
Constraints
- All values in input are integers.
- 1 \le N \le 3 \times 10^5
- 1 \le W \le 3 \times 10^8
- 1 \le A_i \le 10^9
- 1 \le B_i \le 1000
Input
Input is given from Standard Input in the following format:
N W A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print the answer as an integer.
Sample Input 1
3 5 3 1 4 2 2 3
Sample Output 1
15
The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.
Sample Input 2
4 100 6 2 1 5 3 9 8 7
Sample Output 2
100
There may be less than W grams of cheese in total.
Sample Input 3
10 3141 314944731 649 140276783 228 578012421 809 878510647 519 925326537 943 337666726 611 879137070 306 87808915 39 756059990 244 228622672 291
Sample Output 3
2357689932073
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
X
と .
からなる文字列 S が与えられます。
S に対して、次の操作を 0 回以上 K 回以下行うことができます。
.
をX
に置き換える
操作後に、X
を最大で何個連続させることができますか?
制約
- 1 \leq |S| \leq 2 \times 10^5
- S の各文字は
X
または.
である - 0 \leq K \leq 2 \times 10^5
- K は整数である
入力
入力は以下の形式で標準入力から与えられる。
S K
出力
答えを出力せよ。
入力例 1
XX...X.X.X. 2
出力例 1
5
S の 7 文字目と 9 文字目の .
を X
に置き換えて XX...XXXXX.
とすると、6 文字目から 10 文字目で X
が 5 個連続しています。
X
を 6 個以上連続させることはできないので、答えは 5 です。
入力例 2
XXXX 200000
出力例 2
4
操作を行う回数は 0 回でも構いません。
Score : 400 points
Problem Statement
Given is a string S consisting of X
and .
.
You can do the following operation on S between 0 and K times (inclusive).
- Replace a
.
with anX
.
What is the maximum possible number of consecutive X
s in S after the operations?
Constraints
- 1 \leq |S| \leq 2 \times 10^5
- Each character of S is
X
or.
. - 0 \leq K \leq 2 \times 10^5
- K is an integer.
Input
Input is given from Standard Input in the following format:
S K
Output
Print the answer.
Sample Input 1
XX...X.X.X. 2
Sample Output 1
5
After replacing the X
s at the 7-th and 9-th positions with X
, we have XX...XXXXX.
, which has five consecutive X
s at 6-th through 10-th positions.
We cannot have six or more consecutive X
s, so the answer is 5.
Sample Input 2
XXXX 200000
Sample Output 2
4
It is allowed to do zero operations.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 頂点 M 辺の単純な無向グラフが与えられます。
辺 i は、頂点 A_i と B_i を結んでいます。
頂点 1,2,\ldots,N を順番に消していきます。
なお、頂点 i を消すとは、頂点 i と、頂点 i に接続する全ての辺をグラフから削除することです。
i=1,2,\ldots,N について、頂点 i まで消した時にグラフはいくつの連結成分に分かれていますか?
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq \min(\frac{N(N-1)}{2} , 2 \times 10^5 )
- 1 \leq A_i \lt B_i \leq N
- i \neq j ならば (A_i,B_i) \neq (A_j,B_j)
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
N 行出力せよ。
i 行目には、頂点 i まで消した時のグラフの連結成分の数を出力せよ。
入力例 1
6 7 1 2 1 4 1 5 2 4 2 3 3 5 3 6
出力例 1
1 2 3 2 1 0
グラフは上図のように変化していきます。
入力例 2
8 7 7 8 3 4 5 6 5 7 5 8 6 7 6 8
出力例 2
3 2 2 1 1 1 1 0
はじめからグラフが非連結なこともあります。
Score : 500 points
Problem Statement
Given is an undirected graph with N vertices and M edges.
Edge i connects Vertices A_i and B_i.
We will erase Vertices 1, 2, \ldots, N one by one.
Here, erasing Vertex i means deleting Vertex i and all edges incident to Vertex i from the graph.
For each i=1, 2, \ldots, N, how many connected components does the graph have when vertices up to Vertex i are deleted?
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq \min(\frac{N(N-1)}{2} , 2 \times 10^5 )
- 1 \leq A_i \lt B_i \leq N
- (A_i,B_i) \neq (A_j,B_j) if i \neq j.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
Output
Print N lines.
The i-th line should contain the number of connected components in the graph when vertices up to Vertex i are deleted.
Sample Input 1
6 7 1 2 1 4 1 5 2 4 2 3 3 5 3 6
Sample Output 1
1 2 3 2 1 0
The figure above shows the transition of the graph.
Sample Input 2
8 7 7 8 3 4 5 6 5 7 5 8 6 7 6 8
Sample Output 2
3 2 2 1 1 1 1 0
The graph may be disconnected from the beginning.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
Y
と .
からなる文字列 S が与えられます。
次の操作を 0 回以上 K 回以下行うことができます。
- S の隣り合う 2 文字を入れ替える
操作後に、Y
を最大で何個連続させることができますか?
制約
- 2 \leq |S| \leq 2 \times 10^5
- S の各文字は
Y
または.
である - 0 \leq K \leq 10^{12}
- K は整数である
入力
入力は以下の形式で標準入力から与えられる。
S K
出力
答えを出力せよ。
入力例 1
YY...Y.Y.Y. 2
出力例 1
3
S の 6,7 文字目および 9,10 文字目を入れ替えて YY....YYY..
とすると、7 文字目から 9 文字目で Y
が 3 個連続しています。
Y
を 4 個以上連続させることはできないので、答えは 3 です。
入力例 2
YYYY....YYY 3
出力例 2
4
Score : 600 points
Problem Statement
Given is a string S consisting of Y
and .
.
You can do the following operation on S between 0 and K times (inclusive).
- Swap two adjacent characters in S.
What is the maximum possible number of consecutive Y
s in S after the operations?
Constraints
- 2 \leq |S| \leq 2 \times 10^5
- Each character of S is
Y
or.
. - 0 \leq K \leq 10^{12}
- K is an integer.
Input
Input is given from Standard Input in the following format:
S K
Output
Print the answer.
Sample Input 1
YY...Y.Y.Y. 2
Sample Output 1
3
After swapping the 6-th, 7-th characters, and 9-th, 10-th characters, we have YY....YYY..
, which has three consecutive Y
s at 7-th through 9-th positions.
We cannot have four or more consecutive Y
s, so the answer is 3.
Sample Input 2
YYYY....YYY 3
Sample Output 2
4
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 行 N 列のグリッドがあり、各マスには白い駒が 1 個置かれているか、黒い駒が 1 個置かれているか、何も置かれていないかのいずれかです。
上から i 行目、左から j 列目のマスの状態は S_{i,j} で表され、W
のとき白い駒が置かれていて、B
のとき黒い駒が置かれていて、.
のときは何も置かれていない空マスです。
高橋君とすぬけ君がゲームをします。高橋君からはじめて、交互にターンが回ってきます。
高橋君のターンには、
- 1 つ上に空マスがあるような白い駒を 1 つ選び、上に進める
- 好きな黒い駒を 1 つ食べる
のいずれかの操作をします。
すぬけ君のターンには、
- 1 つ上に空マスがあるような黒い駒を 1 つ選び、上に進める
- 好きな白い駒を 1 つ食べる
のいずれかの操作をします。
操作ができなくなった方が負けとします。両者が最適に行動するとき、どちらが勝ちますか?
なお「駒を上に進める」とは、i 行 j 列目の駒を i-1 行 j 列目に移動させることを指します。
高橋君とすぬけ君は同じ向きから盤面を見ていて、「上」というのは両者にとって同じ向きであることに注意してください。
制約
- 1 \leq N \leq 8
- N は整数
- S_{i,j} は
W
またはB
または.
である
入力
入力は以下の形式で標準入力から与えられる。
N S_{1,1}S_{1,2}\ldots S_{1,N} S_{2,1}S_{2,2}\ldots S_{2,N} \vdots S_{N,1}S_{N,2}\ldots S_{N,N}
出力
高橋君が勝つならば Takahashi
と、すぬけ君が勝つならば Snuke
と出力せよ。
入力例 1
3 BB. .B. ...
出力例 1
Takahashi
はじめに高橋君が 1 行 1 列目の黒い駒を食べると、盤面は下のようになります。
.B. .B. ...
このときすぬけ君は操作を行うことができないので、高橋君の勝ちです。
盤面の外に駒を動かすことや、他の駒があるマスに駒を移動させることはできないことに注意してください。
入力例 2
2 .. WW
出力例 2
Snuke
入力例 3
4 WWBW WWWW BWB. BBBB
出力例 3
Snuke
Score : 600 points
Problem Statement
There is a grid with N rows and N columns, where each square has one white piece, one black piece, or nothing on it.
The square at the i-th row from the top and j-th column from the left is described by S_{i,j}. If S_{i,j} is W
, the square has a white piece; if S_{i,j} is B
, it has a black piece; if S_{i,j} is .
, it is empty.
Takahashi and Snuke will play a game, where the players take alternate turns, with Takahashi going first.
In Takahashi's turn, he does one of the following operations.
- Choose a white piece that can move one square up to an empty square, and move it one square up (see below).
- Eat a black piece of his choice.
In Snuke's turn, he does one of the following operations.
- Choose a black piece that can move one square up to an empty square, and move it one square up.
- Eat a white piece of his choice.
The player who becomes unable to do the operation loses the game. Which player will win when both players play optimally?
Here, moving a piece one square up means moving a piece at the i-th row and j-th column to the (i-1)-th row and j-th column.
Note that this is the same for both players; they see the board from the same direction.
Constraints
- 1 \leq N \leq 8
- N is an integer.
- S_{i,j} is
W
,B
, or.
.
Input
Input is given from Standard Input in the following format:
N S_{1,1}S_{1,2}\ldots S_{1,N} S_{2,1}S_{2,2}\ldots S_{2,N} \vdots S_{N,1}S_{N,2}\ldots S_{N,N}
Output
If Takahashi will win, print Takahashi
; if Snuke will win, print Snuke
.
Sample Input 1
3 BB. .B. ...
Sample Output 1
Takahashi
If Takahashi eats the black piece at the 1-st row and 1-st columns, the board will become:
.B. .B. ...
Then, Snuke cannot do an operation, making Takahashi win.
Note that it is forbidden to move a piece out of the board or to a square occupied by another piece.
Sample Input 2
2 .. WW
Sample Output 2
Snuke
Sample Input 3
4 WWBW WWWW BWB. BBBB
Sample Output 3
Snuke