AtCoder Daily Training HARD 2024/03/20 20:00start

E - Happy New Year!

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

10 進法で表記したときに 0,2 のみからなる正整数のうち、 K 番目に小さいものを求めてください。

制約

K は 1 以上 10^{18} 以下の整数

入力

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

出力

答えを整数として出力せよ。
ただし、たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要がある。たとえば、 2.34e+22 のような指数表記や、 0523 のような先頭に不要な 0 を付けたような表記は許されない。

入力例 1

出力例 1

10 進法で表記した時に 0,2 のみからなる正整数を小さい方から並べると、 2,20,22,\dots となります。
このうち K=3 番目である 22 を出力してください。

入力例 2

出力例 2

入力例 3

923423423420220108

出力例 3

220022020000202020002022022000002020002222002200002022002200

たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要があることに注意してください。

Score : 300 points

Problem Statement

Among the positive integers that consist of 0's and 2's when written in base 10, find the K-th smallest integer.

Constraints

K is an integer between 1 and 10^{18} (inclusive).

Input

Input is given from Standard Input in the following format:

Output

Print the answer as an integer.
Here, the exact value must be printed as an integer, even if it is big. Exponential notations such as 2.34e+22, for example, or unnecessary leading zeros such as 0523 are not allowed.

Sample Input 1

Sample Output 1

The positive integers that consist of 0's and 2's when written in base 10 are 2,20,22,\dots in ascending order.
The (K=) 3-rd of them, which is 22, should be printed.

Sample Input 2

Sample Output 2

Sample Input 3

923423423420220108

Sample Output 3

220022020000202020002022022000002020002222002200002022002200

Note that the exact value of the answer must be printed as an integer, even if it is big.

F - Make Takahashi Happy

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

H 行 W 列のマス目があります。 1 \leq i \leq H かつ 1 \leq j \leq W を満たす 2 つの整数 i, j について、上から i 行目、左から j 列目のマス（以下、(i, j) と表す）には、整数 A_{i, j} が書かれています。

いま、高橋君は (1, 1) にいます。これから高橋君は「いまいるマスから右または下に隣接するマスに移動する」ことを繰り返して、(H, W) まで移動します。ただし、その過程でマス目の外部に移動することは出来ません。

その結果、高橋君が通ったマス（始点 (1, 1) と終点 (H, W) を含む）に書かれた整数がすべて異なるとき、高橋君は嬉しくなります。高橋君の移動経路として考えられるもののうち、高橋君が嬉しくなるものの個数を出力してください。

制約

2 \leq H, W \leq 10
1 \leq A_{i, j} \leq 10^9
入力はすべて整数

入力

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

H W
A_{1, 1} A_{1, 2} \ldots A_{1, W}
A_{2, 1} A_{2, 2} \ldots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \ldots A_{H, W}

出力

答えを出力せよ。

入力例 1

出力例 1

高橋君の移動経路として考えられるものは下記の 6 通りです。

