A - A ↔ BB

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

A, B, C からなる長さ N の文字列 S が与えられます．

あなたは，S に対して以下の 2 種類の操作を好きな順序で好きな回数行うことができます．

  • S の中で A を選び，消す． 文字を消した位置に，新たに BB を書き込む．
  • S の中で隣接する 2 文字であって，BB となっているものを選び，消す． 文字を消した位置に，新たに A を書き込む．

操作を終えたあとの S としてあり得る文字列のうち，辞書順最小のものを求めてください．

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。

以下では S の i 文字目の文字を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

  1. S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
  2. S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
  3. S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

  • 1 \leq N \leq 200000
  • S は A, B, C からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ．

入力例 1

4
CBAA

出力例 1

CAAB

以下のように操作すればよいです．

  • 最初，S=CBAA である．
  • S の 3 文字目の A を消し，BB を書き込む．S=CBBBA となる．
  • S の 2,3 文字目の BB を消し，A を書き込む．S=CABA となる．
  • S の 4 文字目の A を消し，BB を書き込む．S=CABBB となる．
  • S の 3,4 文字目の BB を消し，A を書き込む．S=CAAB となる．

S を CAAB より辞書順で小さい文字列にすることはできません． よって答えは CAAB になります．

入力例 2

1
A

出力例 2

A

一度も操作を行いません．

入力例 3

6
BBBCBB

出力例 3

ABCA

Score : 300 points

Problem Statement

You are given a string S of length N consisting of A, B, C.

You can do the following two kinds of operations on S any number of times in any order.

  • Choose A in S, delete it, and insert BB at that position.
  • Choose two adjacent characters that are BB in S, delete them, and insert A at that position.

Find the lexicographically smallest possible string that S can become after your operations.

What is the lexicographical order?

Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.

Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

  1. Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
  2. If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
  3. If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

Constraints

  • 1 \leq N \leq 200000
  • S is a string of length N consisting of A, B, C.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

4
CBAA

Sample Output 1

CAAB

We should do the following.

  • Initially, we have S=CBAA.
  • Delete the 3-rd character A and insert BB, making S=CBBBA.
  • Delete the 2-nd and 3-rd characters BB and insert A, making S=CABA.
  • Delete the 4-th character A and insert BB, making S=CABBB.
  • Delete the 3-rd and 4-th characters BB and insert A, making S=CAAB.

We cannot make S lexicographically smaller than CAAB. Thus, the answer is CAAB.

Sample Input 2

1
A

Sample Output 2

A

We do no operation.

Sample Input 3

6
BBBCBB

Sample Output 3

ABCA
B - Triple Shift

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

長さ N の整数列 A=(A_1,A_2,\cdots,A_N) および B=(B_1,B_2,\cdots,B_N) が与えられます．

あなたは，以下の操作を好きな回数繰り返すことができます．

  • 整数 i (1 \leq i \leq N-2) を選び，現在の A_i,A_{i+1},A_{i+2} の値をそれぞれ x,y,z とする． そして，A_i,A_{i+1},A_{i+2} の値をそれぞれ z,x,y で置き換える．

A を B に一致させることができるかどうか判定してください．

制約

  • 3 \leq N \leq 5000
  • 1 \leq A_i,B_i \leq 5000
  • 入力される値はすべて整数

入力

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

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

出力

A を B に一致させることが可能な場合は Yes を，そうでない場合は No を出力せよ．

入力例 1

4
3 1 4 5
4 1 5 3

出力例 1

Yes

以下のように操作すればよいです．

  • 最初，A=(3,1,4,5) である．
  • i=1 で操作を行う．A=(4,3,1,5) となる．
  • i=2 で操作を行う．A=(4,5,3,1) となる．
  • i=2 で操作を行う．A=(4,1,5,3) となる．

入力例 2

3
1 2 2
2 1 2

出力例 2

Yes

入力例 3

3
1 2 3
2 3 4

出力例 3

No

Score : 400 points

Problem Statement

You are given integer sequences of length N each: A=(A_1,A_2,\cdots,A_N) and B=(B_1,B_2,\cdots,B_N).

