Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
英小文字からなる長さ M の文字列 N 個 S_1,S_2,\dots,S_N が与えられます。ここで、S_i は互いに異なります。
これらを並び替えた文字列の列 T_1,T_2,\dots,T_N であって、以下の条件を満たすものが存在するか判定してください。
- 1 \le i \le N-1 を満たす全ての整数 i に対して、T_i を 1 文字だけ別の英小文字に変えて T_{i+1} にすることが出来る。
制約
- 2 \le N \le 8
- 1 \le M \le 5
- S_i は英小文字からなる長さ M の文字列である。(1 \le i \le N)
- S_i は互いに異なる。
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N
出力
問題文の条件を満たす列が存在するならば Yes を、そうでないならば No を出力せよ。
入力例 1
4 4 bbed abcd abed fbed
出力例 1
Yes
abcd , abed , bbed , fbed の順に並び替えると条件を満たします。
入力例 2
2 5 abcde abced
出力例 2
No
どのように並び替えても条件を満たすことは出来ません。
入力例 3
8 4 fast face cast race fact rice nice case
出力例 3
Yes
Score : 250 points
Problem Statement
You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.
Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:
- for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.
Constraints
- 2 \le N \le 8
- 1 \le M \le 5
- S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
- S_i are pairwise distinct.
Input
The input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N
Output
Print Yes if one can obtain a conforming sequence; print No otherwise.
Sample Input 1
4 4 bbed abcd abed fbed
Sample Output 1
Yes
One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.
Sample Input 2
2 5 abcde abced
Sample Output 2
No
No matter how the strings are rearranged, the condition is never satisfied.
Sample Input 3
8 4 fast face cast race fact rice nice case
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
黒板に整数 N が 1 個書かれています。
高橋君は黒板に書かれている 2 以上の整数が全て無くなるまで以下の一連の操作を繰り返します。
- 黒板に書かれている 2 以上の整数を 1 つ選び x とする。
- 黒板から x を 1 個消す。そして、2 個の整数 \left \lfloor \dfrac{x}{2} \right\rfloor, \left\lceil \dfrac{x}{2} \right\rceil を新たに黒板に書く。
- この一連の操作を行うために高橋君は x 円払う必要がある。
ここで \lfloor a \rfloor は a 以下の整数のうち最大のものを、\lceil a \rceil は a 以上の整数のうち最小のものを意味します。
操作を行えなくなった時点で高橋君が払った金額の総和は何円ですか?
なお、どのような順番で操作を行っても高橋君が払う金額の総和は一定であることが証明できます。
制約
- 2 \leq N \leq 10^{17}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
高橋君が払った金額の総和が何円であるかを出力せよ。
入力例 1
3
出力例 1
5
高橋君が行う操作の一例を挙げると次のようになります。
- はじめ、黒板には 3 が 1 個書かれている。
- 高橋君は 3 を選ぶ。高橋君は 3 円を払い、黒板から 3 を 1 個消して \left \lfloor \dfrac{3}{2} \right\rfloor = 1, \left\lceil \dfrac{3}{2} \right\rceil = 2 を新たに黒板に書く。
- 黒板には 2 が 1 個と 1 が 1 個書かれている。
- 高橋君は 2 を選ぶ。高橋君は 2 円を払い、黒板から 2 を 1 個消して \left \lfloor \dfrac{2}{2} \right\rfloor = 1, \left\lceil \dfrac{2}{2} \right\rceil = 1 を新たに黒板に書く。
- 黒板には 1 が 3 個書かれている。
- 黒板から 2 以上の整数が全て無くなったので操作を終了する。
操作全体で高橋君は 3 + 2 = 5 円払ったので、5 を出力します。
入力例 2
340
出力例 2
2888
入力例 3
100000000000000000
出力例 3
5655884811924144128
Score: 300 points
Problem Statement
There is a single integer N written on a blackboard.
Takahashi will repeat the following series of operations until all integers not less than 2 are removed from the blackboard:
- Choose one integer x not less than 2 written on the blackboard.
- Erase one occurrence of x from the blackboard. Then, write two new integers \left \lfloor \dfrac{x}{2} \right\rfloor and \left\lceil \dfrac{x}{2} \right\rceil on the blackboard.
- Takahashi must pay x yen to perform this series of operations.
Here, \lfloor a \rfloor denotes the largest integer not greater than a, and \lceil a \rceil denotes the smallest integer not less than a.
What is the total amount of money Takahashi will have paid when no more operations can be performed?
It can be proved that the total amount he will pay is constant regardless of the order in which the operations are performed.
Constraints
- 2 \leq N \leq 10^{17}
Input
The input is given from Standard Input in the following format:
N
Output
Print the total amount of money Takahashi will have paid, in yen.
Sample Input 1
3
Sample Output 1
5
Here is an example of how Takahashi performs the operations:
- Initially, there is one 3 written on the blackboard.
- He chooses 3. He pays 3 yen, erases one 3 from the blackboard, and writes \left \lfloor \dfrac{3}{2} \right\rfloor = 1 and \left\lceil \dfrac{3}{2} \right\rceil = 2 on the blackboard.
- There is one 2 and one 1 written on the blackboard.
- He chooses 2. He pays 2 yen, erases one 2 from the blackboard, and writes \left \lfloor \dfrac{2}{2} \right\rfloor = 1 and \left\lceil \dfrac{2}{2} \right\rceil = 1 on the blackboard.
- There are three 1s written on the blackboard.
- Since all integers not less than 2 have been removed from the blackboard, the process is finished.
Takahashi has paid a total of 3 + 2 = 5 yen for the entire process, so print 5.
Sample Input 2
340
Sample Output 2
2888
Sample Input 3
100000000000000000
Sample Output 3
5655884811924144128
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
正整数 x,y に対して f(x,y) を以下で定義します。
- 十進表記の x,y をそれぞれ文字列として解釈しこの順に連結して得られる文字列を z とする。z を十進表記の整数として解釈したときの値を f(x,y) とする。
例えば f(3,14)=314, f(100,1)=1001 です。
長さ N の正整数列 A=(A_1,\ldots,A_N) が与えられます。次の式の値を 998244353 で割ったあまりを求めてください。
制約
- 2\leq N\leq 2\times 10^5
- 1\leq A_i \leq 10^9
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 3 14 15
出力例 1
2044
- f(A_1,A_2)=314
- f(A_1,A_3)=315
- f(A_2,A_3)=1415
なので、答えは f(A_1,A_2)+f(A_1,A_3)+f(A_2,A_3) = 2044 です。
入力例 2
5 1001 5 1000000 1000000000 100000
出力例 2
625549048
式の値を 998244353 で割ったあまりを求めることに注意してください。
Score: 400 points
Problem Statement
For positive integers x and y, define f(x, y) as follows:
- Interpret the decimal representations of x and y as strings and concatenate them in this order to obtain a string z. The value of f(x, y) is the value of z when interpreted as a decimal integer.
For example, f(3, 14) = 314 and f(100, 1) = 1001.
You are given a sequence of positive integers A = (A_1, \ldots, A_N) of length N. Find the value of the following expression modulo 998244353:
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print the answer.
Sample Input 1
3 3 14 15
Sample Output 1
2044
- f(A_1, A_2) = 314
- f(A_1, A_3) = 315
- f(A_2, A_3) = 1415
Thus, the answer is f(A_1, A_2) + f(A_1, A_3) + f(A_2, A_3) = 2044.
Sample Input 2
5 1001 5 1000000 1000000000 100000
Sample Output 2
625549048
Be sure to calculate the value modulo 998244353.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
「ユ木」を、以下の手順で生成することができる木と定義します。
- 正整数 x,y を選ぶ
- 頂点を 1 つ用意する
- 別に x 個の頂点を用意し、それぞれを手順 2 で用意した頂点と辺で結ぶ
- 手順 3 で用意した x 個の頂点それぞれに、 y 個の葉をつける
x=4,y=2 のユ木を下図に示します。手順 2,3,4 で用意される頂点をそれぞれ赤、青、緑で示しています。

