実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
英大文字からなる長さ 3 の文字列 T が、英小文字からなる文字列 S の 空港コード であるとは、 T が S から次のいずれかの方法により得られることとします。
- S の長さ 3 の（連続とは限らない）部分列をとり、それを英大文字に変換したものを T とする
- S の長さ 2 の（連続とは限らない）部分列をとり、それを英大文字に変換したものの末尾に
Xを追加したものを T とする
文字列 S, T が与えられるので、 T が S の空港コードであるか判定してください。
制約
- S は英小文字からなる長さ 3 以上 10^5 以下の文字列
- T は英大文字からなる長さ 3 の文字列
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
T が S の空港コードであるならば Yes を、そうでないならば No を出力せよ。
入力例 1
narita NRT
出力例 1
Yes
narita の部分列 nrt を英大文字に変換した文字列 NRT は、 narita の空港コードです。
入力例 2
losangeles LAX
出力例 2
Yes
losangeles の部分列 la を英大文字に変換した文字列 LA の末尾に X を追加したもの LAX は、 losangeles の空港コードです。
入力例 3
snuke RNG
出力例 3
No
Score: 300 points
Problem Statement
A string T of length 3 consisting of uppercase English letters is an airport code for a string S of lowercase English letters if and only if T can be derived from S by one of the following methods:
- Take a subsequence of length 3 from S (not necessarily contiguous) and convert it to uppercase letters to form T.
- Take a subsequence of length 2 from S (not necessarily contiguous), convert it to uppercase letters, and append
Xto the end to form T.
Given strings S and T, determine if T is an airport code for S.
Constraints
- S is a string of lowercase English letters with a length between 3 and 10^5, inclusive.
- T is a string of uppercase English letters with a length of 3.
Input
The input is given from Standard Input in the following format:
S T
Output
Print Yes if T is an airport code for S, and No otherwise.
Sample Input 1
narita NRT
Sample Output 1
Yes
The subsequence nrt of narita, when converted to uppercase, forms the string NRT, which is an airport code for narita.
Sample Input 2
losangeles LAX
Sample Output 2
Yes
The subsequence la of losangeles, when converted to uppercase and appended with X, forms the string LAX, which is an airport code for losangeles.
Sample Input 3
snuke RNG
Sample Output 3
No
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
N 行 N 列のグリッドが与えられます。ここで、N は偶数です。グリッドの上から i 行目、左から j 列目のマスをマス (i, j) と表記します。
グリッドの各マスは黒か白のいずれかで塗られており、A_{i, j} = # のときマス (i, j) は黒、A_{i, j} = . のときマス (i, j) は白で塗られています。
i = 1, 2, \ldots, \frac{N}{2} の順に以下の操作を行った後のグリッドの各マスの色を求めてください。
- i 以上 N + 1 - i 以下の整数 x, y について、マス (y, N + 1 - x) の色をマス (x, y) の色で置き換える。この置き換えは条件を満たすすべての整数 x, y について同時に行う。
制約
- N は 2 以上 3000 以下の偶数
- A_{i, j} は
#または.
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1, 1}A_{1, 2}\ldotsA_{1, N}
A_{2, 1}A_{2, 2}\ldotsA_{2, N}
\vdots
A_{N, 1}A_{N, 2}\ldotsA_{N, N}
出力
すべての操作を終えた後、マス (i, j) の色が黒であるとき B_{i, j} = #、マス (i, j) の色が白であるとき B_{i, j} = . として以下の形式で出力せよ。
B_{1, 1}B_{1, 2}\ldotsB_{1, N}
B_{2, 1}B_{2, 2}\ldotsB_{2, N}
\vdots
B_{N, 1}B_{N, 2}\ldotsB_{N, N}
入力例 1
8 .......# .......# .####..# .####..# .##....# .##....# .####### .#######
出力例 1
........ #######. #.....#. #.###.#. #.#...#. #.#####. #....... ########
操作によってグリッドの各マスの色は以下のように変化します。
.......# ........ ........ ........ ........ .......# ######.. #######. #######. #######. .####..# ######.. #....##. #.....#. #.....#. .####..# → ##..##.. → #....##. → #.##..#. → #.###.#. .##....# ##..##.. #..####. #.##..#. #.#...#. .##....# ##...... #..####. #.#####. #.#####. .####### ##...... #....... #....... #....... .####### ######## ######## ######## ########
入力例 2
6 .#.#.# ##.#.. ...### ###... ..#.## #.#.#.
出力例 2
#.#.#. .#.#.# #.#.#. .#.#.# #.#.#. .#.#.#
入力例 3
12 .......#.### #...#...#..# ###.#..##### ..#.#.#.#... .#.....#.### .......#.#.. #...#..#.... #####....... ...#...#.#.# ..###..#..## #..#.#.#.#.# .####.......
出力例 3
.#..##...##. #.#.#.#.#... ###.##..#... #.#.#.#.#... #.#.##...##. ............ ............ .###.###.### ...#...#.#.. .###...#.### ...#...#...# .###...#.###
Score : 400 points
Problem Statement
You are given a grid with N rows and N columns, where N is an even number. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
Each cell is painted black or white. If A_{i, j} = #, cell (i, j) is black; if A_{i, j} = ., it is white.
Find the color of each cell after performing the following operation for i = 1, 2, \ldots, \frac{N}{2} in this order.
- For all pairs of integers x, y between i and N + 1 - i, inclusive, replace the color of cell (y, N + 1 - x) with the color of cell (x, y). Perform these replacements simultaneously for all such pairs x, y.
Constraints
- N is an even number between 2 and 3000, inclusive.
- Each A_{i, j} is
#or..
Input
The input is given from Standard Input in the following format:
N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}
Output
After all operations, let B_{i, j} = # if cell (i, j) is black, and B_{i, j} = . if it is white. Print the grid in the following format:
B_{1,1}B_{1,2}\ldots B_{1,N}
B_{2,1}B_{2,2}\ldots B_{2,N}
\vdots
B_{N,1}B_{N,2}\ldots B_{N,N}
Sample Input 1
8 .......# .......# .####..# .####..# .##....# .##....# .####### .#######
Sample Output 1
........ #######. #.....#. #.###.#. #.#...#. #.#####. #....... ########
The operations change the colors of the grid cells as follows:
.......# ........ ........ ........ ........ .......# ######.. #######. #######. #######. .####..# ######.. #....##. #.....#. #.....#. .####..# → ##..##.. → #....##. → #.##..#. → #.###.#. .##....# ##..##.. #..####. #.##..#. #.#...#. .##....# ##...... #..####. #.#####. #.#####. .####### ##...... #....... #....... #....... .####### ######## ######## ######## ########
Sample Input 2
6 .#.#.# ##.#.. ...### ###... ..#.## #.#.#.
Sample Output 2
#.#.#. .#.#.# #.#.#. .#.#.# #.#.#. .#.#.#
Sample Input 3
12 .......#.### #...#...#..# ###.#..##### ..#.#.#.#... .#.....#.### .......#.#.. #...#..#.... #####....... ...#...#.#.# ..###..#..## #..#.#.#.#.# .####.......
Sample Output 3
.#..##...##. #.#.#.#.#... ###.##..#... #.#.#.#.#... #.#.##...##. ............ ............ .###.###.### ...#...#.#.. .###...#.### ...#...#...# .###...#.###
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 350 点
問題文
正整数 N に対して、N を N 個つなげた整数を V_N とします。
より厳密には、N を文字列とみなしたものを N 個連結し、
それを再度整数とみなしたものを V_N とします。
例えば、V_3=333, V_{10}=10101010101010101010 です。
V_N を 998244353 で割った余りを求めてください。
制約
- 1\leq N\leq 10^{18}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
V_N を 998244353 で割った余りを出力せよ。
入力例 1
5
出力例 1
55555
V_5=55555 を 998244353 で割った余りは 55555 です。
入力例 2
9
出力例 2
1755646
V_9=999999999 を 998244353 で割った余りは 1755646 です。
入力例 3
10000000000
出力例 3
468086693
入力が 32 bit 整数型に収まらない可能性があることに注意してください。
Score : 350 points
Problem Statement
For a positive integer N, let V_N be the integer formed by concatenating N exactly N times.
More precisely, consider N as a string, concatenate N copies of it, and treat the result as an integer to get V_N.
For example, V_3=333 and V_{10}=10101010101010101010.
Find the remainder when V_N is divided by 998244353.
Constraints
- 1 \leq N \leq 10^{18}
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the remainder when V_N is divided by 998244353.
Sample Input 1
5
Sample Output 1
55555
The remainder when V_5=55555 is divided by 998244353 is 55555.
Sample Input 2
9
Sample Output 2
1755646
The remainder when V_9=999999999 is divided by 998244353 is 1755646.
Sample Input 3
10000000000
Sample Output 3
468086693
Note that the input may not fit into a 32-bit integer type.
実行時間制限: 4 sec / メモリ制限: 1024 MiB
配点 : 450 点
問題文
N 個の島と、2 つの島の間を双方向に結ぶ M 本の橋があり、
それぞれ島 1, 島 2, \ldots, 島 N および 橋 1, 橋 2, \ldots, 橋 M と番号づけられています。
橋 i は島 U_i と島 V_i を相互に結んでおり、どちらの方向に移動するにも T_i だけ時間がかかります。
ここで、橋の両端が同一の島であるような橋は存在しませんが、ある 2 つの島の間が 2 本以上の橋で直接繋がれている可能性はあります。
また、どの 2 つの島の間もいくつかの橋をわたって移動することができます。
Q 個の問題が与えられるので、各問題に対する答えを求めてください。i 番目の問題は次のようなものです。
相異なる K_i 本の橋、橋 B_{i,1}, 橋 B_{i,2}, \ldots, 橋 B_{i,K_i} が与えられます。
これらの橋をすべて 1 回以上わたり、島 1 から島 N まで移動するために必要な時間の最小値を求めてください。
ただし、島 1 から島 N までの移動において、橋をわたって島の間を移動するのにかかる時間以外は無視できるものとします。
また、与えられた橋はどの順で、またどの向きにわたってもかまいません。
制約
- 2\leq N \leq 400
- N-1\leq M \leq 2\times 10^5
- 1\leq U_i<V_i\leq N
- 1\leq T_i\leq 10^9
- 1\leq Q\leq 3000
- 1\leq K_i\leq 5
- 1\leq B_{i,1}<B_{i,2}<\cdots<B_{i,K_i}\leq M
- 入力はすべて整数
- どの 2 つの島の間もいくつかの橋をわたって移動することができる。
入力
入力は以下の形式で標準入力から与えられる。
N M
U_1 V_1 T_1
U_2 V_2 T_2
\vdots
U_M V_M T_M
Q
K_1
B_{1,1} B_{1,2} \cdots B_{1,{K_1}}
K_2
B_{2,1} B_{2,2} \cdots B_{2,{K_2}}
\vdots
K_Q
B_{Q,1} B_{Q,2} \cdots B_{Q,{K_Q}}
出力
Q 行出力せよ。i 行目（1\leq i\leq Q）には i 番目の問題に対する答えを整数で出力せよ。
入力例 1
3 5 1 2 10 1 3 20 1 3 30 2 3 15 2 3 25 2 1 1 2 3 5
出力例 1
25 70
1 番目の問題では橋 1 をわたった上で島 1 から島 3 へ移動するために必要な時間の最小値を求める必要があります。
橋 1 を使って島 1 から島 2 に移動した後に橋 4 を使って島 2 から島 3 に移動したとき時間は 10+15=25 だけかかり、このときが最小です。
よって、1 行目には 25 を出力します。
2 番目の問題では橋 3 および橋 5 をわたった上で島 1 から島 3 へ移動するために必要な時間の最小値を求める必要があります。
橋 3 を通って島 1 から島 3 に移動した後に橋 5 を使って島 2 へ移動し、橋 4 を使用して島 3 に移動したとき時間は 30+25+15=70 だけかかり、このときが最小です。よって、2 行目には 70 を出力します。
入力例 2
6 6 1 5 1 2 5 1 2 4 1 3 4 1 3 6 1 1 6 1 2 5 1 2 3 4 5 1 5
出力例 2
5 3
各問題において指定された橋をわたる際、わたる方向はどちらでも問題ありません。
入力例 3
5 5 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 1 5 1000000000 1 1 3
出力例 3
4000000000
答えが 32bit 整数型に収まらない可能性があることに注意してください。
Score : 450 points
Problem Statement
There are N islands and M bidirectional bridges connecting two islands. The islands and bridges are numbered 1, 2, \ldots, N and 1, 2, \ldots, M, respectively.
Bridge i connects islands U_i and V_i, and the time it takes to cross it in either direction is T_i.
No bridge connects an island to itself, but it is possible for two islands to be directly connected by more than one bridge.
One can travel between any two islands using some bridges.
You are given Q queries, so answer each of them. The i-th query is as follows:
You are given K_i distinct bridges: bridges B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}.
Find the minimum time required to travel from island 1 to island N using each of these bridges at least once.
Only consider the time spent crossing bridges.
You can cross the given bridges in any order and in any direction.
Constraints
- 2 \leq N \leq 400
- N-1 \leq M \leq 2 \times 10^5
- 1 \leq U_i < V_i \leq N
- 1 \leq T_i \leq 10^9
- 1 \leq Q \leq 3000
- 1 \leq K_i \leq 5
- 1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M
- All input values are integers.
- It is possible to travel between any two islands using some bridges.
Input
The input is given from Standard Input in the following format:
N M
U_1 V_1 T_1
U_2 V_2 T_2
\vdots
U_M V_M T_M
Q
K_1
B_{1,1} B_{1,2} \cdots B_{1,{K_1}}
K_2
B_{2,1} B_{2,2} \cdots B_{2,{K_2}}
\vdots
K_Q
B_{Q,1} B_{Q,2} \cdots B_{Q,{K_Q}}
Output
Print Q lines. The i-th line (1 \leq i \leq Q) should contain the answer to the i-th query as an integer.
Sample Input 1
3 5 1 2 10 1 3 20 1 3 30 2 3 15 2 3 25 2 1 1 2 3 5
Sample Output 1
25 70
For the first query, we need to find the minimum time to travel from island 1 to island 3 while using bridge 1. The minimum time is achieved by using bridge 1 to move from island 1 to island 2, then using bridge 4 to move from island 2 to island 3. The time taken is 10 + 15 = 25. Hence, print 25 on the first line.
For the second query, we need to find the minimum time to travel from island 1 to island 3 while using both bridges 3 and 5. The minimum time is achieved by using bridge 3 to move from island 1 to island 3, then using bridge 5 to move to island 2, and finally using bridge 4 to return to island 3. The time taken is 30 + 25 + 15 = 70. Hence, print 70 on the second line.
Sample Input 2
6 6 1 5 1 2 5 1 2 4 1 3 4 1 3 6 1 1 6 1 2 5 1 2 3 4 5 1 5
Sample Output 2
5 3
For each query, you can cross the specified bridges in either direction.
Sample Input 3
5 5 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 1 5 1000000000 1 1 3
Sample Output 3
4000000000
Beware that the answer may not fit in a 32-bit integer.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
スパイス屋には、スパイス 1 、スパイス 2、\ldots 、スパイス 2^N-1 の 2^N-1 種類のスパイスがそれぞれ 1 個ずつ売られています。 i = 1, 2, \ldots, 2^N-1 について、スパイス i の値段は c_i 円です。 高橋君はそれらを好きなだけ買うことができます。
高橋君は帰宅後、買ったスパイスのうち 1 つ以上を選び、それらを組み合わせてカレーを作る予定です。
高橋君がスパイス A_1 、スパイス A_2 、\ldots、スパイス A_k の k 個のスパイスを組み合わせると、完成するカレーの辛さは A_1 \oplus A_2 \oplus \cdots \oplus A_k になります。
ここで、\oplus はビットごとの排他的論理和を表します。
高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず 1 以上 2^N-1 以下の任意の整数の辛さのカレーを作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してください。
制約
- 2 \leq N \leq 16
- 1 \leq c_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
c_1 c_2 \ldots c_{2^N-1}
出力
高橋君が支払う金額としてあり得る最小値を出力せよ。
入力例 1
2 4 5 3
出力例 1
7
高橋君がスパイス 1 とスパイス 3 を買うと、下記の通り、1 以上 3 以下の任意の整数の辛さのカレーを作ることができます。
- 辛さ 1 のカレーを作るには、スパイス 1 のみを使い、
- 辛さ 2 のカレーを作るには、スパイス 1 とスパイス 3 を組み合わせ、
- 辛さ 3 のカレーを作るには、スパイス 3 のみを使えば良いです。
このとき高橋君が支払う金額は c_1 + c_3 = 4 + 3 = 7 円であり、これが高橋君が支払う金額としてあり得る最小値です。
入力例 2
4 9 7 9 7 10 4 3 9 4 8 10 5 6 3 8
出力例 2
15
Score : 500 points
Problem Statement
The shop supaisu-ya sells 2^N-1 kinds of spices: Spice 1, Spice 2, \ldots, Spice 2^N-1. One pack of each spice is in stock. For each i = 1, 2, \ldots, 2^N-1, Spice i costs c_i yen. Takahashi can buy any of these spices.
He plans to make curry after getting home by choosing one or more of the bought spices and mixing them.
If k spices, Spice A_1, Spice A_2, \ldots, Spice A_k, are mixed, the hotness of the resulting curry is A_1 \oplus A_2 \oplus \cdots \oplus A_k, where \oplus denotes the bitwise XOR.
Takahashi wants to decide the hotness of the curry based on his feeling after getting home. For now, he will buy a set of spices that allows him to make curry of any hotness from 1 through 2^N-1. Print the minimum possible amount of money Takahashi pays.
Constraints
- 2 \leq N \leq 16
- 1 \leq c_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
c_1 c_2 \ldots c_{2^N-1}
Output
Print the minimum possible amount of money Takahashi pays.
Sample Input 1
2 4 5 3
Sample Output 1
7
If Takahashi buys Spice 1 and 3, he can make curry of any hotness from 1 through 3, as follows.
- To make curry of hotness 1, use just Spice 1.
- To make curry of hotness 2, mix Spice 1 and Spice 3.
- To make curry of hotness 3, use just Spice 3.
Here, Takahashi pays c_1 + c_3 = 4 + 3 = 7 yen, which is the minimum possible amount he pays.
Sample Input 2
4 9 7 9 7 10 4 3 9 4 8 10 5 6 3 8
Sample Output 2
15