問題文

整数 N が与えられます。2023 年パ研合宿 SpeedRun で N 位を取った人の AtCoder ユーザー名を出力してください。

この問題の制約において、チーム戦順位表、個人戦順位表のどちらを参照しても解答には影響しません。

制約

• 1 \leq N \leq 3
• 入力は全て整数

入力例 1

1

出力例 1

maspy

1 位を取ったのは maspy さんです。

入力例 2

2

出力例 2

square1001

2 位を取ったのは square1001 さんです。

問題文

パソコン力を高めるの国は N 個の都市とそれらを結ぶ N - 1 本の双方向の道路からなる。i 本目の道路は都市 A_i, B_i を結ぶ。道路以外を使って都市間を移動することはできず、またどの国からどの国へもいくつかの道路を通ることで移動することができる。つまり、この国はグラフとして木構造をなす。

巡回セールスマンの Mr.X は都市間をセールスに回る。セールスは二日間からなる。彼ははじめ都市 1 にいて、一日目には都市 X_1, X_2, \cdots ,X_M を訪れる。その後どこかの都市に泊まり、二日目には都市 Y_1, Y_2, \cdots ,Y_M を訪れ、最後に都市 S に到着してセールスを終える必要がある。ここで、各日に訪れる都市の順番は問わない。また、ある日のはじめにいた都市についても、その日に訪れたとみなす。

Mr.X はセールスをできるだけ少ない回数道路を通って終えたい。2 日間に道路を通る回数の最小値を求めよ。

制約

• 2 \leq N \leq 10^5
• 1 \leq M \leq N
• 1 \leq S \leq N
• 1 \leq A_i, B_i \leq N \ (1 \leq i \leq N - 1)
• 与えられるグラフは木である。
• 1 \leq X_i, Y_i \leq N
• 入力は全て整数である。

配点

以下の小課題に点数が定められている。

1. (200 点) N \leq 1000
2. (300 点) 追加の制約はない。

入力例 1

5 3 4
1 2
1 3
1 4
1 5
1 2 3
2 3 4

出力例 1

7

例えば、一日目には都市 1, 2, 1, 3 の順に訪れて、二日目は都市 3, 1, 2, 1, 4 の順に訪れると、合計で 7 回道路を通る。これは最善の方法の一つである。

入力例 2

7 4 1
1 2
1 3
2 4
2 5
3 6
3 7
4 5 6 7
4 5 6 7

出力例 2

20

問題文

N 要素の整数列 A = (A_0, A_1, \cdots, A_{N - 1}) が存在する。ここで、ある 2 つの非負整数 k, l があって A_i = ki + l を満たす。

いたずら好きの Mr.X は A のうち \displaystyle \lfloor \frac{N - 1}{2} \rfloor 要素を取り除いて、取り除いた要素の個数だけ好きな値を追加し、その後自由に並び替えた。Mr.X が変更した後の数列 A が与えられる。k, l を求めよ。

k, l にいくつかの候補が存在する場合があるが、その場合はどれを出力しても正解とみなされる。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^{18}
• 入力は全て整数

配点

以下の小課題に点数が定められている。

1. (200 点) N \leq 100
2. (300 点) 追加の制約はない。

入力例 1

5
2 7 6 1 9

出力例 1

2 1

(k, l) = (2, 1) とすると、もともとの A は (1, 3, 5, 7, 9) となる。

(k, l) = (1, 6) なども正解と判定される。

入力例 2

5
1 3 1 3 1

出力例 2

0 1

問題文

Mr.X はゲームをしており、これから M 個のダンジョンを攻略する。

各ダンジョンは N 階層からなる。ダンジョン i の j \ (1 \leq j \leq N) 階層には強さ A_{i,j} のモンスターがいる。Mr.X はダンジョン x \ (1 \leq x \leq M) を以下のように攻略する。

1. ダンジョン x に入るときの初期体力 h_x を定める。ここで \displaystyle h_x > \max_{i=1}^{N} A_{x, i} を満たす必要がある。
2. ダンジョン x の階層 1 に入る。
3. i = 1, 2, \cdots ,N について順に、以下のように階層 i を攻略する。今の体力を u とする。
   1. u \leq A_{x, i} の場合、復活アイテムを 1 回用いて u を h_x にする。
   2. u を u - A_{x, i} で置き換えて階層 i + 1 に進む。ただし i = N のとき攻略を終了する。

