AtCoder Grand Contest 036

A - Triangle

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

整数 S が与えられます。以下の条件をすべて満たす 6 つの整数 X_1,Y_1,X_2,Y_2,X_3,Y_3 を 1 組求めてください。

0 \leq X_1,Y_1,X_2,Y_2,X_3,Y_3 \leq 10^9
二次元平面上の 3 つの点 (X_1,Y_1),(X_2,Y_2),(X_3,Y_3) を頂点とする三角形の面積が S/2 である。

なお、この問題の制約の範囲で、条件を満たすような 6 つの整数が必ず存在することが証明できます。

制約

1 \leq S \leq 10^{18}
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

出力

条件を満たす 6 つの整数 X_1,Y_1,X_2,Y_2,X_3,Y_3 を、この順に空白区切りで出力せよ。解が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

出力例 1

1 0 2 2 0 1

二次元平面上の 3 つの点 (1,0),(2,2),(0,1) を頂点とする三角形の面積は 3/2 です。なお、3 0 3 1 0 1 や、1 0 0 1 2 2 という出力をしても正解と判定されます。

入力例 2

出力例 2

0 0 10 0 0 10

入力例 3

311114770564041497

出力例 3

314159265 358979323 846264338 327950288 419716939 937510582

Score : 400 points

Problem Statement

Given is an integer S. Find a combination of six integers X_1,Y_1,X_2,Y_2,X_3, and Y_3 that satisfies all of the following conditions:

0 \leq X_1,Y_1,X_2,Y_2,X_3,Y_3 \leq 10^9
The area of the triangle in a two-dimensional plane whose vertices are (X_1,Y_1),(X_2,Y_2), and (X_3,Y_3) is S/2.

We can prove that there always exist six integers that satisfy the conditions under the constraints of this problem.

Constraints

1 \leq S \leq 10^{18}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

Output

Print six integers X_1,Y_1,X_2,Y_2,X_3, and Y_3 that satisfy the conditions, in this order, with spaces in between. If multiple solutions exist, any of them will be accepted.

Sample Input 1

Sample Output 1

1 0 2 2 0 1

The area of the triangle in a two-dimensional plane whose vertices are (1,0),(2,2), and (0,1) is 3/2. Printing 3 0 3 1 0 1 or 1 0 0 1 2 2 will also be accepted.

Sample Input 2

Sample Output 2

0 0 10 0 0 10

Sample Input 3

311114770564041497

Sample Output 3

314159265 358979323 846264338 327950288 419716939 937510582

B - Do Not Duplicate

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

長さ N \times K の数列 X=(X_0,X_1,\cdots,X_{N \times K-1}) があります。数列 X の要素は長さ N の数列 A=(A_0,A_1,\cdots,A_{N-1}) によって表され、全ての i,j (0 \leq i \leq K-1,\ 0 \leq j \leq N-1) について、 X_{i \times N + j}=A_j です。

すぬけさんは、整数列 s を持っています。最初、s は空です。すぬけさんはこれから、すべての i=0,1,2,\cdots,N \times K-1 について、この順に、以下の操作を行います。

s が X_i を含んでいない場合: s の末尾に X_i を追加する。
s が X_i を含んでいる場合: s が X_i を含まなくなるまで、s の末尾の要素を削除し続ける。このとき、X_i を末尾に加えないことに注意せよ。

全ての操作が終わったあとの数列 s の状態を求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq K \leq 10^{12}
1 \leq A_i \leq 2 \times 10^5
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N K
A_0 A_1 \cdots A_{N-1}

出力

全ての操作が終わったあとの数列 s の要素を、先頭から末尾の順に空白区切りで出力せよ。

入力例 1

3 2
1 2 3

出力例 1

2 3

X=(1,2,3,1,2,3) です。操作は、以下のように行われます。

i=0: s が 1 を含まないので、s の末尾に 1 を追加する。s=(1) となる。
i=1: s が 2 を含まないので、s の末尾に 2 を追加する。s=(1,2) となる。
i=2: s が 3 を含まないので、s の末尾に 3 を追加する。s=(1,2,3) となる。
i=3: s が 1 を含むので、s が 1 を含む限り、末尾の要素を削除し続ける。s は (1,2,3)→(1,2)→(1)→() と変化する。
i=4: s が 2 を含まないので、s の末尾に 2 を追加する。s=(2) となる。
i=5: s が 3 を含まないので、s の末尾に 3 を追加する。s=(2,3) となる。

入力例 2

5 10
1 2 3 2 3

出力例 2

入力例 3

6 1000000000000
1 1 2 2 3 3

出力例 3

数列 s が空のこともあります。

入力例 4

11 97
3 1 4 1 5 9 2 6 5 3 5

