AtCoder Daily Training HARD 2024/03/14 18:30start

E - Many Balls

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

空の箱があります。
髙橋君は以下の 2 種類の魔法を好きな順番で好きな回数使えます。

魔法 A ：箱の中にボールを 1 つ増やす
魔法 B ：箱の中のボールの数を 2 倍にする

合計 \mathbf{120} 回以内の魔法で、箱の中のボールの数をちょうど N 個にする方法を 1 つ教えてください。
なお、与えられた制約のもとで条件を満たす方法が必ず存在することが示せます。

魔法以外の方法でボールの数を変化させることはできません。

制約

1 \leq N \leq 10^{18}
入力は全て整数

入力

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

出力

A , B のみからなる文字列 S を出力せよ。
S の i 文字目が A ならば、髙橋君が i 回目に使う魔法が魔法 A であることを表し、B ならば魔法 B であることを表す。

S の長さは \mathbf{120} 以下でなければならない。

入力例 1

出力例 1

AABA

ボールの数は、0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5 と変化します。
AAAAA などの答えも正解になります。

入力例 2

出力例 2

BBABBAAAB

ボールの数は、0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14 と変化します。
S の長さを最小化する必要はありません。

Score : 300 points

Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

Spell A: puts one new ball into the box.
Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

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

Input

Input is given from Standard Input in the following format:

Output

Print a string S consisting of A and B. The i-th character of S should represent the spell for the i-th cast.

S must have at most \mathbf{120} characters.

Sample Input 1

Sample Output 1

AABA

This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.

F - Path Graph?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, 2, \dots, N の番号が、辺には 1, 2, \dots, M の番号が付けられています。
辺 i \, (i = 1, 2, \dots, M) は頂点 u_i, v_i を結んでいます。

このグラフがパスグラフであるか判定してください。

単純無向グラフとは

単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

パスグラフとは

頂点に 1, 2, \dots, N の番号が付けられたN 頂点のグラフがパスグラフであるとは、(1, 2, \dots, N) を並べ変えて得られる数列 (v_1, v_2, \dots, v_N) であって、以下の条件を満たすものが存在することをいいます。

全ての i = 1, 2, \dots, N-1 に対して、頂点 v_i, v_{i+1} を結ぶ辺が存在する
整数 i, j が 1 \leq i, j \leq N, |i - j| \geq 2 を満たすならば、頂点 v_i, v_j を結ぶ辺は存在しない

制約

2 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
入力される値は全て整数
入力で与えられるグラフは単純

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

与えられたグラフがパスグラフなら Yes、そうでないなら No と出力せよ。

入力例 1

出力例 1

Yes

与えらえたグラフは下図のようであり、これはパスグラフです。

example_00

入力例 2

2 0

出力例 2

No

与えらえたグラフは下図のようであり、これはパスグラフではありません。

example_01

入力例 3

出力例 3

No

与えらえたグラフは下図のようであり、これはパスグラフではありません。

example_02

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

What is a simple undirected graph?

A simple undirected graph is a graph without self-loops or multiple edges whose edges do not have a direction.

What is a path graph?

A graph with N vertices numbered 1, 2, \dots, N is said to be a path graph if and only if there is a sequence (v_1, v_2, \dots, v_N) that is a permutation of (1, 2, \dots, N) and satisfies the following conditions:

For all i = 1, 2, \dots, N-1, there is an edge connecting vertices v_i and v_{i+1}.
If integers i and j satisfies 1 \leq i, j \leq N and |i - j| \geq 2, then there is no edge that connects vertices v_i and v_j.

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
All values in the input are integers.
The graph given in the input is simple.

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 Yes if the given graph is a path graph; print No otherwise.

Sample Input 1

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

example_00

Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

example_01

Sample Input 3

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

example_02

G - Moves on Binary Tree

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

頂点数 2^{10^{100}}-1 の完全二分木があり、頂点には 1,2,...,2^{10^{100}}-1 の番号がついています。
頂点 1 が根であり、各 1\leq i < 2^{10^{100}-1} について、頂点 i は頂点 2i を左の子、頂点 2i+1 を右の子として持ちます。

高橋君は最初頂点 X におり、N 回移動を行います。移動は文字列 S により表され、i 回目の移動は次のように行います。

S の i 番目の文字が U のとき、今いる頂点の親に移動する
S の i 番目の文字が L のとき、今いる頂点の左の子に移動する
S の i 番目の文字が R のとき、今いる頂点の右の子に移動する

N 回の移動後に高橋君がいる頂点の番号を求めてください。なお、答えが 10^{18} 以下になるような入力のみが与えられます。

制約

1 \leq N \leq 10^6
1 \leq X \leq 10^{18}
N,X は整数
S は長さ N であり、U,L,R のみからなる
高橋君が根にいるとき、親に移動しようとすることはない
高橋君が葉にいるとき、子に移動しようとすることはない
高橋君が N 回の移動後にいる頂点の番号は 10^{18} 以下である

入力

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

N X
S

出力

答えを出力せよ。

入力例 1

3 2
URL

出力例 1

完全二分木は次のような構造をしています。

各移動により、高橋君がいる頂点の番号は 2 \to 1 \to 3 \to 6 と変化します。

入力例 2

4 500000000000000000
RRUU

出力例 2

500000000000000000

移動の途中過程において、高橋君がいる頂点の番号が 10^{18} を超えることもあります。

入力例 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

出力例 3

126419752371

Score : 400 points

Problem Statement

There is a perfect binary tree with 2^{10^{100}}-1 vertices, numbered 1,2,...,2^{10^{100}}-1.
Vertex 1 is the root. For each 1\leq i < 2^{10^{100}-1}, Vertex i has two children: Vertex 2i to the left and Vertex 2i+1 to the right.