Mr.X のアカウントのレベルは L なので、初期体力を決めるとき \displaystyle \sum_{i=1}^{M} h_i \leq L を満たす必要がある。また、 M 個のダンジョンそれぞれで使う復活アイテムの個数を考えたとき、その最大値をできるだけ小さくしたい。条件を満たすように初期体力を決める時、各ダンジョンで使う復活アイテムの個数の最大値の最小値を求めよ。

制約

• 1 \leq N \leq 3 \times 10^4
• 1 \leq M \leq 10^2
• 1 \leq A_{i, j} \leq 10^9
• \displaystyle \sum_{i=1}^{M} (\max_{j=1}^{N} A_{i, j} + 1) \leq L \leq 10^{18}
• 入力は全て整数

配点

以下の小課題に点数が定められている。

1. (200 点) N \leq 3 \times 10^3
2. (500 点) 追加の制約はない。

入力例 1

3 3 24
5 2 3
9 3 7
3 7 1

出力例 1

2

h = (6, 10, 8) とすると、ダンジョン 1 には復活アイテムが 1 つ、残りのダンジョンには復活アイテムが 2 つ必要であり、これが最適である。

入力例 2

5 10 132
6 9 11 9 6 10 5 5 4 11
20 20 5 14 17 9 15 14 20 8
18 17 1 20 8 5 1 8 2 9
5 6 1 2 2 6 1 2 2 1
12 4 13 2 5 15 20 4 4 12

出力例 2

3

問題文

N 枚のカードがあり、順番に 1, 2, \cdots ,N 番目のカードと呼ぶ。全てのカードは表と裏にそれぞれ 0 と 1 が書かれている。

これらのカードを M 個の条件を全て満たすように、表と裏のどちらかを上にして机に置く。i 番目の条件は以下の少なくとも一方を満たすことである。

• A_i 番目のカードの上面に X_i が書かれている。
• B_i 番目のカードの上面に Y_i が書かれている。

条件を満たすようなカードの置き方が存在するような入力しか与えられないことが保証される。ただし、カードの置き方は複数あるかもしれない。以下の条件を満たす整数組 (p, q, r, s) の個数を求めよ。

• 1 \leq p, q \leq N
• \{r, s\} \subset \{0, 1\}
• 全てのカードの置き方について、以下の少なくとも一方を満たす。
  • p 番目のカードの上面に r が書かれている。
  • q 番目のカードの上面に s が書かれている。

制約

• 1 \leq N \leq 3 \times 10^4
• 0 \leq M \leq 3 \times 10^4
• 1 \leq A_i, B_i \leq N
• \{ X_i, Y_i \} \subset \{0, 1\}
• 条件を満たすようなカードの置き方が最低 1 通り存在する。
• 入力は全て整数

入力例 1

2 1
1 2 0 0

出力例 1

6

1 番目のカードと 2 番目のカードのいずれかの上面に 0 が書かれている必要があります。これを満たすように置くと、カードの表面に書かれた文字としてあり得るのは (0, 0), (1, 0), (0, 1) の 3 通りです。よって、 (p, q, r, s) としてあり得るのは、 (1, 1, 0, 1), (1, 1, 1, 0), (1, 2, 0, 0), (2, 1, 0, 0), (2, 2, 0, 1), (2, 2, 1, 0) です。

入力例 2

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

出力例 2

241

問題文

N 頂点からなる完全 DAG がある。つまり、このグラフの任意の頂点組 i, j \ (1 \leq i < j \leq N) には頂点 i から頂点 j への辺があり、また辺はそれらのみである。

M 個のクエリが順番に与えられるので答えよ。i 番目のクエリは以下の通りである。

• 頂点 X_i から Y_i への辺を削除する。その後、頂点 1 から頂点 Z_i への最短距離を求める。

制約