出力例 4

9 2 6

Score : 700 points

Problem Statement

We have a sequence of N \times K integers: X=(X_0,X_1,\cdots,X_{N \times K-1}). Its elements are represented by another sequence of N integers: A=(A_0,A_1,\cdots,A_{N-1}). For each pair i, j (0 \leq i \leq K-1,\ 0 \leq j \leq N-1), X_{i \times N + j}=A_j holds.

Snuke has an integer sequence s, which is initially empty. For each i=0,1,2,\cdots,N \times K-1, in this order, he will perform the following operation:

If s does not contain X_i: add X_i to the end of s.
If s does contain X_i: repeatedly delete the element at the end of s until s no longer contains X_i. Note that, in this case, we do not add X_i to the end of s.

Find the elements of s after Snuke finished the operations.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq K \leq 10^{12}
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 K
A_0 A_1 \cdots A_{N-1}

Output

Print the elements of s after Snuke finished the operations, in order from beginning to end, with spaces in between.

Sample Input 1

3 2
1 2 3

Sample Output 1

2 3

In this case, X=(1,2,3,1,2,3). We will perform the operations as follows:

i=0: s does not contain 1, so we add 1 to the end of s, resulting in s=(1).
i=1: s does not contain 2, so we add 2 to the end of s, resulting in s=(1,2).
i=2: s does not contain 3, so we add 3 to the end of s, resulting in s=(1,2,3).
i=3: s does contain 1, so we repeatedly delete the element at the end of s as long as s contains 1, which causes the following changes to s: (1,2,3)→(1,2)→(1)→().
i=4: s does not contain 2, so we add 2 to the end of s, resulting in s=(2).
i=5: s does not contain 3, so we add 3 to the end of s, resulting in s=(2,3).

Sample Input 2

5 10
1 2 3 2 3

Sample Output 2

Sample Input 3

6 1000000000000
1 1 2 2 3 3

Sample Output 3

s may be empty in the end.

Sample Input 4

11 97
3 1 4 1 5 9 2 6 5 3 5

Sample Output 4

9 2 6

C - GP 2

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

長さ N の数列 x=(x_0,x_1,\cdots,x_{N-1}) があります。最初、すべての i (0 \leq i \leq N-1) について x_i=0 です。

すぬけさんは、次の操作をちょうど M 回行います。

相異なる添字 i,j (0 \leq i,j \leq N-1,\ i \neq j) を選ぶ。そして、x_i を x_i+2 で置き換える。また、x_j を x_j+1 で置き換える。

最終的な数列 x の状態としてありうるものが何通りあるかを求めてください。ただし、答えは非常に大きくなることがあるので、998244353 で割ったあまりを求めてください。

制約

2 \leq N \leq 10^6
1 \leq M \leq 5 \times 10^5
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

最終的な数列 x の状態としてありうるものが何通りあるかを 998244353 で割ったあまりを出力せよ。

入力例 1

2 2

出力例 1

2 回の操作後の x の状態としてありうるものは以下の 3 通りです。

x=(2,4)
x=(3,3)
x=(4,2)

たとえば、x=(3,3) としたい場合、次のように操作すればよいです。

1 回目の操作：i=0,j=1 とする。x は (0,0) から (2,1) へ変化する。
2 回目の操作：i=1,j=0 とする。x は (2,1) から (3,3) へ変化する。

入力例 2

3 2

出力例 2

入力例 3

10 10

出力例 3

211428932

入力例 4

100000 50000

出力例 4

Score : 900 points

Problem Statement

We have a sequence of N integers: x=(x_0,x_1,\cdots,x_{N-1}). Initially, x_i=0 for each i (0 \leq i \leq N-1).

Snuke will perform the following operation exactly M times:

Choose two distinct indices i, j (0 \leq i,j \leq N-1,\ i \neq j). Then, replace x_i with x_i+2 and x_j with x_j+1.

Find the number of different sequences that can result after M operations. Since it can be enormous, compute the count modulo 998244353.

Constraints

2 \leq N \leq 10^6
1 \leq M \leq 5 \times 10^5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the number of different sequences that can result after M operations, modulo 998244353.

Sample Input 1

2 2

Sample Output 1

After two operations, there are three possible outcomes:

x=(2,4)
x=(3,3)
x=(4,2)

For example, x=(3,3) can result after the following sequence of operations:

First, choose i=0,j=1, changing x from (0,0) to (2,1).
Second, choose i=1,j=0, changing x from (2,1) to (3,3).

Sample Input 2

3 2

Sample Output 2

Sample Input 3

10 10

Sample Output 3

211428932

Sample Input 4

100000 50000

Sample Output 4

D - Negative Cycle

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1200 点

問題文