Takahashi starts at Vertex X and performs N moves, represented by a string S. The i-th move is as follows.

If the i-th character of S is U, go to the parent of the vertex he is on now.
If the i-th character of S is L, go to the left child of the vertex he is on now.
If the i-th character of S is R, go to the right child of the vertex he is on now.

Find the index of the vertex Takahashi will be on after N moves. In the given cases, it is guaranteed that the answer is at most 10^{18}.

Constraints

1 \leq N \leq 10^6
1 \leq X \leq 10^{18}
N and X are integers.
S has a length of N and consists of U, L, and R.
When Takahashi is at the root, he never attempts to go to the parent.
When Takahashi is at a leaf, he never attempts to go to a child.
The index of the vertex Takahashi is on after N moves is at most 10^{18}.

Input

Input is given from Standard Input in the following format:

N X
S

Output

Print the answer.

Sample Input 1

3 2
URL

Sample Output 1

The perfect binary tree has the following structure.

In the three moves, Takahashi goes 2 \to 1 \to 3 \to 6.

Sample Input 2

4 500000000000000000
RRUU

Sample Output 2

500000000000000000

During the process, Takahashi may be at a vertex whose index exceeds 10^{18}.

Sample Input 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

Sample Output 3

126419752371

H - Geometric Progression

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

整数 A, X, M が与えられます。\displaystyle \sum_{i = 0}^{X-1} A^i を M で割った余りを求めてください。

制約

1 \leq A, M \leq 10^9
1 \leq X \leq 10^{12}
入力はすべて整数

入力

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

A X M

出力

答えを出力せよ。

入力例 1

3 4 7

出力例 1

3^0 + 3^1 + 3^2 + 3^3 = 40 です。40 を 7 で割った余りは 5 であるため、5 を出力します。

入力例 2

8 10 9

出力例 2

入力例 3

1000000000 1000000000000 998244353

出力例 3

919667211

Score : 500 points

Problem Statement

Given integers A, X, and M, find \displaystyle \sum_{i = 0}^{X-1} A^i, modulo M.

Constraints

1 \leq A, M \leq 10^9
1 \leq X \leq 10^{12}
All values in the input are integers.

Input

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

A X M

Output

Print the answer.

Sample Input 1

3 4 7

Sample Output 1

3^0 + 3^1 + 3^2 + 3^3 = 40, which equals 5 modulo 7, so 5 should be printed.

Sample Input 2

8 10 9

Sample Output 2

Sample Input 3

1000000000 1000000000000 998244353

Sample Output 3

919667211

I - Shift Table

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

高橋君と青木君は、これから N 日間アルバイトをします。
高橋君のシフト表は文字列 S により与えられ、S の i 文字目が # のとき i 日目に出勤、. のとき i 日目に欠勤します。
これをもとに、青木君は以下のようにシフト表を作りました。

まず、N でない N の正の約数 M をとる。
次に、1 日目から M 日目までの勤怠を決める。
最後に、i = 1, 2, \ldots, N - M の順に M + i 日目の勤怠が i 日目の勤怠と一致するように M + i 日目の勤怠を決める。

ここで、M の値が異なる場合でも最終的にできたシフトが同じものとなることがあることに注意してください。

N 日すべてについて高橋君と青木君の少なくとも一方が出勤することになったとき、青木君のシフト表として考えられるものの個数を 998244353 で割った余りを求めてください。

制約

N は 2 以上 10^5 以下の整数
S は長さ N の #、. からなる文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

6
##.#.#

出力例 1

高橋君は 1 \cdot 2 \cdot 4 \cdot 6 日目に出勤します。
青木君のシフト表を表す文字列を T とし、青木君は T の i 文字目が # のとき i 日目に出勤、. のとき i 日目に欠勤するとします。
T としてあり得るものは ###### \cdot #.#.#. \cdot .##.## の 3 つです。

1 つめのシフト表は M を 1 または 2 または 3、2 つめのシフト表は M = 2、3 つめのシフト表は M = 3 とすることにより実現できます。

入力例 2

7
...####

出力例 2

入力例 3

12
####.####.##

出力例 3

Score : 525 points

Problem Statement

Takahashi and Aoki will work part-time for the next N days.
Takahashi's shift schedule is given by the string S, where the i-th character of S is # if he works on the i-th day, and . if he is absent on the i-th day.
Based on this, Aoki created his shift schedule as follows.

First, take a positive divisor M of N that is not equal to N.
Next, decide the attendance for the first M days.
Finally, for i = 1, 2, \ldots, N - M in this order, decide the attendance for the (M + i)-th day so that it matches the attendance for the i-th day.

Note that different values of M may lead to the same final shift schedule.

Find the number of possible shift schedules for Aoki such that at least one of Takahashi and Aoki works on each of the N days, modulo 998244353.

Constraints

N is an integer between 2 and 10^5, inclusive.
S is a string of length N consisting of # and ..

Input

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

N
S

Output

Print the answer.

Sample Input 1

6
##.#.#

Sample Output 1

Takahashi works on days 1, 2, 4, and 6.
Let T be the string representing Aoki's shift schedule, where the i-th character of T is # if he works on the i-th day, and . if he is absent on the i-th day.
There are three possible strings for T: ######, #.#.#., and .##.##.

The first shift schedule can be realized by choosing M = 1 or 2 or 3, the second by choosing M = 2, and the third by choosing M = 3.

Sample Input 2

7
...####

Sample Output 2

Sample Input 3

12
####.####.##