実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
2 次元グリッド上に 2 つの図形 S と T があります。グリッドは正方形のマスからなります。
S は N 行 N 列のグリッド内にあり、S_{i,j} が # であるようなマス全体からなります。
T も N 行 N 列のグリッド内にあり、T_{i,j} が # であるようなマス全体からなります。
S と T を 90 度回転及び平行移動の繰り返しによって一致させることができるか判定してください。
制約
- 1 \leq N \leq 200
- S,T は
#と.のみからなる - S,T は 1 つ以上
#を含む
入力
入力は以下の形式で標準入力から与えられる。
N
S_{1,1}S_{1,2}\ldots S_{1,N}
\vdots
S_{N,1}S_{N,2}\ldots S_{N,N}
T_{1,1}T_{1,2}\ldots T_{1,N}
\vdots
T_{N,1}T_{N,2}\ldots T_{N,N}
出力
S と T を90 度回転及び平行移動の繰り返しによって一致させることができるとき Yes を、そうでないとき No を出力せよ。
入力例 1
5 ..... ..#.. .###. ..... ..... ..... ..... ....# ...## ....#
出力例 1
Yes
S を左回りに 90 度回転させ、平行移動することで T に一致させることができます。
入力例 2
5 ##### ##..# #..## ##### ..... ##### #..## ##..# ##### .....
出力例 2
No
90 度回転と平行移動の繰り返しによって一致させることはできません。
入力例 3
4 #... ..#. ..#. .... #... #... ..#. ....
出力例 3
Yes
S 及び T は連結とは限りません。
入力例 4
4 #... .##. ..#. .... ##.. #... ..#. ....
出力例 4
No
回転や移動の操作は連結成分ごとにできるわけではなく、S,T 全体に対して行うことに注意してください。
Score : 300 points
Problem Statement
We have two figures S and T on a two-dimensional grid with square cells.
S lies within a grid with N rows and N columns, and consists of the cells where S_{i,j} is #.
T lies within the same grid with N rows and N columns, and consists of the cells where T_{i,j} is #.
Determine whether it is possible to exactly match S and T by 90-degree rotations and translations.
Constraints
- 1 \leq N \leq 200
- Each of S and T consists of
#and.. - Each of S and T contains at least one
#.
Input
Input is given from Standard Input in the following format:
N
S_{1,1}S_{1,2}\ldots S_{1,N}
\vdots
S_{N,1}S_{N,2}\ldots S_{N,N}
T_{1,1}T_{1,2}\ldots T_{1,N}
\vdots
T_{N,1}T_{N,2}\ldots T_{N,N}
Output
Print Yes if it is possible to exactly match S and T by 90-degree rotations and translations, and No otherwise.
Sample Input 1
5 ..... ..#.. .###. ..... ..... ..... ..... ....# ...## ....#
Sample Output 1
Yes
We can match S to T by rotating it 90-degrees counter-clockwise and translating it.
Sample Input 2
5 ##### ##..# #..## ##### ..... ##### #..## ##..# ##### .....
Sample Output 2
No
It is impossible to match them by 90-degree rotations and translations.
Sample Input 3
4 #... ..#. ..#. .... #... #... ..#. ....
Sample Output 3
Yes
Each of S and T may not be connected.
Sample Input 4
4 #... .##. ..#. .... ##.. #... ..#. ....
Sample Output 4
No
Note that it is not allowed to rotate or translate just a part of a figure; it is only allowed to rotate or translate a whole figure.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
英小文字のみからなる N 個の文字列 S_1,S_2,\dots,S_N が与えられます。
S_1,S_2,\dots,S_N から文字列を好きな個数選ぶことを考えます。
このとき、「選んだ文字列の中でちょうど K 個の文字列に登場する英小文字」の種類数としてあり得る最大値を求めてください。
制約
- 1 \le N \le 15
- 1 \le K \le N
- N,K は整数
- S_i は英小文字からなる空でない文字列である。
- 1 \le i \le N を満たす整数 i に対し、S_i に同じ文字は 2 個以上含まれない。
- i \neq j ならば S_i \neq S_j である。
入力
入力は以下の形式で標準入力から与えられる。
N K S_1 S_2 \vdots S_N
出力
答えを出力せよ。
入力例 1
4 2 abi aef bc acg
出力例 1
3
S_1,S_3,S_4 を選んだ場合、a,b,c がちょうど 2 個の文字列に含まれます。
4 個以上の文字がちょうど 2 個の文字列に含まれるような選び方は存在しないため、答えは 3 です。
入力例 2
2 2 a b
出力例 2
0
同じ文字列を複数回選ぶことはできません。
入力例 3
5 2 abpqxyz az pq bc cy
出力例 3
7
Score : 300 points
Problem Statement
You are given N strings S_1,S_2,\dots,S_N consisting of lowercase English alphabets.
Consider choosing some number of strings from S_1,S_2,\dots,S_N.
Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly K of the chosen strings."
Constraints
- 1 \le N \le 15
- 1 \le K \le N
- N and K are integers.
- S_i is a non-empty string consisting of lowercase English alphabets.
- For each integer i such that 1 \le i \le N, S_i does not contain two or more same alphabets.
- If i \neq j, then S_i \neq S_j.
Input
Input is given from Standard Input in the following format:
N K S_1 S_2 \vdots S_N
Output
Print the answer.
Sample Input 1
4 2 abi aef bc acg
Sample Output 1
3
When S_1,S_3, and S_4 are chosen, a,b, and c occur in exactly two of the strings.
There is no way to choose strings so that 4 or more alphabets occur in exactly 2 of the strings, so the answer is 3.
Sample Input 2
2 2 a b
Sample Output 2
0
You cannot choose the same string more than once.
Sample Input 3
5 2 abpqxyz az pq bc cy
Sample Output 3
7
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
長さ N の数列 A=(A_1,A_2,\ldots,A_N) と、整数 K が与えられます。
A の連続部分列のうち、要素の和が K になるものはいくつありますか？
すなわち、以下の条件を全て満たす整数の組 (l,r) はいくつありますか？
- 1\leq l\leq r\leq N
- \displaystyle\sum_{i=l}^{r}A_i = K
制約
- 1\leq N \leq 2\times 10^5
- |A_i| \leq 10^9
- |K| \leq 10^{15}
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
6 5 8 -3 5 7 0 -4
出力例 1
3
(l,r)=(1,2),(3,3),(2,6) の 3 組が条件を満たします。
入力例 2
2 -1000000000000000 1000000000 -1000000000
出力例 2
0
条件を満たす (l,r) の組が 1 つも存在しないこともあります。
Score : 400 points
Problem Statement
Given is a sequence of length N: A=(A_1,A_2,\ldots,A_N), and an integer K.
How many of the contiguous subsequences of A have the sum of K?
In other words, how many pairs of integers (l,r) satisfy all of the conditions below?
- 1\leq l\leq r\leq N
- \displaystyle\sum_{i=l}^{r}A_i = K
Constraints
- 1\leq N \leq 2\times 10^5
- |A_i| \leq 10^9
- |K| \leq 10^{15}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
6 5 8 -3 5 7 0 -4
Sample Output 1
3
(l,r)=(1,2),(3,3),(2,6) are the three pairs that satisfy the conditions.
Sample Input 2
2 -1000000000000000 1000000000 -1000000000
Sample Output 2
0
There may be no pair that satisfies the conditions.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
ベルトコンベアに載って 10^{100} 個のじゃがいもが 1 個ずつ流れてきます。流れてくるじゃがいもの重さは長さ N の数列 W = (W_0, \dots, W_{N-1}) で表され、i \, (1 \leq i \leq 10^{100}) 番目に流れてくるじゃがいもの重さは W_{(i-1) \bmod N} です。ここで、(i-1) \bmod N は i - 1 を N で割った余りを表します。
高橋君は、まず空の箱を用意し、次のルールに従ってじゃがいもを順番に箱に詰めていきます。
- じゃがいもを箱に入れる。箱に入っているじゃがいもの重さの総和が X 以上になったら、その箱には蓋をし、新たに空の箱を用意する。
Q 個のクエリが与えられます。i \, (1 \leq i \leq Q) 番目のクエリでは、正整数 K_i が与えられるので、K_i 番目に蓋をされた箱に入っているじゃがいもの個数を求めてください。問題の制約下で、蓋をされた箱が K_i 個以上存在することが証明できます。
制約
- 1 \leq N, Q \leq 2 \times 10^5
- 1 \leq X \leq 10^9
- 1 \leq W_i \leq 10^9 \, (0 \leq i \leq N - 1)
- 1 \leq K_i \leq 10^{12} \, (1 \leq i \leq Q)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q X
W_0 W_1 \ldots W_{N-1}
K_1
\vdots
K_Q
出力
Q 行出力せよ。i \, (1 \leq i \leq Q) 行目には、i 番目のクエリへの答えを出力せよ。
入力例 1
3 2 5 3 4 1 1 2
出力例 1
2 3
2 つの箱に蓋をするまでの高橋くんの行動は以下の通りです。
- 空の箱を用意する。
- 1 番目のじゃがいもを箱に入れる。箱に入っているじゃがいもの重さの総和は 3 である。
- 2 番目のじゃがいもを箱に入れる。箱に入っているじゃがいもの重さの総和は 3 + 4 = 7 であり、X = 5 以上になったのでこの箱には蓋をする。
- 新たに空の箱を用意する。
- 3 番目のじゃがいもを箱に入れる。箱に入っているじゃがいもの重さの総和は 1 である。
- 4 番目のじゃがいもを箱に入れる。箱に入っているじゃがいもの重さの総和は 1 + 3 = 4 である。
- 5 番目のじゃがいもを箱に入れる。箱に入っているじゃがいもの重さの総和は 1 + 3 + 4 = 8 であり、X = 5 以上になったのでこの箱には蓋をする。
1 番目に蓋をされた箱には 2 つのじゃがいもが入っており、2 番目に蓋をされた箱には 3 つのじゃがいもが入っています。
入力例 2
10 5 20 5 8 5 9 8 7 4 4 8 2 1 1000 1000000 1000000000 1000000000000
出力例 2
4 5 5 5 5
Score : 500 points
Problem Statement
10^{100} potatoes are coming from a conveyor belt one by one. The weights of the potatoes are described by a sequence W = (W_0, \dots, W_{N-1}) of length N: the weight of the i-th potato coming is W_{(i-1) \bmod N}, where (i-1) \bmod N denotes the remainder when i - 1 is divided by N.
Takahashi will prepare an empty box and then pack the potatoes in order, as follows.
- Pack the incoming potato into the box. If the total weight of the potatoes in the box is now X or greater, seal that box and prepare a new empty box.
You are given Q queries. In the i-th query (1 \leq i \leq Q), given a positive integer K_i, find the number of potatoes in the K_i-th box to be sealed. It can be proved that, under the Constraints of the problem, there will be at least K_i sealed boxes.
Constraints
- 1 \leq N, Q \leq 2 \times 10^5
- 1 \leq X \leq 10^9
- 1 \leq W_i \leq 10^9 \, (0 \leq i \leq N - 1)
- 1 \leq K_i \leq 10^{12} \, (1 \leq i \leq Q)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q X
W_0 W_1 \ldots W_{N-1}
K_1
\vdots
K_Q
Output
Print Q lines. The i-th line (1 \leq i \leq Q) should contain the answer to the i-th query.
Sample Input 1
3 2 5 3 4 1 1 2
Sample Output 1
2 3
Before sealing the 2-nd box, Takahashi will do the following:
- Prepare an empty box.
- Pack the 1-st potato into the box. Now, the total weight of potatoes in the box is 3.
- Pack the 2-nd potato into the box. Now, the total weight of potatoes in the box is 3 + 4 = 7, which is not less than X = 5, so seal this box.
- Prepare a new empty box.
- Pack the 3-rd potato into the box. Now, the total weight of potatoes in the box is 1.
- Pack the 4-th potato into the box. Now, the total weight of potatoes in the box is 1 + 3 = 4.
- Pack the 5-th potato into the box. Now, the total weight of potatoes in the box is 1 + 3 + 4 = 8, which is not less than X = 5, so seal this box.
The 1-st box sealed contains 2 potatoes, and the 2-nd box sealed contains 3 potatoes.
Sample Input 2
10 5 20 5 8 5 9 8 7 4 4 8 2 1 1000 1000000 1000000000 1000000000000
Sample Output 2
4 5 5 5 5
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
長さ L のパンが 1 つあり、これを N 人の子供たちに切り分けます。 i 番目 (1\leq i\leq N) の子供は長さ A_i のパンを欲しがっています。
そこで、高橋君は次の操作を繰り返して、長さ A_1,A_2,\ldots,A_N のパンを切り出して配ることにしました。
長さ k のパン 1 つと 1 以上 k-1 以下の整数 x を選ぶ。選んだパンを長さ x のパンと 長さ k-x のパンに切り分ける。
このとき、x の値によらずコストが k かかる。
それぞれの子供に配るパンは長さがちょうど A_i のパン 1 つである必要がありますが、誰にも配られずに余るパンがいくつあっても構いません。
このとき、全ての子供たちにパンを配るために必要な最小のコストを求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- 1\leq A_i\leq 10^9
- A_1+A_2+\cdots+A_N\leq L\leq 10^{15}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L A_1 A_2 \ldots A_N
出力
全ての子供たちにパンを配るために必要な最小のコストを出力せよ。
入力例 1
5 7 1 2 1 2 1
出力例 1
16
高橋君は次のようにしてパンを切り分けて配ることができます。
- 長さ 7 のパンと整数 x=3 を選ぶ。パンは長さ 3 のパンと長さ 4 のパンに切り分けられる。 (コスト 7 )
- 長さ 3 のパンと整数 x=1 を選ぶ。パンは長さ 1 のパンと長さ 2 のパンに切り分けられる。前者を 1 番目の子供に配る。 (コスト 3 )
- 長さ 2 のパンと整数 x=1 を選ぶ。パンは長さ 1 のパン 2 つに切り分けられる。これを 3,5 番目の子供に配る。 (コスト 2 )
- 長さ 4 のパンと整数 x=2 を選ぶ。パンは長さ 2 のパン 2 つに切り分けられる。これを 2,4 番目の子供に配る。 (コスト 4 )
このとき、コストは 7+3+2+4=16 かかり、これが最小です。 また、余るパンはありません。
入力例 2
3 1000000000000000 1000000000 1000000000 1000000000
出力例 2
1000005000000000
それぞれの子供に配るパンの長さはちょうど A_i でなければならない事に注意してください。
Score : 500 points
Problem Statement
We have a loaf of bread of length L, which we will cut and distribute to N children.
The i-th child (1\leq i\leq N) wants a loaf of length A_i.
Now, Takahashi will repeat the operation below to cut the loaf into lengths A_1, A_2, \ldots, A_N for the children.
Choose a loaf of length k and an integer x between 1 and k-1 (inclusive). Cut the loaf into two loaves of length x and k-x.
This operation incurs a cost of k regardless of the value of x.
Each child i must receive a loaf of length exactly A_i, but it is allowed to leave some loaves undistributed.
Find the minimum cost needed to distribute loaves to all children.
Constraints
- 2 \leq N \leq 2\times 10^5
- 1\leq A_i\leq 10^9
- A_1+A_2+\cdots+A_N\leq L\leq 10^{15}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N L A_1 A_2 \ldots A_N
Output
Print the minimum cost needed to distribute loaves to all children.
Sample Input 1
5 7 1 2 1 2 1
Sample Output 1
16
Takahashi can cut the loaf for the children as follows.
- Choose the loaf of length 7 and x=3, cutting it into loaves of length 3 and 4 for a cost of 7.
- Choose the loaf of length 3 and x=1, cutting it into loaves of length 1 and 2 for a cost of 3. Give the former to the 1-st child.
- Choose the loaf of length 2 and x=1, cutting it into two loaves of length 1 for a cost of 2. Give them to the 3-rd and 5-th children.
- Choose the loaf of length 4 and x=2, cutting it into two loaves of length 2 for a cost of 4. Give them to the 2-nd and 4-th children.
This incurs a cost of 7+3+2+4=16, which is the minimum possible. There will be no leftover loaves.
Sample Input 2
3 1000000000000000 1000000000 1000000000 1000000000
Sample Output 2
1000005000000000
Note that each child i must receive a loaf of length exactly A_i.