N 頂点からなる重み付き有向グラフがあり、頂点には 0 から N-1 までの番号がついています。

最初、このグラフには N-1 本の辺があります。このうち i 番目 (0 \leq i \leq N-2) の辺は、頂点 i から頂点 i+1 へ向かう重さ 0 の辺です。

すぬけさんはこれから、全ての i,j (0 \leq i,j \leq N-1,\ i \neq j) について、新たに辺 (i → j) を追加する操作を行います。辺の重さは、i < j なら -1、そうでないなら 1 とします。

りんごくんは、グラフに負閉路（閉路であって、そこに含まれる辺の重みの総和が 0 未満のもの）があるととても悲しいです。そこで、すぬけさんが追加した辺のうちいくつかを削除して、最終的なグラフに負閉路が含まれないようにすることにしました。すぬけさんが追加した辺 (i → j) を削除するには A_{i,j} のコストがかかります。なお、最初からあった N-1 本の辺を削除することはできません。

りんごくんが目的を達成するために必要なコストの総和の最小値を求めてください。

制約

3 \leq N \leq 500
1 \leq A_{i,j} \leq 10^9
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
A_{0,1} A_{0,2} A_{0,3} \cdots A_{0,N-1}
A_{1,0} A_{1,2} A_{1,3} \cdots A_{1,N-1}
A_{2,0} A_{2,1} A_{2,3} \cdots A_{2,N-1}
\vdots
A_{N-1,0} A_{N-1,1} A_{N-1,2} \cdots A_{N-1,N-2}

出力

りんごくんが目的を達成するために必要なコストの総和の最小値を出力せよ。

入力例 1

出力例 1

すぬけさんが追加した辺 (0 → 1) を削除すると、グラフに負閉路がないようになります。この時必要なコストは 2 で、これが最小です。

入力例 2

出力例 2

すぬけさんが追加した辺 (1 → 2) と (3 → 0) を削除すると、グラフに負閉路がないようになります。この時必要なコストは 1+1=2 で、これが最小です。

入力例 3

10
190587 2038070 142162180 88207341 215145790 38 2 5 20
32047998 21426 4177178 52 734621629 2596 102224223 5 1864
41 481241221 1518272 51 772 146 8805349 3243297 449
918151 126080576 5186563 46354 6646 491776 5750138 2897 161
3656 7551068 2919714 43035419 495 3408 26 3317 2698
455357 3 12 1857 5459 7870 4123856 2402 258
3 25700 16191 102120 971821039 52375 40449 20548149 16186673
2 16 130300357 18 6574485 29175 179 1693 2681
99 833 131 2 414045824 57357 56 302669472 95
8408 7 1266941 60620177 129747 41382505 38966 187 5151064

出力例 3

Score : 1200 points

Problem Statement

We have a weighted directed graph with N vertices numbered 0 to N-1.

The graph initially has N-1 edges. The i-th edge (0 \leq i \leq N-2) is directed from Vertex i to Vertex i+1 and has a weight of 0.

Snuke will now add a new edge (i → j) for every pair i, j (0 \leq i,j \leq N-1,\ i \neq j). The weight of the edge will be -1 if i < j, and 1 otherwise.

Ringo is a boy. A negative cycle (a cycle whose total weight is negative) in a graph makes him sad. He will delete some of the edges added by Snuke so that the graph will no longer contain a negative cycle. The cost of deleting the edge (i → j) is A_{i,j}. He cannot delete edges that have been present from the beginning.

Find the minimum total cost required to achieve Ringo's objective.

Constraints

3 \leq N \leq 500
1 \leq A_{i,j} \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_{0,1} A_{0,2} A_{0,3} \cdots A_{0,N-1}
A_{1,0} A_{1,2} A_{1,3} \cdots A_{1,N-1}
A_{2,0} A_{2,1} A_{2,3} \cdots A_{2,N-1}
\vdots
A_{N-1,0} A_{N-1,1} A_{N-1,2} \cdots A_{N-1,N-2}

Output

Print the minimum total cost required to achieve Ringo's objective.

Sample Input 1

Sample Output 1

If we delete the edge (0 → 1) added by Snuke, the graph will no longer contain a negative cycle. The cost will be 2 in this case, which is the minimum possible.

Sample Input 2

Sample Output 2

If we delete the edges (1 → 2) and (3 → 0) added by Snuke, the graph will no longer contain a negative cycle. The cost will be 1+1=2 in this case, which is the minimum possible.

Sample Input 3

