Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の狭義単調増加列 A=(A _ 1,A _ 2,\ldots,A _ N) と、長さ M の狭義単調増加列 B=(B _ 1,B _ 2,\ldots,B _ M) が与えられます。 ここで、すべての i,j\ (1\leq i\leq N,1\leq j\leq M) について A _ i\neq B _ j が成り立っています。
長さ N+M の狭義単調増加列 C=(C _ 1,C _ 2,\ldots,C _ {N+M}) を、次の操作を行った結果得られる列として定めます。
- C を A と B を連結した列とする。厳密には、i=1,2,\ldots,N について C _ i=A _ i とし、i=N+1,N+2,\ldots,N+M について C _ i=B _ {i-N} とする。
- C を昇順にソートする。
A _ 1,A _ 2,\ldots,A _ N と B _ 1,B _ 2,\ldots,B _ M がそれぞれ C では何番目にあるか求めてください。 より厳密には、まず i=1,2,\ldots,N について C _ k=A _ i を満たす k を順に求めたのち、j=1,2,\ldots,M について C _ k=B _ j を満たす k を順に求めてください。
制約
- 1\leq N,M\leq 10^5
- 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
- 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
- すべての i,j\ (1\leq i\leq N,1\leq j\leq M) について A _ i\neq B _ j
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A _ 1 A _ 2 \ldots A _ N B _ 1 B _ 2 \ldots B _ M
出力
答えを 2 行で出力せよ。
1 行目には A _ 1,A _ 2,\ldots,A _ N がそれぞれ C では何番目にあるかを空白区切りで出力せよ。
2 行目には B _ 1,B _ 2,\ldots,B _ M がそれぞれ C では何番目にあるかを空白区切りで出力せよ。
入力例 1
4 3 3 14 15 92 6 53 58
出力例 1
1 3 4 7 2 5 6
C は (3,6,14,15,53,58,92) となります。 A=(3,14,15,92) の要素はそれぞれ 1,3,4,7 番目にあり、B=(6,53,58) の要素はそれぞれ 2,5,6 番目にあります。
入力例 2
4 4 1 2 3 4 100 200 300 400
出力例 2
1 2 3 4 5 6 7 8
入力例 3
8 12 3 4 10 15 17 18 22 30 5 7 11 13 14 16 19 21 23 24 27 28
出力例 3
1 2 5 9 11 12 15 20 3 4 6 7 8 10 13 14 16 17 18 19
Score : 300 points
Problem Statement
You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.
- Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
- Sort C in ascending order.
For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.
Constraints
- 1\leq N,M\leq 10^5
- 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
- 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
- A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M A _ 1 A _ 2 \ldots A _ N B _ 1 B _ 2 \ldots B _ M
Output
Print the answer in two lines.
The first line should contain the positions of A _ 1,A _ 2,\ldots,A _ N in C, with spaces in between.
The second line should contain the positions of B _ 1,B _ 2,\ldots,B _ M in C, with spaces in between.
Sample Input 1
4 3 3 14 15 92 6 53 58
Sample Output 1
1 3 4 7 2 5 6
C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).
Sample Input 2
4 4 1 2 3 4 100 200 300 400
Sample Output 2
1 2 3 4 5 6 7 8
Sample Input 3
8 12 3 4 10 15 17 18 22 30 5 7 11 13 14 16 19 21 23 24 27 28
Sample Output 3
1 2 5 9 11 12 15 20 3 4 6 7 8 10 13 14 16 17 18 19
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
配点 : 400 点
問題文
長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
以下の 2 条件をともに満たすような整数の組 (i,j,k) の個数を求めてください。
- 1\leq i \lt j \lt k \leq N
- A_i,A_j,A_k は相異なる
制約
- 3 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 2\times 10^5
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
4 3 1 4 1
出力例 1
2
条件を満たす整数の組 (i,j,k) は (1,2,3),(1,3,4) の 2 つです。
入力例 2
10 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990
出力例 2
120
入力例 3
15 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
出力例 3
355
Score : 400 points
Problem Statement
You are given a sequence of length N: A=(A_1,A_2,\ldots,A_N).
Find the number of triples (i,j,k) that satisfy both of the following conditions.
- 1\leq i \lt j \lt k \leq N
- A_i, A_j, and A_k are distinct.
Constraints
- 3 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 2\times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
4 3 1 4 1
Sample Output 1
2
The two triples (i,j,k) satisfying the conditions are (1,2,3) and (1,3,4).
Sample Input 2
10 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990
Sample Output 2
120
Sample Input 3
15 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
Sample Output 3
355
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
全ての要素が 0 で初期化された長さ N の整数列 A=(A_1,A_2,\ldots,A_N) があります。また、集合 S があります。はじめ S は空です。
以下の Q 個のクエリを順に行います。Q 個のクエリを全て処理した後の数列 A の各要素の値を求めてください。 i 番目のクエリは以下の形式です。
- 整数 x_i が与えられる。整数 x_i が S に含まれる場合、S から x_i を削除する。そうでない場合、S に x_i を追加する。次に、j=1,2,\ldots,N について、j\in S ならば A_j に |S| を加算する。
なお、|S| は集合 S の要素数を意味します。例えば S=\lbrace 3,4,7\rbrace のとき、|S|=3 です。
制約
- 1\leq N,Q\leq 2\times10^5
- 1\leq x_i\leq N
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q x_1 x_2 \ldots x_Q
出力
クエリを全て処理した後の数列 A を以下の形式で出力せよ。
A_1 A_2 \ldots A_N
入力例 1
3 4 1 3 3 2
出力例 1
6 2 2
1 番目のクエリでは、S に 1 を追加し、S=\lbrace 1\rbrace となります。その後、A_1 に |S|=1 を加算します。A=(1,0,0) となります。
2 番目のクエリでは、S に 3 を追加し、S=\lbrace 1,3\rbrace となります。その後、A_1,A_3 に |S|=2 を加算します。A=(3,0,2) となります。
3 番目のクエリでは、S から 3 を削除し、S=\lbrace 1\rbrace となります。その後、A_1 に |S|=1 を加算します。A=(4,0,2) となります。
4 番目のクエリでは、S に 2 を追加し、S=\lbrace 1,2\rbrace となります。その後、A_1,A_2 に |S|=2 を加算します。A=(6,2,2) となります。
最終的に、A=(6,2,2) となります。
入力例 2
4 6 1 2 3 2 4 2
出力例 2
15 9 12 7
Score: 500 points
Problem Statement
There is an integer sequence A=(A_1,A_2,\ldots,A_N) of length N, where all elements are initially set to 0. Also, there is a set S, which is initially empty.
Perform the following Q queries in order. Find the value of each element in the sequence A after processing all Q queries. The i-th query is in the following format:
- An integer x_i is given. If the integer x_i is contained in S, remove x_i from S. Otherwise, insert x_i to S. Then, for each j=1,2,\ldots,N, add |S| to A_j if j\in S.
Here, |S| denotes the number of elements in the set S. For example, if S=\lbrace 3,4,7\rbrace, then |S|=3.
Constraints
- 1\leq N,Q\leq 2\times10^5
- 1\leq x_i\leq N
- All given numbers are integers.
Input
The input is given from Standard Input in the following format:
N Q x_1 x_2 \ldots x_Q
Output
Print the sequence A after processing all queries in the following format:
A_1 A_2 \ldots A_N
Sample Input 1
3 4 1 3 3 2
Sample Output 1
6 2 2
In the first query, 1 is inserted to S, making S=\lbrace 1\rbrace. Then, |S|=1 is added to A_1. The sequence becomes A=(1,0,0).
In the second query, 3 is inserted to S, making S=\lbrace 1,3\rbrace. Then, |S|=2 is added to A_1 and A_3. The sequence becomes A=(3,0,2).
In the third query, 3 is removed from S, making S=\lbrace 1\rbrace. Then, |S|=1 is added to A_1. The sequence becomes A=(4,0,2).
In the fourth query, 2 is inserted to S, making S=\lbrace 1,2\rbrace. Then, |S|=2 is added to A_1 and A_2. The sequence becomes A=(6,2,2).
Eventually, the sequence becomes A=(6,2,2).
Sample Input 2
4 6 1 2 3 2 4 2
Sample Output 2
15 9 12 7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
以下の条件を全て満たす数列の個数を、998244353 で割った余りを求めてください。
- 数列の長さが N
- 数列の各項は 1 以上 M 以下の整数
- 最長増加部分列の長さがちょうど 3
注記
数列の部分列とは、数列から 0 個以上の要素を取り除いた後、残りの要素を元の順序で連結して得られる数列のことをいいます。
例えば、(10,30) は (10,20,30) の部分列ですが、(20,10) は (10,20,30) の部分列ではありません。
数列の最長増加部分列とは、数列の狭義単調増加な部分列のうち、長さが最大のもののことをいいます。
制約
- 3 \leq N \leq 1000
- 3 \leq M \leq 10
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
4 5
出力例 1
135
例えば (3,4,1,5) は条件を満たす数列です。
一方 (4,4,1,5) は最長増加部分列の長さが 2 なので条件を満たしません。
入力例 2
3 4
出力例 2
4
入力例 3
111 3
出力例 3
144980434
998244353 で割った余りを求めてください。
Score : 500 points
Problem Statement
Find the number of sequences that satisfy all of the conditions below, modulo 998244353.
- The length is N.
- Each of the elements is an integer between 1 and M (inclusive).
- Its longest increasing subsequence has the length of exactly 3.
Notes
A subsequence of a sequence is the result of removing zero or more elements from it and concatenating the remaining elements without changing the order. For example, (10,30) is a subsequence of (10,20,30), while (20,10) is not a subsequence of (10,20,30).
A longest increasing subsequence of a sequence is its strictly increasing subsequence with the greatest length.
Constraints
- 3 \leq N \leq 1000
- 3 \leq M \leq 10
- 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
4 5
Sample Output 1
135
One sequence that satisfies the conditions is (3,4,1,5).
On the other hand, (4,4,1,5) do not, because its longest increasing subsequence has the length of 2.
Sample Input 2
3 4
Sample Output 2
4
Sample Input 3
111 3
Sample Output 3
144980434
Find the count modulo 998244353.