(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 2, 3, 4 であり、高橋君は嬉しくなりません。
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 3, 4 であり、高橋君は嬉しくなりません。
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 3, 4 であり、高橋君は嬉しくなりません。
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。

よって、高橋君が嬉しくなる移動経路は、上で 3, 5, 6 番目に述べた 3 個です。

入力例 2

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

出力例 2

この例では、高橋君は考えられるどの経路を通っても嬉しくなります。

Score : 300 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns. For two integers i and j such that 1 \leq i \leq H and 1 \leq j \leq W, the square at the i-th row from the top and j-th column from the left (which we denote by (i, j)) has an integer A_{i, j} written on it.

Takahashi is currently at (1,1). From now on, he repeats moving to an adjacent square to the right of or below his current square until he reaches (H, W). When he makes a move, he is not allowed to go outside the grid.

Takahashi will be happy if the integers written on the squares he visits (including initial (1, 1) and final (H, W)) are distinct. Find the number of his possible paths that make him happy.

Constraints

2 \leq H, W \leq 10
1 \leq A_{i, j} \leq 10^9
All values in the input are integers.

Input

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

H W
A_{1, 1} A_{1, 2} \ldots A_{1, W}
A_{2, 1} A_{2, 2} \ldots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \ldots A_{H, W}

Output

Print the answer.

Sample Input 1

Sample Output 1

There are six possible paths:

(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 2, 3, 4, so he will not be happy.
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.

Thus, the third, fifth, and sixth paths described above make him happy.

Sample Input 2

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

Sample Output 2

In this example, every possible path makes him happy.

G - Make Bipartite 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

N 個の頂点と M 本の辺からなる単純な（すなわち、自己ループも多重辺も含まない）無向グラフ G が与えられます。 i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結びます。

1 \leq u \lt v \leq N を満たす整数の組 (u, v) であって、下記の 2 つの条件をともに満たすものの個数を出力してください。

グラフ G において、頂点 u と頂点 v を結ぶ辺は存在しない。
グラフ G に、頂点 u と頂点 v を結ぶ辺を追加して得られるグラフは、二部グラフである。

二部グラフとは？

無向グラフが二部グラフであるとは、下記の条件を満たすように各頂点を黒または白のどちらかの色で塗ることができることを言います。

同じ色に塗られた頂点どうしを結ぶ辺は存在しない。

制約

2 \leq N \leq 2 \times 10^5
0 \leq M \leq \min \lbrace 2 \times 10^5, N(N-1)/2 \rbrace
1 \leq u_i, v_i \leq N
グラフ G は単純
入力はすべて整数

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

答えを出力せよ。

入力例 1

出力例 1

問題文中の条件を満たす整数の組 (u, v) は、(1, 4) と (1, 5) の 2 つです。よって、2 を出力します。
他の組については、例えば、(1, 3) はグラフ G において頂点 1 と頂点 3 を結ぶ辺が存在することから、 (4, 5) はグラフ G に頂点 4 と頂点 5 を結ぶ辺を追加して得られるグラフが二部グラフではないことから、それぞれ問題文中の条件を満たしません。

入力例 2

出力例 2

与えられるグラフが二部グラフであったり連結であるとは限らないことに注意してください。

入力例 3

出力例 3

Score : 400 points

Problem Statement

You are given a simple undirected graph G with N vertices and M edges (a simple graph does not contain self-loops or multi-edges). For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i.

Print the number of pairs of integers (u, v) that satisfy 1 \leq u \lt v \leq N and both of the following conditions.

The graph G does not have an edge connecting vertex u and vertex v.
Adding an edge connecting vertex u and vertex v in the graph G results in a bipartite graph.

What is a bipartite graph?

An undirected graph is said to be bipartite if and only if one can paint each vertex black or white to satisfy the following condition.

No edge connects vertices painted in the same color.

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq M \leq \min \lbrace 2 \times 10^5, N(N-1)/2 \rbrace
1 \leq u_i, v_i \leq N
The graph G is simple.
All values in the input are integers.

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print the answer.

Sample Input 1

Sample Output 1

We have two pairs of integers (u, v) that satisfy the conditions in the problem statement: (1, 4) and (1, 5). Thus, you should print 2.
The other pairs do not satisfy the conditions. For instance, for (1, 3), the graph G has an edge connecting vertex 1 and vertex 3; for (4, 5), adding an edge connecting vertex 4 and vertex 5 in the graph G does not result in a bipartite graph.

Sample Input 2

Sample Output 2

Note that the given graph may not be bipartite or connected.

Sample Input 3

Sample Output 3

H - Range Sums

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

高橋くんは秘密の整数列 a を持っており、現時点で、a の長さが N であることは分かっています。

a の中身を当てたいあなたに対し、高橋くんは以下の Q 個の情報を追加で与えてくれることを約束しました。

i\ (1 \leq i \leq Q) 個目の情報: a_{l_i}+a_{l_i+1}+\cdots+a_{r_i} の値

高橋くんが約束を守り、Q 個の情報すべてが与えられた場合、a に含まれる全要素の総和 a_1+a_2+\cdots+a_N を特定することは可能ですか？

制約

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq \min(2 \times 10^5,\frac{N(N+1)}{2})
1 \leq l_i \leq r_i \leq N
(l_i,r_i) \neq (l_j,r_j)\ (i \neq j)
入力はすべて整数

入力

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

N Q
l_1 r_1
l_2 r_2
\hspace{0.4cm}\vdots
l_Q r_Q

出力

a に含まれる全要素の総和を特定することが可能なら Yes を、そうでないなら No を出力せよ。

入力例 1

出力例 1

Yes

1 個目の情報と 2 個目の情報から、a_1+a_2+a_2+a_3 の値が分かります。そこから 3 個目の情報によって得られる a_2 の値を引くと、a_1+a_2+a_3 の値を特定可能です。

入力例 2

出力例 2

No

a の先頭 3 項の総和を特定することは可能ですが、全要素の総和を特定することは不可能です。

入力例 3

出力例 3

Yes

4 個目の情報によって全要素の総和が直接与えられています。

Score : 500 points

Problem Statement

Takahashi has a secret integer sequence a. You know that the length of a is N.

You want to guess the contents of a. He has promised to give you the following Q additional pieces of information.

The i-th information: the value a_{l_i}+a_{l_i+1}+\cdots+a_{r_i}.

Is it possible to determine the sum of all elements in a, a_1+a_2+\cdots+a_N, if the Q pieces of promised information are given?

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq \min(2 \times 10^5,\frac{N(N+1)}{2})
1 \leq l_i \leq r_i \leq N
(l_i,r_i) \neq (l_j,r_j)\ (i \neq j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
l_1 r_1
l_2 r_2
\hspace{0.4cm}\vdots
l_Q r_Q

Output

If it is possible to determine the sum of all elements in a, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

From the first and second information, we can find the value a_1+a_2+a_2+a_3. By subtracting the value of a_2 from it, we can determine the value a_1+a_2+a_3.

Sample Input 2

Sample Output 2

No

We can determine the sum of the first 3 elements of a, but not the sum of all elements.

Sample Input 3

Sample Output 3

Yes

The fourth information directly gives us the sum of all elements.

I - substr = S

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

T 個のテストケースについて、数字のみからなる文字列 S と正整数 L,R が与えられるので、以下の問題を解いてください。

正整数 x に対して f(x)= ( x を ( 先頭に 0 を含まないように ) 書き下した文字列の連続部分列のうち S と合致するものの個数 ) と定義します。

例えば S= 22 であるとき、f(122) = 1, f(123) = 0, f(226) = 1, f(222) = 2 となります。

このとき、 \displaystyle \sum_{k=L}^{R} f(k) を求めてください。

制約

1 \le T \le 1000
S は数字のみからなる長さ 1 以上 16 以下の文字列
L,R は 1 \le L \le R < 10^{16} を満たす整数

入力

入力は以下の形式で標準入力から与えられる。\rm{case}_i は i 個目のテストケースを表す。

T
\rm{case}_{1}
\rm{case}_{2}
\vdots
\rm{case}_{\it{T}}

各テストケースは以下の形式である。

S L R

出力

全体で T 行出力せよ。
そのうち i 行目には i 番目のテストケースに対する答えを整数として出力せよ。

入力例 1

6
22 23 234
0295 295 295
0 1 9999999999999999
2718 998244353 9982443530000000
869120 1234567890123456 2345678901234567
2023032520230325 1 9999999999999999

出力例 1

12
0
14888888888888889
12982260572545
10987664021
1

この入力には 6 個のテストケースが含まれます。

1 つ目のケースは S= 22 ,L=23,R=234 です。
- f(122)=f(220)=f(221)=f(223)=f(224)=\dots=f(229)=1
- f(222)=2
- 以上より、このケースに対する答えは 12 です。
2 つ目のケースは S= 0295 ,L=295,R=295 です。
- f(295)=0 となることに注意してください。

Score : 500 points

Problem Statement

You are given a string S consisting of digits and positive integers L and R for each of T test cases. Solve the following problem.

For a positive integer x, let us define f(x) as the number of contiguous substrings of the decimal representation of x (without leading zeros) that equal S.

For instance, if S= 22, we have f(122) = 1, f(123) = 0, f(226) = 1, and f(222) = 2.

Find \displaystyle \sum_{k=L}^{R} f(k).

Constraints

1 \le T \le 1000
S is a string consisting of digits whose length is between 1 and 16, inclusive.
L and R are integers satisfying 1 \le L \le R < 10^{16}.

Input

The input is given from Standard Input in the following format, where \rm{case}_i denotes the i-th test case:

T
\rm{case}_{1}
\rm{case}_{2}
\vdots
\rm{case}_{\it{T}}

Each test case is in the following format:

S L R

Output

Print T lines in total.
The i-th line should contain an integer representing the answer to the i-th test case.

Sample Input 1

6
22 23 234
0295 295 295
0 1 9999999999999999
2718 998244353 9982443530000000
869120 1234567890123456 2345678901234567
2023032520230325 1 9999999999999999

Sample Output 1

12
0
14888888888888889
12982260572545
10987664021
1

This input contains six test cases.

In the first test case, S= 22, L=23, R=234.
- f(122)=f(220)=f(221)=f(223)=f(224)=\dots=f(229)=1.
- f(222)=2.
- Thus, the answer is 12.
In the second test case, S= 0295, L=295, R=295.
- Note that f(295)=0.