Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
10^{100} 行 7 列の行列 A があり、任意の整数対 (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7) についてその (i,j) 成分は (i-1) \times 7 + j です。
N 行 M 列の行列 B が与えられるので、B が A から一部の矩形領域を（向きを変えずに）切り出したものであるかを判定してください。
制約
- 1 \leq N \leq 10^4
- 1 \leq M \leq 7
- 1 \leq B_{i,j} \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\hspace{1.6cm}\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}
出力
B が A から一部の矩形領域を切り出したものであれば Yes と、そうでないなら No と出力せよ。
入力例 1
2 3 1 2 3 8 9 10
出力例 1
Yes
与えられる B は、A の左上 2 行 3 列を切り出したものとなっています。
入力例 2
2 1 1 2
出力例 2
No
与えられる B を 90 度回転させると A の左上 1 行 2 列と一致しますが、問題文中に「向きを変えずに」とある通り回転による一致は認められていないため、答えは No となります。
入力例 3
10 4 1346 1347 1348 1349 1353 1354 1355 1356 1360 1361 1362 1363 1367 1368 1369 1370 1374 1375 1376 1377 1381 1382 1383 1384 1388 1389 1390 1391 1395 1396 1397 1398 1402 1403 1404 1405 1409 1410 1411 1412
出力例 3
Yes
Score : 300 points
Problem Statement
There is a 10^{100} \times 7 matrix A, where the (i,j)-th entry is (i-1) \times 7 + j for every pair of integers (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7).
Given an N \times M matrix B, determine whether B is some (unrotated) rectangular part of A.
Constraints
- 1 \leq N \leq 10^4
- 1 \leq M \leq 7
- 1 \leq B_{i,j} \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\hspace{1.6cm}\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}
Output
If B is some rectangular part of A, print Yes; otherwise, print No.
Sample Input 1
2 3 1 2 3 8 9 10
Sample Output 1
Yes
The given matrix B is the top-left 2 \times 3 submatrix of A.
Sample Input 2
2 1 1 2
Sample Output 2
No
Although the given matrix B would match the top-left 1 \times 2 submatrix of A after rotating 90 degrees, the Problem Statement asks whether B is an unrotated part of A, so the answer is No.
Sample Input 3
10 4 1346 1347 1348 1349 1353 1354 1355 1356 1360 1361 1362 1363 1367 1368 1369 1370 1374 1375 1376 1377 1381 1382 1383 1384 1388 1389 1390 1391 1395 1396 1397 1398 1402 1403 1404 1405 1409 1410 1411 1412
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N かつ全ての要素が 1 以上 M 以下である整数列のうち、狭義単調増加であるものを全て辞書順に出力してください。
注記
ある 2 個の異なる長さの等しい整数列 A_1,A_2,\dots,A_N と B_1,B_2,\dots,B_N が以下を満たすとき、またその時に限り辞書順で A が B より早いと定義されます。
- ある整数 i(1 \le i \le N) が存在し、1 \le j < i である全ての整数 j に対し A_j=B_j が成り立ち、かつ A_i < B_i が成り立つ。
ある整数列 A_1,A_2,\dots,A_N は以下を満たすとき、またその時に限り狭義単調増加です。
- 全ての整数 i(1 \le i \le N-1) に対し A_i < A_{i+1} が成り立つ。
制約
- 1 \le N \le M \le 10
- 入力は全て整数。
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
条件を満たす整数列を一行に一つずつ、辞書順に出力せよ（出力例を参考にせよ）。
入力例 1
2 3
出力例 1
1 2 1 3 2 3
条件を満たす数列は (1,2),(1,3),(2,3) の 3 個です。これらを辞書順で早い方から出力します。
入力例 2
3 5
出力例 2
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
Score : 300 points
Problem Statement
Print all strictly increasing integer sequences of length N where all elements are between 1 and M (inclusive), in lexicographically ascending order.
Notes
For two integer sequences of the same length A_1,A_2,\dots,A_N and B_1,B_2,\dots,B_N, A is said to be lexicographically earlier than B if and only if:
- there is an integer i (1 \le i \le N) such that A_j=B_j for all integers j satisfying 1 \le j < i, and A_i < B_i.
An integer sequence A_1,A_2,\dots,A_N is said to be strictly increasing if and only if:
- A_i < A_{i+1} for all integers i (1 \le i \le N-1).
Constraints
- 1 \le N \le M \le 10
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the sought sequences in lexicographically ascending order, each in its own line (see Sample Outputs).
Sample Input 1
2 3
Sample Output 1
1 2 1 3 2 3
The sought sequences are (1,2),(1,3),(2,3), which should be printed in lexicographically ascending order.
Sample Input 2
3 5
Sample Output 2
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君と青木君が選挙で戦っています。
選挙区は N 個あります。i 番目の選挙区には X_i + Y_i 人の有権者がいて、そのうち X_i 人が高橋派、Y_i 人が青木派です。(X_i + Y_i はすべて奇数です)
それぞれの区では、多数派がその区の Z_i 議席を全て獲得します。そして、N 個の選挙区全体として過半数の議席を獲得した方が選挙に勝利します。(\displaystyle \sum_{i=1}^N Z_i は奇数です)
高橋君が選挙で勝利するには最低で何人を青木派から高橋派に鞍替えさせる必要がありますか？
制約
- 1 \leq N \leq 100
- 0 \leq X_i, Y_i \leq 10^9
- X_i + Y_i は奇数
- 1 \leq Z_i
- \displaystyle \sum_{i=1}^N Z_i \leq 10^5
- \displaystyle \sum_{i=1}^N Z_i は奇数
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 Z_1 X_2 Y_2 Z_2 \vdots X_N Y_N Z_N
出力
答えを出力せよ。
入力例 1
1 3 8 1
出力例 1
3
選挙区が 1 個しかないので、1 番目の選挙区で議席を獲得した人が選挙に勝利します。
1 番目の選挙区の青木派 3 人を高橋派に鞍替えさせると、1 番目の選挙区にいる有権者のうち高橋派は 6 人、青木派は 5 人になり、高橋君は議席を獲得できます。
入力例 2
2 3 6 2 1 8 5
出力例 2
4
1 番目の選挙区の議席数よりも 2 番目の選挙区の議席数の方が多いため、高橋君が選挙に勝つには 2 番目の選挙区で高橋派を多数派にする必要があります。
2 番目の選挙区の青木派の 4 人を鞍替えさせると高橋君は 5 議席を獲得できます。このとき青木君の獲得する議席は 2 議席なので、高橋君は選挙に勝利できます。
入力例 3
3 3 4 2 1 2 3 7 2 6
出力例 3
0
青木派から高橋派に鞍替えする人が 0 人でも高橋君が選挙で勝つ場合は 0 人が答えになります。
入力例 4
10 1878 2089 16 1982 1769 13 2148 1601 14 2189 2362 15 2268 2279 16 2394 2841 18 2926 2971 20 3091 2146 20 3878 4685 38 4504 4617 29
出力例 4
86
Score : 400 points
Problem Statement
Takahashi and Aoki are competing in an election.
There are N electoral districts. The i-th district has X_i + Y_i voters, of which X_i are for Takahashi and Y_i are for Aoki. (X_i + Y_i is always an odd number.)
In each district, the majority party wins all Z_i seats in that district. Then, whoever wins the majority of seats in the N districts as a whole wins the election. (\displaystyle \sum_{i=1}^N Z_i is odd.)
At least how many voters must switch from Aoki to Takahashi for Takahashi to win the election?
Constraints
- 1 \leq N \leq 100
- 0 \leq X_i, Y_i \leq 10^9
- X_i + Y_i is odd.
- 1 \leq Z_i
- \displaystyle \sum_{i=1}^N Z_i \leq 10^5
- \displaystyle \sum_{i=1}^N Z_i is odd.
Input
The input is given from Standard Input in the following format:
N X_1 Y_1 Z_1 X_2 Y_2 Z_2 \vdots X_N Y_N Z_N
Output
Print the answer.
Sample Input 1
1 3 8 1
Sample Output 1
3
Since there is only one district, whoever wins the seat in that district wins the election.
If three voters for Aoki in the district switch to Takahashi, there will be six voters for Takahashi and five for Aoki, and Takahashi will win the seat.
Sample Input 2
2 3 6 2 1 8 5
Sample Output 2
4
Since there are more seats in the second district than in the first district, Takahashi must win a majority in the second district to win the election.
If four voters for Aoki in the second district switch sides, Takahashi will win five seats. In this case, Aoki will win two seats, so Takahashi will win the election.
Sample Input 3
3 3 4 2 1 2 3 7 2 6
Sample Output 3
0
If Takahashi will win the election even if zero voters switch sides, the answer is 0.
Sample Input 4
10 1878 2089 16 1982 1769 13 2148 1601 14 2189 2362 15 2268 2279 16 2394 2841 18 2926 2971 20 3091 2146 20 3878 4685 38 4504 4617 29
Sample Output 4
86
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
この問題における 11/22 文字列の定義は A 問題および C 問題と同じです。
文字列 T が以下の条件を全て満たすとき、T を 11/22 文字列 と呼びます。
- |T| は奇数である。ここで、|T| は T の長さを表す。
- 1 文字目から \frac{|T|+1}{2} - 1 文字目までが
1である。 - \frac{|T|+1}{2} 文字目が
/である。 - \frac{|T|+1}{2} + 1 文字目から |T| 文字目までが
2である。
例えば 11/22, 111/222, / は 11/22 文字列ですが、1122, 1/22, 11/2222, 22/11, //2/2/211 はそうではありません。
1, 2, / からなる長さ N の文字列 S が与えられるので、Q 個のクエリを処理してください。
各クエリでは L, R が与えられます。S の L 文字目から R 文字目までからなる (連続な) 部分文字列を T としたとき、 11/22 文字列であるような T の (連続とは限らない) 部分列の長さの最大値を求めてください。そのような部分列が存在しないときは 0 を出力してください。
制約
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- S は
1,2,/からなる長さ N の文字列 - 1 \leq L \leq R \leq N
- N, Q, L, R は整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。
N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
各クエリは以下の形式で与えられる。
L R
出力
Q 行出力せよ。i 行目には i 番目のクエリへの答えを出力せよ。
入力例 1
12 5 111/212/1122 1 7 9 12 3 6 4 10 1 12
出力例 1
5 0 3 1 7
1 番目のクエリについて、S の 1 文字目から 7 文字目からなる部分文字列は 111/212 です。この文字列は 11/22 を部分列として含み、これは 11/22 文字列であるような部分列として最大です。よって答えは 5 です。
2 番目のクエリについて、S の 9 文字目から 12 文字目からなる部分文字列は 1122 です。この文字列は 11/22 文字列であるような部分列を含まないので、答えは 0 です。
Score : 500 points
Problem Statement
The definition of an 11/22 string in this problem is the same as in Problems A and C.
A string T is called an 11/22 string when it satisfies all of the following conditions:
- |T| is odd. Here, |T| denotes the length of T.
- The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all
1. - The (\frac{|T|+1}{2})-th character is
/. - The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all
2.
For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.
Given a string S of length N consisting of 1, 2, and /, process Q queries.
Each query provides two integers L and R. Let T be the (contiguous) substring of S from the L-th through R-th character. Find the maximum length of a subsequence (not necessarily contiguous) of T that is an 11/22 string. If no such subsequence exists, print 0.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- S is a string of length N consisting of
1,2, and/. - 1 \leq L \leq R \leq N
- N, Q, L, and R are integers.
Input
The input is given from Standard Input in the following format. Here, \mathrm{query}_i denotes the i-th query.
N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is given in the following format:
L R
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
12 5 111/212/1122 1 7 9 12 3 6 4 10 1 12
Sample Output 1
5 0 3 1 7
For the first query, the substring from the 1-st to 7-th character of S is 111/212. This string contains 11/22 as a subsequence, which is the longest subsequence that is an 11/22 string. Therefore, the answer is 5.
For the second query, the substring from the 9-th to 12-th character of S is 1122. This string does not contain any subsequence that is an 11/22 string, so the answer is 0.
Time Limit: 2.5 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
店で N 個の商品が売られています。 i 個目の商品の価格は P_i 円、効用は U_i 、色は C_i です。
あなたは、これらの N 個の商品から何個か( 0 個でもよい)を選んで購入します。 このとき、購入した品物の合計価格は X 円以下でなければなりません。
あなたの満足度は、購入した商品の効用の合計を S、購入した商品の色の種類数を T としたとき、S+T \times K です。 ここで、K は入力で与えられる定数です。
あなたの満足度を最大化するように購入する商品を選んだとき、満足度を求めてください。
制約
- 1 \leq N \leq 500
- 1 \leq X \leq 50000
- 1 \leq K \leq 10^9
- 1 \leq P_i \leq X (1 \leq i \leq N)
- 1 \leq U_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq C_i \leq N (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X K P_1 U_1 C_1 P_2 U_2 C_2 \vdots P_N U_N C_N
出力
答えを出力せよ。
入力例 1
3 10 5 1 3 1 7 4 2 4 5 1
出力例 1
17
1 個目、2 個目の商品を購入したとき、効用の合計 S は 7 で、色の種類数 T は 2 です。よって、満足度は 7+2 \times 5 = 17 です。また、満足度が 18 以上になるような購入の仕方は存在しないため、答えは 17 です。
入力例 2
5 30 3 5 4 3 11 20 1 9 10 4 7 5 2 16 15 4
出力例 2
44
2 個目、3 個目、4 個目の商品を購入したとき、効用の合計 S は 35 で、色の種類数 T は 3 です。よって、満足度は 35+3 \times 3 = 44 です。また、満足度が 45 以上になるような購入の仕方は存在しないため、答えは 44 です。
入力例 3
22 75 6426 9 309 9 5 470 5 17 481 12 27 352 14 1 191 18 7 353 20 9 99 15 20 401 17 46 434 19 11 459 22 10 317 19 15 440 18 17 438 19 25 461 22 5 320 22 1 476 21 11 315 3 8 112 9 11 438 13 19 362 8 10 422 13 10 152 21
出力例 3
67717
Score : 525 points
Problem Statement
There are N products for sale in a store. The i-th product has a price of P_i yen, a utility value of U_i, and a color C_i.
You will choose some subset of these N products to buy (possibly none). The total price of the chosen products must be at most X yen.
Your satisfaction is S + T \times K, where S is the sum of utilities of the chosen products, and T is the number of distinct colors among the chosen products. Here, K is a given constant.
You will choose products to maximize your satisfaction. Find the maximized satisfaction.
Constraints
- 1 \leq N \leq 500
- 1 \leq X \leq 50000
- 1 \leq K \leq 10^9
- 1 \leq P_i \leq X (1 \leq i \leq N)
- 1 \leq U_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq C_i \leq N (1 \leq i \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X K P_1 U_1 C_1 P_2 U_2 C_2 \vdots P_N U_N C_N
Output
Print the answer.
Sample Input 1
3 10 5 1 3 1 7 4 2 4 5 1
Sample Output 1
17
If you buy the 1st and 2nd products, the total utility S is 7, and the number of distinct colors T is 2. Thus, your satisfaction is 7 + 2 \times 5 = 17. No purchase plan makes your satisfaction 18 or greater, so the answer is 17.
Sample Input 2
5 30 3 5 4 3 11 20 1 9 10 4 7 5 2 16 15 4
Sample Output 2
44
If you buy the 2nd, 3rd, and 4th products, the total utility S is 35, and the number of distinct colors T is 3. Thus, your satisfaction is 35 + 3 \times 3 = 44. No purchase plan makes your satisfaction 45 or greater, so the answer is 44.
Sample Input 3
22 75 6426 9 309 9 5 470 5 17 481 12 27 352 14 1 191 18 7 353 20 9 99 15 20 401 17 46 434 19 11 459 22 10 317 19 15 440 18 17 438 19 25 461 22 5 320 22 1 476 21 11 315 3 8 112 9 11 438 13 19 362 8 10 422 13 10 152 21
Sample Output 3
67717