You can repeat the following operation any number of times.

  • Choose an integer i (1 \leq i \leq N-2) and let x,y,z be the current values of A_i,A_{i+1},A_{i+2}, respectively. Then, replace the values of A_i,A_{i+1},A_{i+2} with z,x,y, respectively.

Determine whether it is possible to make A equal B.

Constraints

  • 3 \leq N \leq 5000
  • 1 \leq A_i,B_i \leq 5000
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

Output

If it is possible to make A equal B, print Yes; otherwise, print No.

Sample Input 1

4
3 1 4 5
4 1 5 3

Sample Output 1

Yes

We should do the following.

  • Initially, we have A=(3,1,4,5).
  • Do the operation with i=1, making A=(4,3,1,5).
  • Do the operation with i=2, making A=(4,5,3,1).
  • Do the operation with i=2, making A=(4,1,5,3).

Sample Input 2

3
1 2 2
2 1 2

Sample Output 2

Yes

Sample Input 3

3
1 2 3
2 3 4

Sample Output 3

No
C - Circular Addition

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

長さ N の整数列 x=(x_0,x_1,\cdots,x_{N-1}) があります（添字が 0 から始まることに注意）． 最初，x の要素はすべて 0 です．

あなたは，以下の操作を好きな回数繰り返すことができます．

  • 整数 i,k (0 \leq i \leq N-1, 1 \leq k \leq N) を選ぶ． その後，i \leq j \leq i+k-1 を満たすすべての j について，x_{j\bmod N} の値を 1 増やす．

長さ N の整数列 A=(A_0,A_1,\cdots,A_{N-1}) が与えられます． x を A に一致させるために必要な最小の操作回数を求めてください．

制約

  • 1 \leq N \leq 200000
  • 1 \leq A_i \leq 10^9
  • 入力される値はすべて整数

入力

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

N
A_0 A_1 \cdots A_{N-1}

出力

答えを出力せよ．

入力例 1

4
1 2 1 2

出力例 1

2

以下のように操作すればよいです．

  • 最初，x=(0,0,0,0) である．
  • i=1,k=3 で操作を行う．x=(0,1,1,1) となる．
  • i=3,k=3 で操作を行う．x=(1,2,1,2) となる．

入力例 2

5
3 1 4 1 5

出力例 2

7

入力例 3

1
1000000000

出力例 3

1000000000

Score : 500 points

Problem Statement

We have an integer sequence of length N: x=(x_0,x_1,\cdots,x_{N-1}) (note that its index is 0-based). Initially, all elements of x are 0.

You can repeat the following operation any number of times.

  • Choose integers i,k (0 \leq i \leq N-1, 1 \leq k \leq N). Then, for every j such that i \leq j \leq i+k-1, increase the value of x_{j\bmod N} by 1.

You are given an integer sequence of length N: A=(A_0,A_1,\cdots,A_{N-1}). Find the minimum number of operations needed to make x equal A.

Constraints

  • 1 \leq N \leq 200000
  • 1 \leq A_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 A_1 \cdots A_{N-1}

Output

Print the answer.

Sample Input 1

4
1 2 1 2

Sample Output 1

2

We should do the following.

  • Initially, we have x=(0,0,0,0).
  • Do the operation with i=1,k=3, making x=(0,1,1,1).
  • Do the operation with i=3,k=3, making x=(1,2,1,2).

Sample Input 2

5
3 1 4 1 5

Sample Output 2

7

Sample Input 3

1
1000000000

Sample Output 3

1000000000
D - Without Carry

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．

整数の組 (i,j) (1 \leq i < j \leq N) であって，A_i+A_j を筆算で計算する際に繰り上がりが発生しないものの個数を求めてください．

制約

  • 2 \leq N \leq 10^6
  • 0 \leq A_i \leq 10^6-1
  • 入力される値はすべて整数

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ．

入力例 1

4
4 8 12 90

出力例 1

3

数えるべき組 (i,j) は，(1,3),(1,4),(2,4) の 3 つです．

例えば，A_1+A_3=4+12 を計算する際には繰り上がりが発生しないので，(i,j)=(1,3) は数えます． 反対に，A_3+A_4=12+90 を計算する際には繰り上がりが発生するので，(i,j)=(3,4) は数えません．

