AtCoder Regular Contest 129

A - Smaller XOR

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

整数 N,L,R が与えられます．以下の条件を両方満たす整数 x の個数を数えてください．

L \leq x \leq R
(x \oplus N) < 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 である。

例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。

制約

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

入力

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

N L R

出力

答えを出力せよ．

入力例 1

2 1 2

出力例 1

x=1 の場合，L \leq x \leq R は満たしますが，(x \oplus N) < N は満たしません． x=2 の場合，両方の条件を満たします．他に条件を満たす x は存在しません．

入力例 2

10 2 19

出力例 2

入力例 3

1000000000000000000 1 1000000000000000000

出力例 3

847078495393153025

Score : 300 points

Problem Statement

Given are integers N, L, and R. Count the number of integers x that satisfy both of the following conditions.

L \leq x \leq R
(x \oplus N) < N (Here, \oplus denotes the bitwise \mathrm{XOR}.）

What is the bitwise \mathrm{XOR}?

The bitwise \mathrm{XOR} of 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.

For example, we have 3\oplus 5 = 6 (in base two: 011\oplus 101 = 110).

Constraints

1 \leq N \leq 10^{18}
1 \leq L \leq R \leq 10^{18}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N L R

Output

Print the answer.

Sample Input 1

2 1 2

Sample Output 1

For x=1, L \leq x \leq R is satisfied, but (x \oplus N) < N is not. For x=2, both conditions are satisfied. There is no other x that satisfies the conditions.

Sample Input 2

10 2 19

Sample Output 2

Sample Input 3

1000000000000000000 1 1000000000000000000

Sample Output 3

847078495393153025

B - Range Point Distance

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

整数 l,r,x (l \leq r) に対して，dist(l,r,x) を次のように定義します．

x<l のとき: dist(l,r,x)=l-x
l \leq x \leq r のとき: dist(l,r,x)=0
r<x のとき: dist(l,r,x)=x-r

整数のペアが N 個与えられ，そのうち i 個目のペアは (L_i,R_i) です． k=1,2,\cdots,N のそれぞれについて，次の問題を解いてください．

整数 x を自由に選び，\max(dist(L_1,R_1,x),dist(L_2,R_2,x),\cdots,dist(L_k,R_k,x)) を計算する．この値としてあり得る最小値を求めよ．

制約

1 \leq N \leq 2 \times 10^5
1 \leq L_i \leq R_i \leq 10^9
入力される値はすべて整数である

入力

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

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

各 k=1,2,\cdots,N に対する答えを順番に出力せよ．

入力例 1

出力例 1

0
0
1

k=1 のときは x=1 とすればよいです．
k=2 のときは x=3 とすればよいです．
k=3 のときは x=4 とすればよいです．

入力例 2

出力例 2

Score : 400 points

Problem Statement

For integers l, r, and x (l \leq r), let us define dist(l,r,x) as follows.

If x<l: dist(l,r,x)=l-x
If l \leq x \leq r: dist(l,r,x)=0
If r<x: dist(l,r,x)=x-r

You are given N pairs of integers, the i-th of which is (L_i,R_i). For each k=1,2,\cdots,N, solve the following problem.

Let us choose an integer x freely and compute \max(dist(L_1,R_1,x),dist(L_2,R_2,x),\cdots,dist(L_k,R_k,x)). Find the minimum possible value of this.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq L_i \leq R_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

Output

Print the answers for k=1,2,\cdots,N in this order.

Sample Input 1

Sample Output 1

0
0
1

For k=1, an optimal choice is x=1.
For k=2, an optimal choice is x=3.
For k=3, an optimal choice is x=4.

Sample Input 2

Sample Output 2

C - Multiple of 7

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数 N が与えられます．

1, 2, \cdots, 9 からなる文字列 s であって，以下の条件を満たすものを一つ求めてください．

s の長さ |s| は 10^6 以下．
次の条件を満たす整数の組 (l,r) (1 \leq l \leq r \leq |s|) の個数がちょうど N である．
- s の l 文字目から r 文字目までを取り出して数として見たとき，7 で割り切れる．

なお，この問題の制約より，解が必ず存在することが証明できます．

制約

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

入力

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

出力

条件を満たす s を出力せよ．解が複数存在する場合，どれを出力しても正解とみなされる．

入力例 1

出力例 1

(l,r)=(1,2),(2,3) の 2 つが条件を満たします．

入力例 2

出力例 2

(l,r)=(1,1),(2,2),(1,2) の 3 つが条件を満たします．

Score : 500 points

Problem Statement

Given is an integer N.

Find one string s consisting of 1, 2, \cdots, 9 that satisfies the conditions below.

The length of s, |s|, is at most 10^6.
There are exactly N pairs of integers (l,r) (1 \leq l \leq r \leq |s|) that satisfy the following condition.
- When the l-th through r-th characters of s are extracted and seen as a number, it is divisible by 7.

Under the Constraints of this problem, we can prove that a solution always exists.

Constraints

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

Input

Input is given from Standard Input in the following format:

Output

Print a string s that satisfies the conditions. If multiple solutions exist, printing any of them would be accepted.

Sample Input 1

Sample Output 1

Two pairs (l,r)=(1,2),(2,3) satisfy the conditions.

Sample Input 2

Sample Output 2

Three pairs (l,r)=(1,1),(2,2),(1,2) satisfy the conditions.

D - -1+2-1

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

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

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

整数 i (1 \leq i \leq N) を選び，A_{i-1},A_i,A_{i+1} にそれぞれ -1,2,-1 を足す．ただしここで，A_0 は A_N を指すものとし，また A_{N+1} は A_1 を指すものとする．

A のすべての要素を 0 にすることが可能かどうか判定し，また可能な場合は必要な最小の操作回数を求めてください．

制約

3 \leq N \leq 200000
-100 \leq A_i \leq 100
入力される値はすべて整数である

入力

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

N
A_1 A_2 \cdots A_N

出力

A のすべての要素を 0 にすることが不可能なら，-1 と出力せよ．可能ならば，必要な最小の操作回数を出力せよ．

入力例 1

4
3 0 -1 -2

出力例 1

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

i=2 を選んで操作する．A=(2,2,-2,-2) になる．
i=3 を選んで操作する．A=(2,1,0,-3) になる．
i=3 を選んで操作する．A=(2,0,2,-4) になる．
i=4 を選んで操作する．A=(1,0,1,-2) になる．
i=4 を選んで操作する．A=(0,0,0,0) になる．

入力例 2

3
1 0 -2

出力例 2

-1

入力例 3

4
1 -1 1 -1

出力例 3

-1

入力例 4

10
-28 -3 90 -90 77 49 -31 48 -28 -84

出力例 4

Score : 600 points

Problem Statement

Given is an integer sequence of length N: A=(A_1,A_2,\cdots,A_N).

You can repeat the operation below any number of times.

Choose an integer i (1 \leq i \leq N) and add -1, 2, -1 to A_{i-1},A_i,A_{i+1}, respectively. Here, A_0 stands for A_N, and A_{N+1} stands for A_1.

Determine whether it is possible to make every element of A 0. If it is possible, find the minimum number of operations needed.

Constraints

3 \leq N \leq 200000
-100 \leq A_i \leq 100
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

If it is impossible to make every element of A 0, print -1. If it is possible to do so, print the minimum number of operations needed.

Sample Input 1

4
3 0 -1 -2

Sample Output 1

We can achieve the objective in five operations, as follows.

Do the operation with i=2. Now we have A=(2,2,-2,-2).
Do the operation with i=3. Now we have A=(2,1,0,-3).
Do the operation with i=3. Now we have A=(2,0,2,-4).
Do the operation with i=4. Now we have A=(1,0,1,-2).
Do the operation with i=4. Now we have A=(0,0,0,0).

Sample Input 2

3
1 0 -2

Sample Output 2

-1

Sample Input 3

4
1 -1 1 -1

Sample Output 3

-1

Sample Input 4

10
-28 -3 90 -90 77 49 -31 48 -28 -84

Sample Output 4

E - Yet Another Minimization

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

すぬけくんは，長さ N の整数列 x=(x_1,x_2,\cdots,x_N) を作ろうとしています．各 i (1 \leq i \leq N) について，x_i の値の候補が M 種類あり，そのうち k 種類目の値は A_{i,k} です．なお，A_{i,k} を選ぶ場合には，C_{i,k} のコストがかかります．

また，x を決めたあと，各 i,j (1 \leq i < j \leq N) について， |x_i-x_j| \times W_{i,j} のコストが追加でかかります．

最終的なコストの総和としてありうる最小値を求めてください．

制約

2 \leq N \leq 50
2 \leq M \leq 5
1 \leq A_{i,1} < A_{i,2} < \cdots < A_{i,M} \leq 10^6
1 \leq C_{i,k} \leq 10^{15}
1 \leq W_{i,j} \leq 10^6
入力される値はすべて整数である

入力

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

N M
A_{1,1} C_{1,1}
A_{1,2} C_{1,2}
\vdots
A_{1,M} C_{1,M}
A_{2,1} C_{2,1}
A_{2,2} C_{2,2}
\vdots
A_{2,M} C_{2,M}
\vdots
A_{N,1} C_{N,1}
A_{N,2} C_{N,2}
\vdots
A_{N,M} C_{N,M}
W_{1,2} W_{1,3} \cdots W_{1,N-1} W_{1,N}
W_{2,3} W_{2,4} \cdots W_{2,N}
\vdots
W_{N-1,N}

出力

答えを出力せよ．

入力例 1

出力例 1

x=(5,9,7) とすればよいです．このときかかるコストの内訳は以下のとおりです．

x_1 として A_{1,2} を選んだので，C_{1,2}=2 のコストがかかる．
x_2 として A_{2,2} を選んだので，C_{2,2}=4 のコストがかかる．
x_3 として A_{3,1} を選んだので，C_{3,1}=2 のコストがかかる．
(i,j)=(1,2) について，|x_i-x_j| \times W_{i,j}=4 のコストがかかる．
(i,j)=(1,3) について，|x_i-x_j| \times W_{i,j}=10 のコストがかかる．
(i,j)=(2,3) について，|x_i-x_j| \times W_{i,j}=6 のコストがかかる．

入力例 2

10 3
19 2517
38 785
43 3611
3 681
20 758
45 4745
6 913
7 2212
22 536
4 685
27 148
36 2283
25 3304
36 1855
43 2747
11 1976
32 4973
43 3964
3 4242
16 4750
50 24
4 4231
22 1526
31 2152
15 2888
28 2249
49 2208
31 3127
40 3221
47 4671
24 6 16 47 42 50 35 43 47
29 18 28 24 27 25 33 12
5 43 20 9 39 46 30
40 24 34 5 30 21
50 6 21 36 5
50 16 13 13
2 40 15
25 48
20

出力例 2

入力例 3

出力例 3

Score : 900 points

Problem Statement

Snuke is making an integer sequence of length N: x=(x_1,x_2,\cdots,x_N). For each i (1 \leq i \leq N), there are M candidates for the value of x_i: the k-th of them is A_{i,k}. Choosing A_{i,k} incurs a cost of C_{i,k}.

Additionally, after deciding x, a cost of |x_i-x_j| \times W_{i,j} is incurred for each i,j (1 \leq i < j \leq N).

Find the minimum possible total cost incurred.

Constraints

2 \leq N \leq 50
2 \leq M \leq 5
1 \leq A_{i,1} < A_{i,2} < \cdots < A_{i,M} \leq 10^6
1 \leq C_{i,k} \leq 10^{15}
1 \leq W_{i,j} \leq 10^6
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_{1,1} C_{1,1}
A_{1,2} C_{1,2}
\vdots
A_{1,M} C_{1,M}
A_{2,1} C_{2,1}
A_{2,2} C_{2,2}
\vdots
A_{2,M} C_{2,M}
\vdots
A_{N,1} C_{N,1}
A_{N,2} C_{N,2}
\vdots
A_{N,M} C_{N,M}
W_{1,2} W_{1,3} \cdots W_{1,N-1} W_{1,N}
W_{2,3} W_{2,4} \cdots W_{2,N}
\vdots
W_{N-1,N}

Output

Print the answer.

Sample Input 1

Sample Output 1

An optimal choice is x=(5,9,7). The individual costs incurred here are as follows.

Choosing A_{1,2} for x_1 incurs a cost of C_{1,2}=2.
Choosing A_{2,2} for x_2 incurs a cost of C_{2,2}=4.
Choosing A_{3,1} for x_3 incurs a cost of C_{3,1}=2.．
For (i,j)=(1,2), a cost of |x_i-x_j| \times W_{i,j}=4 is incurred.
For (i,j)=(1,3), a cost of |x_i-x_j| \times W_{i,j}=10 is incurred.
For (i,j)=(2,3), a cost of |x_i-x_j| \times W_{i,j}=6 is incurred.

Sample Input 2

10 3
19 2517
38 785
43 3611
3 681
20 758
45 4745
6 913
7 2212
22 536
4 685
27 148
36 2283
25 3304
36 1855
43 2747
11 1976
32 4973
43 3964
3 4242
16 4750
50 24
4 4231
22 1526
31 2152
15 2888
28 2249
49 2208
31 3127
40 3221
47 4671
24 6 16 47 42 50 35 43 47
29 18 28 24 27 25 33 12
5 43 20 9 39 46 30
40 24 34 5 30 21
50 6 21 36 5
50 16 13 13
2 40 15
25 48
20

Sample Output 2

Sample Input 3

Sample Output 3

F - Let's Play Tag

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

数直線上に，すぬけくんと N+M 人の子供が立っています．

時刻 0 の彼らの位置は以下のようなものです．

すぬけくんは座標 0 にいる．
N 人の子供は座標が負の位置におり，このうち i 番目の子供は座標 -L_i にいる．
M 人の子供は座標が正の位置におり，このうち i 番目の子供は座標 R_i にいる．

今から彼らは鬼ごっこを開始します．具体的には，彼らは以下の行動をします．

すぬけくんは最初に，N 個の L と M 個の R からなる文字列 s を一つ選ぶ．その後，各 i=1,2,\cdots,N+M について以下の操作を行う．
- s の i 文字目が L なら，座標が負の方向へ速度 2 で移動を開始する．
- s の i 文字目が R なら，座標が正の方向へ速度 2 で移動を開始する．
- 子供を一人捕まえた（座標が一致した）時点で，次の i での操作に移る．なお，i=N+M の場合は鬼ごっこが終了となる．
すべての子供は，すぬけくんから遠ざかる方向へ常に速度 1 で移動し続ける．

すぬけくんが最初に選ぶことができる文字列 s 全てについて鬼ごっこが終了する時刻を求めたときの，それらの値の総和を 998244353 で割った余りを求めてください．

制約

3 \leq N,M \leq 250000
1 \leq L_1 < L_2 < \cdots < L_N < 998244353
1 \leq R_1 < R_2 < \cdots < R_M < 998244353
入力される値はすべて整数である

入力

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

N M
L_1 L_2 \cdots L_N
R_1 R_2 \cdots R_M

出力

答えを出力せよ．

入力例 1

3 3
1 2 3
1 2 3

出力例 1

例えば，s=LRRLLR の場合は，以下のようにゲームが進行します．

時刻 0: すぬけくんが負の方向へ移動を開始する．
時刻 1: すぬけくんが座標 -2 で子供を捕まえた後，正の方向へ移動を開始する．
時刻 5: すぬけくんが座標 6 で子供を捕まえた後，正の方向へ移動を開始する．
時刻 6: すぬけくんが座標 8 で子供を捕まえた後，負の方向へ移動を開始する．
時刻 22: すぬけくんが座標 -24 で子供を捕まえた後，負の方向へ移動を開始する．
時刻 23: すぬけくんが座標 -26 で子供を捕まえたあと，正の方向へ移動を開始する．
時刻 75: すぬけくんが座標 78 で子供を捕まえ，鬼ごっこが終了する．

入力例 2

7 5
89789743 196247866 205535557 542612813 782887985 889864096 899373580
539329402 618885430 714090971 717251433 860233092

出力例 2

937403116

Score : 1000 points

Problem Statement

Snuke and N+M children are standing on a number line.

At time 0, they are at the following positions.

Snuke is at coordinate 0.
N children are at negative coordinates. The i-th of them is at coordinate -L_i.
M children are at positive coordinates. The i-th of them is at coordinate R_i.

They will now play a game of tag. Specifically, they will do the following actions.

Snuke first chooses a string s consisting of N Ls and M Rs. Then, for each i=1,2,\cdots,N+M, he does the following.
- If the i-th character of s is L, start moving at a speed of 2 in the negative direction.
- If the i-th character of s is R, start moving at a speed of 2 in the positive direction.
- When having caught a child (by occupying the same coordinate), go to the next i, or end the game if i=N+M.
Every child keeps moving at a speed of 1 in the direction away from Snuke.

Assume that we have found the time when the game ends for every s that Snuke can choose in the beginning. Find the sum of all those values, modulo 998244353.

Constraints

3 \leq N,M \leq 250000
1 \leq L_1 < L_2 < \cdots < L_N < 998244353
1 \leq R_1 < R_2 < \cdots < R_M < 998244353
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 L_2 \cdots L_N
R_1 R_2 \cdots R_M

Output

Print the answer.

Sample Input 1

3 3
1 2 3
1 2 3

Sample Output 1

For example, if s=LRRLLR, the game goes as follows.

At time 0: Snuke starts moving in the negative direction.
At time 1: Snuke catches a child at coordinate -2 and starts moving in the positive direction.
At time 5: Snuke catches a child at coordinate 6 and starts moving in the positive direction.
At time 6: Snuke catches a child at coordinate 8 and starts moving in the negative direction.
At time 22: Snuke catches a child at coordinate -24 and starts moving in the negative direction.
At time 23: Snuke catches a child at coordinate -26 and starts moving in the positive direction.
At time 75: Snuke catches a child at coordinate 78 and ends the game.

Sample Input 2

7 5
89789743 196247866 205535557 542612813 782887985 889864096 899373580
539329402 618885430 714090971 717251433 860233092

Sample Output 2

937403116