N 頂点の木 T が与えられます。頂点には 1 から N の番号が付けられており、 i\;(=1,2,\dots,N-1) 番目の辺は頂点 u_i と頂点 v_i を結びます。
T の 0 個以上の頂点とそれに隣接する辺を削除して 1 つのユ木にするとき、削除する頂点数の最小値を求めてください。なお、本問題の制約下で、T をかならずユ木にすることができます。
制約
- 3 \leq N \leq 3 \times 10^5
- 1 \leq u_i < v_i \leq N
- 与えられるグラフは木である
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
出力
答えを出力せよ。
入力例 1
8 1 3 2 3 3 4 4 5 5 6 5 7 4 8
出力例 1
1
頂点 8 を削除することで、与えられた木を x=2,y=2 のユ木にすることができます。
入力例 2
3 1 2 2 3
出力例 2
0
与えられた木はすでに x=1,y=1 のユ木です。
入力例 3
10 1 3 1 2 5 7 6 10 2 8 1 6 8 9 2 7 1 4
出力例 3
3
Score : 450 points
Problem Statement
A "Snowflake Tree" is defined as a tree that can be generated by the following procedure:
- Choose positive integers x,y.
- Prepare one vertex.
- Prepare x more vertices, and connect each of them to the vertex prepared in step 2.
- For each of the x vertices prepared in step 3, attach y leaves to it.
The figure below shows a Snowflake Tree with x=4,y=2. The vertices prepared in steps 2, 3, 4 are shown in red, blue, and green, respectively.