10
190587 2038070 142162180 88207341 215145790 38 2 5 20
32047998 21426 4177178 52 734621629 2596 102224223 5 1864
41 481241221 1518272 51 772 146 8805349 3243297 449
918151 126080576 5186563 46354 6646 491776 5750138 2897 161
3656 7551068 2919714 43035419 495 3408 26 3317 2698
455357 3 12 1857 5459 7870 4123856 2402 258
3 25700 16191 102120 971821039 52375 40449 20548149 16186673
2 16 130300357 18 6574485 29175 179 1693 2681
99 833 131 2 414045824 57357 56 302669472 95
8408 7 1266941 60620177 129747 41382505 38966 187 5151064

Sample Output 3

E - ABC String

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1500 点

問題文

A,B,C からなる文字列 S が与えられます。

S の連続とは限らない部分列 x であって、次の条件をすべて満たすもののうち、最長のものを 1 つ求めてください。なお、S の部分列とは、S から 0 個以上の文字を削除して得られる文字列を意味します。

x に含まれる A,B,C それぞれの個数は全て等しい。
x の中で同じ文字は隣り合わない。

制約

1 \leq |S| \leq 10^6
S は A,B,C からなる。

入力

入力は以下の形式で標準入力から与えられる。

出力

条件を満たす最長の部分列を 1 つ出力せよ。解が複数ある場合は、どれを出力しても正解とみなされる。

入力例 1

ABBCBCAB

出力例 1

ACBCAB

S の部分列として、ACBCAB を考えると、これは条件を満たしており、またこれが最長です。また、ABCBCA も条件を満たす最長の部分列です。 ABCBCAB, ABBCCA なども S の部分列ですが、これらは条件を満たしません。

入力例 2

ABABABABACACACAC

出力例 2

BABCAC

入力例 3

ABCABACBCBABABACBCBCBCBCBCAB

出力例 3

ACABACABABACBCBCBCBCA

入力例 4

AAA

出力例 4

条件を満たす部分列が空文字列のみのこともあります。

Score : 1500 points

Problem Statement

Given is a string S consisting of A,B, and C.

Consider the (not necessarily contiguous) subsequences x of S that satisfy all of the following conditions:

A, B, and C all occur the same number of times in x.
No two adjacent characters in x are the same.

Among these subsequences, find one of the longest. Here a subsequence of S is a string obtained by deleting zero or more characters from S.

Constraints

1 \leq |S| \leq 10^6
S consists of A,B, and C.

Input

Input is given from Standard Input in the following format:

Output

Print one longest subsequence that satisfies the conditions. If multiple solutions exist, any of them will be accepted.

Sample Input 1

ABBCBCAB

Sample Output 1

ACBCAB

Consider the subsequence ACBCAB of S. It satisfies the conditions and is one of the longest with these properties, along with ABCBCA. On the other hand, the subsequences ABCBCAB and ABBCCA do not satisfy the conditions.

Sample Input 2

ABABABABACACACAC

Sample Output 2

BABCAC

Sample Input 3

ABCABACBCBABABACBCBCBCBCBCAB

Sample Output 3

ACABACABABACBCBCBCBCA

Sample Input 4

AAA

Sample Output 4

It is possible that only the empty string satisfies the condition.

F - Square Constraints

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1800 点

問題文

整数 N が与えられます。 (0,1,\cdots,2N-1) の順列 (P_0,P_1,\cdots,P_{2N-1}) であって、次の条件を満たすものの個数を求めてください。ただし、答えは非常に大きくなることがあるので、M で割ったあまりを求めてください。

条件: すべての i\ (0 \leq i \leq 2N-1) について、N^2 \leq i^2+P_i^2 \leq (2N)^2 が成り立つ。

制約

1 \leq N \leq 250
2 \leq M \leq 10^9
入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

条件を満たす順列の数を M で割ったあまりを出力せよ。

入力例 1

2 998244353

出力例 1

条件を満たす順列は、以下の 4 つです。

(2,3,0,1)
(2,3,1,0)
(3,2,0,1)
(3,2,1,0)

入力例 2

10 998244353

出力例 2

53999264

入力例 3

200 998244353

出力例 3

112633322

Score : 1800 points

Problem Statement

Given is an integer N. How many permutations (P_0,P_1,\cdots,P_{2N-1}) of (0,1,\cdots,2N-1) satisfy the following condition?

For each i (0 \leq i \leq 2N-1), N^2 \leq i^2+P_i^2 \leq (2N)^2 holds.

Since the number can be enormous, compute it modulo M.

Constraints

1 \leq N \leq 250
2 \leq M \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the number of permutations that satisfy the condition, modulo M.

Sample Input 1

2 998244353

Sample Output 1

Four permutations satisfy the condition:

(2,3,0,1)
(2,3,1,0)
(3,2,0,1)
(3,2,1,0)

Sample Input 2

10 998244353

Sample Output 2

53999264

Sample Input 3

200 998244353

Sample Output 3

112633322