入力例 2

20
313923 246114 271842 371982 284858 10674 532090 593483 185123 364245 665161 241644 604914 645577 410849 387586 732231 952593 249651 36908

出力例 2

6

入力例 3

5
1 1 1 1 1

出力例 3

10

Score : 600 points

Problem Statement

You are given an integer sequence of length N: A=(A_1,A_2,\cdots,A_N).

Find the number of pairs of integers (i,j) (1 \leq i < j \leq N) such that calculation of A_i+A_j by column addition does not involve carrying.

Constraints

  • 2 \leq N \leq 10^6
  • 0 \leq A_i \leq 10^6-1
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

4
4 8 12 90

Sample Output 1

3

The pairs (i,j) that count are (1,3),(1,4),(2,4).

For example, calculation of A_1+A_3=4+12 does not involve carrying, so (i,j)=(1,3) counts. On the other hand, calculation of A_3+A_4=12+90 involves carrying, so (i,j)=(3,4) does not count.

Sample Input 2

20
313923 246114 271842 371982 284858 10674 532090 593483 185123 364245 665161 241644 604914 645577 410849 387586 732231 952593 249651 36908

Sample Output 2

6

Sample Input 3

5
1 1 1 1 1

Sample Output 3

10
E - Non-coprime DAG

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

N 頂点からなる有向グラフ G があり，頂点には 1 から N までの番号がついています．

二つの頂点 i,j (1 \leq i,j \leq N, i \neq j) の間には，以下の条件を両方満たす時，またその時のみ，辺 i \to j が存在します．

  • i<j
  • \mathrm{gcd}(i,j)>1

また，各頂点にはそれぞれ価値が定まっており，頂点 i の価値は A_i です．

以下の条件を満たすように頂点の集合 s を選ぶことを考えます．

  • s に含まれるどの二つの異なる頂点の組 (x,y) (x<y) についても，G 上で x から y には到達できない．

s に含まれる頂点の価値の総和としてあり得る最大値を求めてください．

制約

  • 1 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^9
  • 入力される値はすべて整数

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ．

入力例 1

6
1 1 1 1 1 1

出力例 1

4

s=\{1,2,3,5\} とすればよいです．

入力例 2

6
1 2 1 3 1 6

出力例 2

8

s=\{1,5,6\} とすればよいです．

入力例 3

20
40 39 31 54 27 31 80 3 62 66 15 72 21 38 74 49 15 24 44 3

出力例 3

343

Score : 800 points

Problem Statement

We have a directed graph G with N vertices numbered 1 to N.

Between two vertices i,j (1 \leq i,j \leq N, i \neq j), there is an edge i \to j if and only if both of the following conditions are satisfied.

  • i<j
  • \mathrm{gcd}(i,j)>1

Additionally, each vertex has an associated value: the value of Vertex i is A_i.

Consider choosing a set s of vertices so that the following condition is satisfied.

  • For every pair (x,y) (x<y) of different vertices in s, y is unreachable from x in G.

Find the maximum possible total value of vertices in s.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

6
1 1 1 1 1 1

Sample Output 1

4

We should choose s=\{1,2,3,5\}.

Sample Input 2

6
1 2 1 3 1 6

Sample Output 2

8

We should choose s=\{1,5,6\}.

Sample Input 3

20
40 39 31 54 27 31 80 3 62 66 15 72 21 38 74 49 15 24 44 3

Sample Output 3

343
F - Flip Cells

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

H 行 W 列からなる盤面があり，各マスには 0 か 1 が書き込まれています． 盤面の状態は H 個の文字列 S_1,S_2,\cdots,S_H で表され， S_i の j 文字目が，上から i 行目，左から j 列目のマスに書かれている数字を表します．

すぬけくんはこれから，次の操作を繰り返します．

  • 一つのマス目を一様ランダムに選ぶ． そして，そのマス目に書かれている値を flip する．（つまり，0 ならば 1 に変え，1 ならば 0 に変える）

