C - Stones

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 個の石が一列に並んでおり、すべての石は白か黒で塗られています。 石の状態は長さ N の文字列 S で表され、S の i 文字目が . のとき左から i 個目の石が白であり、# のとき左から i 個目の石が黒であることを表します。

高橋君は、0 個以上の石の色を黒または白に変更し、黒い石のすぐ右に白い石があるような箇所がないようにしたいです。 色を変更する必要のある石の個数の最小値を求めてください。

制約

  • 1 \leq N \leq 2\times 10^5
  • S は ., # のみからなる長さ N の文字列である

入力

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

N
S

出力

色を変更する必要のある石の個数の最小値を出力せよ。

入力例 1

3
#.#

出力例 1

1

例えば、1 個目の石の色を白に変更すればよいです。

入力例 2

5
#.##.

出力例 2

2

入力例 3

9
.........

出力例 3

0

Score : 300 points

Problem Statement

There are N stones arranged in a row. Every stone is painted white or black. A string S represents the color of the stones. The i-th stone from the left is white if the i-th character of S is ., and the stone is black if the character is #.

Takahashi wants to change the colors of some stones to black or white so that there will be no white stone immediately to the right of a black stone. Find the minimum number of stones that needs to be recolored.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • S is a string of length N consisting of . and #.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the minimum number of stones that needs to be recolored.

Sample Input 1

3
#.#

Sample Output 1

1

It is enough to change the color of the first stone to white.

Sample Input 2

5
#.##.

Sample Output 2

2

Sample Input 3

9
.........

Sample Output 3

0
D - Three Colors

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 個の整数が与えられます。i 個目の整数は a_i です。 与えられたすべての整数を赤、緑、青の 3 色のいずれかで塗り、以下の条件を満たすようにする方法の個数を 998244353 で割ったあまりを求めてください。

  • 赤、緑、青で塗られた整数の総和をそれぞれ R,G,B とする。三辺の長さがそれぞれ R,G,B であるような正の面積の三角形が存在する。

制約

  • 3 \leq N \leq 300
  • 1 \leq a_i \leq 300(1\leq i\leq N)
  • 入力はすべて整数である

入力

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

N
a_1
:
a_N

出力

与えられたすべての整数を赤、緑、青の 3 色のいずれかで塗り、条件を満たすようにする方法の個数を 998244353 で割ったあまりを出力せよ。

入力例 1

4
1
1
1
2

出力例 1

18

三角形の三辺の長さがそれぞれ 1,2,2 となるように整数を塗り分けるしかなく、そのような塗り分け方は 18 通り存在します。

入力例 2

6
1
3
2
3
5
2

出力例 2

150

入力例 3

20
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9
3
2
3
8
4

出力例 3

563038556

Score : 600 points

Problem Statement

You are given N integers. The i-th integer is a_i. Find the number, modulo 998244353, of ways to paint each of the integers red, green or blue so that the following condition is satisfied:

  • Let R, G and B be the sums of the integers painted red, green and blue, respectively. There exists a triangle with positive area whose sides have lengths R, G and B.

Constraints

  • 3 \leq N \leq 300
  • 1 \leq a_i \leq 300(1\leq i\leq N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1
:
a_N

Output

Print the number, modulo 998244353, of ways to paint each of the integers red, green or blue so that the condition is satisfied.

Sample Input 1

4
1
1
1
2

Sample Output 1

18

We can only paint the integers so that the lengths of the sides of the triangle will be 1, 2 and 2, and there are 18 such ways.

Sample Input 2

6
1
3
2
3
5
2

Sample Output 2

150

Sample Input 3

20
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9
3
2
3
8
4

Sample Output 3

563038556
E - Polynomial Divisors

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

N 次の整数係数多項式 f(x)=a_Nx^N+a_{N-1}x^{N-1}+...+a_0 が与えられます。任意の整数 x に対して p が f(x) を割り切るような素数 p をすべて求めてください。

制約

  • 0 \leq N \leq 10^4
  • |a_i| \leq 10^9(0\leq i\leq N)
  • a_N \neq 0
  • 入力はすべて整数である

入力

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

N
a_N
:
a_0

出力

任意の整数 x に対して p が f(x) を割り切るような素数 p を小さい順にすべて出力せよ。

入力例 1

2
7
-7
14

出力例 1

2
7

2,7 は例えば、f(1)=14 や f(2)=28 を割り切ります。

入力例 2

3
1
4
1
5

出力例 2




条件を満たす素数がない場合もあります。














入力例 3
0
998244353













出力例 3
998244353







Score : 800 points







Problem Statement
You are given a polynomial of degree N with integer coefficients: f(x)=a_Nx^N+a_{N-1}x^{N-1}+...+a_0. Find all prime numbers p that divide f(x) for every integer x.











Constraints
    

  • 0 \leq N \leq 10^4
    • 

  • |a_i| \leq 10^9(0\leq i\leq N)
    • 

  • a_N \neq 0
    • 

  • All values in input are integers.
    • 

















Input
Input is given from Standard Input in the following format:


N
a_N
:
a_0













Output
Print all prime numbers p that divide f(x) for every integer x, in ascending order.
















Sample Input 1
2
7
-7
14













Sample Output 1
2
7




2 and 7 divide, for example, f(1)=14 and f(2)=28.














Sample Input 2
3
1
4
1
5













Sample Output 2



There may be no integers that satisfy the condition.














Sample Input 3
0
998244353













Sample Output 3
998244353







			


			
		

	
		

		

			F - Banned X
			

			
Time Limit: 2 sec / Memory Limit: 1024 MB


			

				


配点 : 800 点







問題文
0,1,2 のみからなる長さ N の数列であって、
どの連続する部分列に対してもそれに含まれる数の総和がちょうど X にはならないようなものの個数を 998244353 で割ったあまりを求めてください。











制約
    

  • 1 \leq N \leq 3000
    • 

  • 1 \leq X \leq 2N
    • 

  • N,X は整数である
    • 

















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


N X













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
















入力例 1
3 3













出力例 1
14




(0,0,0),(0,0,1),(0,0,2),(0,1,0),(0,1,1),(0,2,0),(0,2,2),(1,0,0),(1,0,1),(1,1,0),(2,0,0),(2,0,2),(2,2,0),(2,2,2) の 14 個の数列が条件を満たします。














入力例 2
8 6













出力例 2
1179
















入力例 3
10 1













出力例 3
1024
















入力例 4
9 13













出力例 4
18402
















入力例 5
314 159













出力例 5
459765451







Score : 800 points







Problem Statement
Find the number, modulo 998244353, of sequences of length N consisting of 0, 1 and 2 such that none of their contiguous subsequences totals to X.











Constraints
    

  • 1 \leq N \leq 3000
    • 

  • 1 \leq X \leq 2N
    • 

  • N and X are integers.
    • 

















Input
Input is given from Standard Input in the following format:


N X













Output
Print the number, modulo 998244353, of sequences that satisfy the condition.
















Sample Input 1
3 3













Sample Output 1
14




14 sequences satisfy the condition: (0,0,0),(0,0,1),(0,0,2),(0,1,0),(0,1,1),(0,2,0),(0,2,2),(1,0,0),(1,0,1),(1,1,0),(2,0,0),(2,0,2),(2,2,0) and (2,2,2).














Sample Input 2
8 6













Sample Output 2
1179
















Sample Input 3
10 1













Sample Output 3
1024
















Sample Input 4
9 13













Sample Output 4
18402
















Sample Input 5
314 159













Sample Output 5
459765451