You are given a tree T with N vertices. The vertices are numbered 1 to N, and the i-th edge (i=1,2,\dots,N-1) connects vertices u_i and v_i.
Consider deleting zero or more vertices of T and the edges adjacent to them so that the remaining graph becomes a single Snowflake Tree. Find the minimum number of vertices that must be deleted. Under the constraints of this problem, it is always possible to transform T into a Snowflake Tree.
Constraints
- 3 \leq N \leq 3 \times 10^5
- 1 \leq u_i < v_i \leq N
- The given graph is a tree.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
Output
Print the answer.
Sample Input 1
8 1 3 2 3 3 4 4 5 5 6 5 7 4 8
Sample Output 1
1
By deleting vertex 8, the given tree can be transformed into a Snowflake Tree with x=2,y=2.
Sample Input 2
3 1 2 2 3
Sample Output 2
0
The given tree is already a Snowflake Tree with x=1,y=1.
Sample Input 3
10 1 3 1 2 5 7 6 10 2 8 1 6 8 9 2 7 1 4
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
N 行 N 列のグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。各マスには 1 から 9 までの数字が書かれており、マス (i,j) には数字 A_{i,j} が書かれています。
はじめ、コマがマス (1,1) にあります。また、 S を空文字列とし、以下の操作を 2N-1 回繰り返します:
- S の末尾に現在コマが存在するマスに書かれた数字を連結する。
- コマを現在のマスの下か右に 1 マス移動する。ただし、 2N-1 回目の操作では移動させない。
2N-1 回の操作の後、コマはマス (N,N) に存在し、 S の長さは 2N-1 となります。
最終的な文字列 S を整数としてみた値を M で割ったあまりがスコアとなります。
達成可能なスコアの最大値を求めてください。
制約
- 1\le N\le 20
- 2\le M\le 10^9
- 1\le A_{i,j}\le 9
- 入力される値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M
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}
出力
答えを出力せよ。
入力例 1
2 7 1 2 3 1
出力例 1
5
コマの動かし方は以下の 2 通りがあります:
- コマを (1,1),(1,2),(2,2) と順に動かしていく。S=
121となり、この場合のスコアは 121 を 7 で割った 2 である。 - コマを (1,1),(2,1),(2,2) と順に動かしていく。S=
131となり、この場合のスコアは 131 を 7 で割った 5 である。
スコアの最大値は 5 なので、 5 を出力してください。
入力例 2
3 100000 1 2 3 3 5 8 7 1 2
出力例 2
13712
入力例 3
5 402 8 1 3 8 9 8 2 4 1 8 4 1 8 5 9 6 2 1 6 7 6 6 7 7 6
出力例 3
384
Score : 525 points
Problem Statement
There is an N\times N grid. Let cell (i,j) denote the cell in the i-th row from the top and j-th column from the left. Each cell contains a digit from 1 to 9; cell (i,j) contains A_{i,j}.
Initially, a token is on cell (1,1). Let S be an empty string. Repeat the following operation 2N-1 times:
- Append to the end of S the digit in the current cell.
- Move the token one cell down or one cell to the right. However, do not move it in the (2N-1)-th operation.
After 2N-1 operations, the token is on cell (N,N) and the length of S is 2N-1.
Interpret S as an integer. The score is the remainder when this integer is divided by M.
Find the maximum achievable score.
Constraints
- 1 \leq N \leq 20
- 2 \leq M \leq 10^9
- 1 \leq A_{i,j} \leq 9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
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
Print the answer.
Sample Input 1
2 7 1 2 3 1
Sample Output 1
5
There are two ways to move the token:
- Move through (1,1),(1,2),(2,2). Then S=
121, and the score is the remainder when 121 is divided by 7, which is 2. - Move through (1,1),(2,1),(2,2). Then S=
131, and the score is the remainder when 131 is divided by 7, which is 5.
The maximum score is 5, so print 5.
Sample Input 2
3 100000 1 2 3 3 5 8 7 1 2
Sample Output 2
13712
Sample Input 3
5 402 8 1 3 8 9 8 2 4 1 8 4 1 8 5 9 6 2 1 6 7 6 6 7 7 6
Sample Output 3
384