ところで，すぬけ君は整数列 A=(A_1,A_2,\cdots,A_H) が大好きです． そのため，以下の条件が満たされた瞬間，操作を終了します．

  • すべての i (1 \leq i \leq H) について，i 行目にある 1 の個数がちょうど A_i である．

特に，操作を 0 回しか行わないこともありえます．

すぬけくんが行う操作回数の期待値を \text{mod }{998244353} で求めてください．

期待値 \text{mod }{998244353} の定義

求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not \equiv 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。

制約

  • 1 \leq H,W \leq 50
  • S_i は 0, 1 からなる長さ W の文字列
  • 0 \leq A_i \leq W

入力

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

H W
S_1
S_2
\vdots
S_H
A_1 A_2 \cdots A_H

出力

答えを出力せよ．

入力例 1

1 2
01
0

出力例 1

3

操作の様子は以下のようになります．

  • 確率 1/2 で 1 の書かれたマスを flip する．1 行目にある 1 の個数が 0 になり，操作が終了する．
  • 確率 1/2 で 0 の書かれたマスを flip する．1 行目にある 1 の個数は 2 になり，操作は継続する．
    • いずれかのマスを flip する．flip したマスに依らず，1 行目にある 1 の個数は 1 になり，操作は継続する．
      • 確率 1/2 で 1 の書かれたマスを flip する．1 行目にある 1 の個数が 0 になり，操作が終了する．
      • 確率 1/2 で 0 の書かれたマスを flip する．1 行目にある 1 の個数は 2 になり，操作は継続する．
      • \vdots

操作回数の期待値は 3 になります．

入力例 2

3 3
000
100
110
0 1 2

出力例 2

0

入力例 3

2 2
00
01
1 0

出力例 3

332748127

入力例 4

5 4
1101
0000
0010
0100
1111
1 3 3 2 1

出力例 4

647836743

Score : 1000 points

Problem Statement

We have a checkerboard with H rows and W columns, where each square has a 0 or 1 written on it. The current state of checkerboard is represented by H strings S_1,S_2,\cdots,S_H: the j-th character of S_i represents the digit in the square at the i-th row from the top and j-th column from the left.

Snuke will repeat the following operation.

  • Choose one square uniformly at random. Then, flip the value written in that square. (In other words, change 0 to 1 and vice versa.)

By the way, he loves an integer sequence A=(A_1,A_2,\cdots,A_H), so he will terminate the process at the moment when the following condition is satisfied.

  • For every i (1 \leq i \leq H), the i-th row from the top contains exactly A_i 1s.

Particularly, he may do zero operations.

Find the expected value of the number of operations Snuke does, modulo 998244353.

Definition of the expected value modulo 998244353

It can be proved that the sought expected value is always a rational number. Additionally, under the Constraints of this problem, when that value is represented as an irreducible fraction \frac{P}{Q}, it can also be proved that Q \not \equiv 0 \pmod{998244353}. Thus, there uniquely exists an integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Find this R.

Constraints

  • 1 \leq H,W \leq 50
  • S_i is a string of length W consisting of 0, 1.
  • 0 \leq A_i \leq W

Input

Input is given from Standard Input in the following format:

H W
S_1
S_2
\vdots
S_H
A_1 A_2 \cdots A_H

Output

Print the answer.

Sample Input 1

1 2
01
0

Sample Output 1

3

The process goes as follows.

  • With probability 1/2, a square with 1 is flipped. The 1-st row now contains zero 1s, terminating the process.
  • With probability 1/2, a square with 0 is flipped. The 1-st row now contains two 1s, continuing the process.
    • One of the squares is flipped. Regardless of which square is flipped, the 1-st row now contains one 1, continuing the process.
      • With probability 1/2, a square with 1 is flipped. The 1-st row now contains zero 1s, terminating the process.
      • With probability 1/2, a square with 0 is flipped. The 1-st row now contains two 1s, continuing the process.
      • \vdots

The expected value of the number of operations is 3.

Sample Input 2

3 3
000
100
110
0 1 2

Sample Output 2

0

Sample Input 3

2 2
00
01
1 0

Sample Output 3

332748127

Sample Input 4

5 4
1101
0000
0010
0100
1111
1 3 3 2 1

Sample Output 4

647836743