• 1 \leq N, M \leq 3 \times 10^5
• \displaystyle M \leq \frac{N(N - 1)}{2}
• 1 \leq X_i < Y_i \leq N
• 1 \leq Z_i \leq N
• (X_i, Y_i) \neq (X_j, Y_j) \ (i \neq j)
• 入力は全て整数

配点

以下の小課題に点数が定められている。

1. (200 点) N \leq 1000
2. 追加の制約はない。

入力例 1

4 6
1 2 3
3 4 4
2 4 3
1 3 4
1 4 3
2 3 4

出力例 1

1
1
1
1
-1
-1

4 番目までのクエリでは、頂点 1 から頂点 Z_i への辺が残っているので答えは 1 である。それ以外のクエリでは頂点 Z_i に到達できないので、 -1 を出力する。

入力例 2

6 10
3 5 4
2 4 2
1 3 3
3 6 6
1 4 1
1 6 1
1 5 6
4 6 6
3 4 1
4 5 6

出力例 2

1
1
2
1
0
0
2
2
0
2

問題文

正整数 N と長さ N の非負整数列 A が与えられる。以下の操作をちょうど K 回繰り返すことを考える。

• A から正の要素をひとつ選ぶ。選んだ要素を x として、これを 0 \leq y < x を満たす整数 y に置き換える。

K 回の操作の後の A としてあり得るものの数を 998244353 で割った余りを求めよ。

制約

• 1 \leq N \leq 10^5
• 1 \leq K \leq 10^5
• 0 \leq A_i \leq 10^9
• 入力は全て整数

配点

以下の小課題に点数が定められている。

1. (200 点) N, K \leq 100
2. (400 点) N, K \leq 1000
3. (200 点) 追加の制約はない。

入力例 1

3 2
1 2 3

出力例 1

14

K 回の操作後の A としてあり得るものを以下に列挙する : (1, 2, 1), (1, 2, 0), (1, 1, 2), (1, 1, 1), (1, 1, 0), (1, 0, 3), (1, 0, 2), (1, 0, 1), (1, 0, 0), (0, 2, 2), (0, 2, 1), (0, 2, 0), (0, 1, 3), (0, 0, 3) の 14 通り。

入力例 2

5 3
1 2 3 4 5

出力例 2

306

問題文

パソコン力を高めるの国は N 個の都市とそれらを結ぶ N - 1 本の双方向の道路からなる。道路 i は都市 A_i, B_i を結ぶ。道路以外を使って都市間を移動することはできず、またどの国からどの国へもいくつかの道路を通ることで移動することができる。つまり、この国はグラフとして木構造をなす。

パ研国も N 個の都市からなる。この国の都市 a, b \ (a \neq b) の間には、以下の条件を満たすとき、またそのときに限って道路が存在する。

• パソコン力を高めるの国の都市 a, b 間を K 本未満の道路を通って行き来できない。

以下の Q 個の質問に答えよ。i 番目の質問は以下である。

• パ研国の都市 X_i, Y_i の間を道路のみを用いて行き来できるか？もしできるならば、最低何本の道路を通る必要があるか？

制約

• 2 \leq K + 1 \leq N \leq 10^5
• 1 \leq A_i, B_i \leq N \ (1 \leq i \leq N - 1)
• 与えられるグラフは木である。
• 1 \leq Q \leq 10^5
• 1 \leq X_i, Y_i \leq N, X_i \neq Y_i \ (1 \leq i \leq N - 1)
• 入力は全て整数

配点

以下の小課題に点数が定められている。

1. (300 点) N, Q \leq 1000
2. (500 点) 追加の制約はない。

入力例 1

4 2 2
1 2
2 3
3 4
1 4
2 3

出力例 1

1
3

パソコン力を高めるの国における都市 1, 4 の距離は 3 なので、パ研国における都市 1, 4 の距離は 1 である。よって、クエリ 1 では 1 を出力すれば良い。

クエリ 2 については、都市 2, 4, 1, 3 の順に進むことで移動できる。これが最善なので、 3 を出力する。

入力例 2

7 3 3
1 2
1 3
2 4
2 5
3 6
3 7
3 4
2 3
6 7

出力例 2

1
3
2