実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
正整数 n に対し、n を十進法表記した文字列を \mathrm{str}(n) で表します。
正整数 n について、ある正整数 m が存在して \mathrm{str}(n) が \mathrm{str}(m) を 2 個以上連結したものになっているとき、 n は「周期的な数」であるといいます。たとえば 11,\ 1212,\ 123123123 は「周期的な数」です。
11 以上の正整数 N が与えられます。 N 以下の「周期的な数」の最大値を求めてください。 N 以下の「周期的な数」は 1 つ以上存在することが示せます。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \leq T \leq 10^4
- 11 \leq N < 10^{18}
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
T \mathrm{case}_1 \vdots \mathrm{case}_T
各ケースは以下の形式で与えられます。
N
出力
T 行出力してください。i 行目には i 番目のテストケースに対する答えを出力してください。
入力例 1
3 1412 23 498650499498649123
出力例 1
1313 22 498650498650498650
1 個目のテストケースについて、 1412 以下の「周期的な数」にはたとえば 11,\ 222,\ 1212,\ 1313 などが考えられますが、このうち最大のものは 1313 です。
Score : 400 points
Problem Statement
For a positive integer n, let \mathrm{str}(n) be the string representing n in decimal.
We say that a positive integer n is periodic when there exists a positive integer m such that \mathrm{str}(n) is the concatenation of two or more copies of \mathrm{str}(m). For example, 11, 1212, and 123123123 are periodic.
You are given a positive integer N at least 11. Find the greatest periodic number at most N. It can be proved that there is at least one periodic number at most N.
You will get T test cases to solve.
Constraints
- 1 \leq T \leq 10^4
- 11 \leq N < 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
T \mathrm{case}_1 \vdots \mathrm{case}_T
Each case is given in the following format:
N
Output
Print T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
3 1412 23 498650499498649123
Sample Output 1
1313 22 498650498650498650
For the first test case, the periodic numbers at most 1412 include 11, 222, 1212, 1313, and the greatest is 1313.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
正整数 N,\ M が与えられます。
長さ N の正整数列 A=(A_1,\ A_2,\ \dots,\ A_N) であって、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。
- 1 \leq A_1 < A_2 < \dots < A_N \leq M
- B_i = A_1 \oplus A_2 \oplus \dots \oplus A_i としたとき、 B_1 < B_2 < \dots < B_N
ただしここで、 \oplus はビット単位 \mathrm{XOR} 演算を表します。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 1 \leq N \leq M < 2^{60}
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N M
出力
答えを出力してください。
入力例 1
2 4
出力例 1
5
例えば (A_1,\ A_2)=(1,\ 3) とすると A_1 < A_2 であり、B_1=A_1=1,\ B_2=A_1\oplus A_2=2 より B_1 < B_2 が成り立つので条件を満たします。
この他には (A_1,\ A_2)=(1,\ 2),\ (1,\ 4),\ (2,\ 4),\ (3,\ 4) が条件を満たします。
入力例 2
4 4
出力例 2
0
入力例 3
10 123456789
出力例 3
205695670
Score : 500 points
Problem Statement
You are given positive integers N and M.
Find the number of sequences A=(A_1,\ A_2,\ \dots,\ A_N) of N positive integers that satisfy the following conditions, modulo 998244353.
- 1 \leq A_1 < A_2 < \dots < A_N \leq M.
- B_1 < B_2 < \dots < B_N, where B_i = A_1 \oplus A_2 \oplus \dots \oplus A_i.
Here, \oplus denotes bitwise \mathrm{XOR}.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:
- When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1 \leq N \leq M < 2^{60}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
2 4
Sample Output 1
5
For example, (A_1,\ A_2)=(1,\ 3) counts, since A_1 < A_2 and B_1 < B_2 where B_1=A_1=1,\ B_2=A_1\oplus A_2=2.
The other pairs that count are (A_1,\ A_2)=(1,\ 2),\ (1,\ 4),\ (2,\ 4),\ (3,\ 4).
Sample Input 2
4 4
Sample Output 2
0
Sample Input 3
10 123456789
Sample Output 3
205695670
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
長さ 2N の文字列 S=S_1S_2\dots S_{2N} について、 S が N 個の (
, および N 個の )
で構成されるとき、 S は「括弧列」であるといいます。
また、「括弧列」S のうち、以下のいずれかに該当するものを「正しい括弧列」といいます。
- 空文字列
- ある「正しい括弧列」A が存在して
(
, A,)
をこの順に連結した文字列 - ある空でない「正しい括弧列」A,\ B が存在して、 A,\ B をこの順に連結した文字列
1 から 2N までの整数からなる 2 つの順列 P=(P_1,\ P_2,\ \dots,\ P_{2N}),\ Q=(Q_1,\ Q_2,\ \dots,\ Q_{2N}) が与えられます。
以下の条件を満たすような「括弧列」S=S_1S_2\dots S_{2N} が存在するか判定してください。
- S_{p_1}S_{p_2}\dots S_{p_{2N}} が「正しい括弧列」となるような 1 から 2N までの整数の順列 p のうち、辞書式順序で最小のものが P
- S_{p_1}S_{p_2}\dots S_{p_{2N}} が「正しい括弧列」となるような 1 から 2N までの整数の順列 p のうち、辞書式順序で最大のものが Q
存在する場合は 1 つ求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P_i,Q_i \leq 2N
- P,\ Q はそれぞれ 1 から 2N までの整数の順列
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N P_1 P_2 \dots P_{2N} Q_1 Q_2 \dots Q_{2N}
出力
上記のような「括弧列」S が存在する場合、そのうち 1 つを出力してください。答えが複数存在する場合はいずれを出力してもかまいません。
存在しない場合は -1
を出力してください。
入力例 1
2 1 2 4 3 4 3 1 2
出力例 1
())(
S= ())(
のとき、S_{p_1}S_{p_2}S_{p_3}S_{p_4} が「正しい括弧列」となる p は p=(1,\ 4,\ 2,\ 3),\ (1,\ 4,\ 3,\ 2) などが考えられますが、このうち辞書式順序で最小のものは p=(1,\ 2,\ 4,\ 3) 、最大のものは p=(4,\ 3,\ 1,\ 2) であり、 S は条件を満たします。
入力例 2
2 1 3 2 4 4 3 2 1
出力例 2
-1
条件を満たす S は存在しません。
入力例 3
3 2 1 5 3 4 6 6 5 3 4 2 1
出力例 3
-1
Score : 600 points
Problem Statement
A string of length 2N, S=S_1S_2\dots S_{2N}, is said to be a parenthesis sequence when S is composed of N (
s and N )
s.
Additionally, a parenthesis sequence S is said to be correct when it is one of the following.
- An empty string.
- The concatenation of
(
, A,)
in this order, where A is a correct parenthesis sequence. - The concatenation of A, B in this order, where A and B are non-empty correct parenthesis sequences.
You are given two permutations P=(P_1,\ P_2,\ \dots,\ P_{2N}) and Q=(Q_1,\ Q_2,\ \dots,\ Q_{2N}) of the integers from 1 to 2N.
Determine whether there exists a parenthesis sequence S=S_1S_2\dots S_{2N} that satisfies the following conditions.
- P is the lexicographically smallest permutation p of the integers from 1 to 2N such that S_{p_1}S_{p_2}\dots S_{p_{2N}} is a correct parenthesis sequence.
- Q is the lexicographically largest permutation p of the integers from 1 to 2N such that S_{p_1}S_{p_2}\dots S_{p_{2N}} is a correct parenthesis sequence.
If such a parenthesis sequence exists, find one.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P_i,Q_i \leq 2N
- Each of P and Q is a permutation of 1 to 2N.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_1 P_2 \dots P_{2N} Q_1 Q_2 \dots Q_{2N}
Output
If there exists a parenthesis sequence S that satisfies the conditions above, print one such sequence. If there are multiple such sequences, you may print any of them.
If there is no such sequence, print -1
.
Sample Input 1
2 1 2 4 3 4 3 1 2
Sample Output 1
())(
For S= ())(
, some of the permutations p such that S_{p_1}S_{p_2}S_{p_3}S_{p_4} is a correct parenthesis sequence are p=(1,\ 4,\ 2,\ 3),\ (1,\ 4,\ 3,\ 2). The lexicographically smallest and largest among them are p=(1,\ 2,\ 4,\ 3) and p=(4,\ 3,\ 1,\ 2), satisfying the conditions.
Sample Input 2
2 1 3 2 4 4 3 2 1
Sample Output 2
-1
No S satisfies the conditions.
Sample Input 3
3 2 1 5 3 4 6 6 5 3 4 2 1
Sample Output 3
-1
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
正整数からなる集合 S について、任意の a,\ b \in S\ (a\neq b) について b が a の倍数でないとき、 S を「良い集合」と呼びます。
N 個の 1 以上 2M 以下の整数からなる集合 S=\lbrace A_1,\ A_2,\ \dots,\ A_N\rbrace が与えられます。
各 i=1,\ 2,\ \dots,\ N に対し、A_i を含む S の部分集合であって、要素数が M である「良い集合」が存在するか判定してください。
制約
- M \leq N \leq 2M
- 1 \leq M \leq 3 \times 10^5
- 1 \leq A_1 < A_2 < \dots < A_N \leq 2M
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N M A_1 A_2 \dots A_{N}
出力
N 行出力してください。 i 行目には A_i を含む S の部分集合であって、要素数が M である「良い集合」が存在する場合 Yes
を、存在しない場合 No
を出力してください。
入力例 1
5 3 1 2 3 4 5
出力例 1
No Yes Yes Yes Yes
A_1=1 を含む「良い集合」は明らかに \lbrace 1\rbrace しか存在せず、要素数は 1 しかないため、i=1 に対する答えは No
です。
A_2=2 を含む「良い集合」としては例えば \lbrace 2,\ 3,\ 5\rbrace が考えられます。このことから i=2 に対する答えは Yes
です。
入力例 2
4 4 2 4 6 8
出力例 2
No No No No
入力例 3
13 10 2 3 4 6 7 9 10 11 13 15 17 19 20
出力例 3
No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No
Score : 700 points
Problem Statement
We say that a set S of positive integers is good when, for any a,\ b \in S\ (a\neq b), b is not a multiple of a.
You are given a set of N integers between 1 and 2M (inclusive): S=\lbrace A_1,\ A_2,\ \dots,\ A_N\rbrace.
For each i=1,\ 2,\ \dots,\ N, determine whether there exists a good set with M elements that is a subset of S containing A_i.
Constraints
- M \leq N \leq 2M
- 1 \leq M \leq 3 \times 10^5
- 1 \leq A_1 < A_2 < \dots < A_N \leq 2M
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_{N}
Output
Print N lines. The i-th line should contain Yes
if there exists a good set with M elements that is a subset of S containing A_i, and No
otherwise.
Sample Input 1
5 3 1 2 3 4 5
Sample Output 1
No Yes Yes Yes Yes
Trivially, the only good set containing A_1=1 is \lbrace 1\rbrace, which has just one element, so the answer for i=1 is No
.
There is a good set \lbrace 2,\ 3,\ 5\rbrace containing A_2=2, so the answer for i=2 is Yes
.
Sample Input 2
4 4 2 4 6 8
Sample Output 2
No No No No
Sample Input 3
13 10 2 3 4 6 7 9 10 11 13 15 17 19 20
Sample Output 3
No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No
実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
N^2 頂点からなる無向グラフがあります。はじめ、グラフは辺を持ちません。 0 \leq i,\ j < N を満たす整数の組 (i,\ j) それぞれについて、それに対応する頂点がひとつ存在し、その頂点を (i,\ j) と呼びます。
Q 個のクエリが与えられます。i 番目のクエリでは 4 つの整数 a_i,\ b_i,\ c_i,\ d_i が与えられるので以下のように順番に処理してください。
- 各 k\ (0 \leq k < N) について、2 頂点 ((a_i+k) \bmod N,\ (b_i+k) \bmod N),\ ((c_i+k) \bmod N,\ (d_i+k) \bmod N) 間に辺を追加してください。その後、グラフの連結成分数を出力してください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq a_i,\ b_i,\ c_i,\ d_i < N
- (a_i,\ b_i) \neq (c_i,\ d_i)
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N Q a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2 \vdots a_Q b_Q c_Q d_Q
出力
Q 行出力してください。i 行目には i 番目のクエリにおけるグラフの連結成分数を出力してください。
入力例 1
3 3 0 0 1 2 2 0 0 0 1 1 2 2
出力例 1
6 4 4
1 番目のクエリでは頂点 (0,\ 0),\ (1,\ 2) 間、(1,\ 1),\ (2,\ 0) 間、(2,\ 2),\ (0,\ 1) 間に辺が追加されます。これにより連結成分数は 9 から 6 に変化します。
入力例 2
4 3 0 0 2 2 2 3 1 2 1 1 3 3
出力例 2
14 11 11
クエリ処理の結果、グラフは単純グラフではなくなることがあります。
入力例 3
6 5 0 0 1 1 1 2 3 4 1 1 5 3 2 0 1 5 5 0 3 3
出力例 3
31 27 21 21 19
Score : 700 points
Problem Statement
There is an undirected graph with N^2 vertices. Initially, it has no edges. For each pair of integers (i,\ j) such that 0 \leq i,\ j < N, the graph has a corresponding vertex called (i,\ j).
You will get Q queries, which should be processed in order. The i-th query, which gives you four integers a_i,\ b_i,\ c_i,\ d_i, is as follows.
- For each k (0 \leq k < N), add an edge between two vertices ((a_i+k) \bmod N,\ (b_i+k) \bmod N) and ((c_i+k) \bmod N,\ (d_i+k) \bmod N). Then, print the current number of connected components in the graph.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq a_i,\ b_i,\ c_i,\ d_i < N
- (a_i,\ b_i) \neq (c_i,\ d_i)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2 \vdots a_Q b_Q c_Q d_Q
Output
Print Q lines. The i-th line should contain the number of connected components in the graph at the i-th query.
Sample Input 1
3 3 0 0 1 2 2 0 0 0 1 1 2 2
Sample Output 1
6 4 4
The first query adds an edge between (0,\ 0),\ (1,\ 2), between (1,\ 1),\ (2,\ 0), and between (2,\ 2),\ (0,\ 1), changing the number of connected components from 9 to 6.
Sample Input 2
4 3 0 0 2 2 2 3 1 2 1 1 3 3
Sample Output 2
14 11 11
The graph after queries may not be simple.
Sample Input 3
6 5 0 0 1 1 1 2 3 4 1 1 5 3 2 0 1 5 5 0 3 3
Sample Output 3
31 27 21 21 19
実行時間制限: 8 sec / メモリ制限: 1024 MB
配点 : 1100 点
問題文
A
, B
, C
, D
のみからなる N 個の文字列 S_i\ (1\le i \le N) が与えられます。
A
, B
, C
, D
のみからなる文字列 T に対し、以下の操作を考えます。
- どの S_i も T の部分文字列にならなくなるまで、以下を繰り返す。
- S_i, および T が S_i を含む場所をひとつ選び、その場所から S_i を取り除いて前後を連結する
部分文字列とは?
部分文字列とは連続する部分列のことを指します。例えばA
, AB
, BC
は ABC
の部分文字列ですが、BA
や AC
は ABC
の部分文字列ではありません。
T が「悪い文字列」であるとは、T に対する操作結果として得られる文字列が複数存在することをいいます。
「悪い文字列」が存在するか判定してください。
制約
- 1 \leq N \leq 10^6
- 1 \leq |S_i| \leq 2 \times 10^6
- |S_1|+|S_2|+\dots +|S_N| \leq 2 \times 10^6
- i\neq j ならば S_i \neq S_j
- S_i は
A
,B
,C
,D
のみからなる文字列
入力
入力は以下の形式で標準入力から与えられます。
N S_1 S_2 \vdots S_N
出力
「悪い文字列」が存在する場合、 Yes
と出力してください。
存在しない場合、 No
と出力してください。
入力例 1
3 A B C
出力例 1
No
T に対する操作結果として得られる文字列は T から A
, B
, C
をすべて除いたもののみです。
入力例 2
1 ABA
出力例 2
Yes
例えば T=ABABA
に対する操作の結果として得られる文字列は AB
, BA
の 2 つあるので T は「悪い文字列」です。
入力例 3
4 CBA ACB AD CAB
出力例 3
Yes
Score : 1100 points
Problem Statement
You are given N srings S_i\ (1\le i \le N) consisting of A
, B
, C
, D
.
Consider the operation below on a string T consisting of A
, B
, C
, D
.
- Repeat the following until T contains none of the strings S_i as a substring.
- Choose an S_i and one of its occurrences in T, remove that occurrence from T, and concatenate the remaining parts.
What is a substring?
A substring of a string is its contiguous subsequence. For example,A
, AB
, and BC
are substrings of ABC
, while BA
and AC
are not.
We say that the string T is bad when multiple strings can result from the operation above.
Determine whether a bad string exists.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq |S_i| \leq 2 \times 10^6
- |S_1|+|S_2|+\dots +|S_N| \leq 2 \times 10^6
- S_i \neq S_j if i\neq j.
- S_i is a string consisting of
A
,B
,C
,D
.
Input
Input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
If a bad string exists, print Yes
.
Otherwise, print No
.
Sample Input 1
3 A B C
Sample Output 1
No
The only string we can get from T is what remains after removing all occurrences of A
, B
, C
from T.
Sample Input 2
1 ABA
Sample Output 2
Yes
For example, from T= ABABA
, we can get two strings: AB
and BA
, so T is a bad string.
Sample Input 3
4 CBA ACB AD CAB
Sample Output 3
Yes