Time Limit: 2.525 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
ニワンゴ君は H 行 W 列のマス目を見つけました。
ニワンゴ君は下記の条件を満たすように全てのマスに 2
か 5
を書き込む方法を知りたいです。
2
が書かれたマスだけに着目し、上下左右斜め に隣接するマス同士に辺を張ったグラフを考えたとき、連結成分のサイズは全て 25
が書かれたマスだけに着目し、上下左右 に隣接するマス同士に辺を張ったグラフを考えたとき、連結成分のサイズは全て 5
条件を満たすような書き込み方が存在するかどうかを判定し、存在するならばその一例を示してください。
制約
- 与えられる入力は全て整数
- 1 \leq H,W \leq 2525
入力
入力は以下の形式で標準入力から与えられる。
H W
出力
条件を満たすような書き込み方が存在するならば Yes
を、しないならば No
を出力してください。
存在する場合、書き込み方を2行目以降に以下の形式で出力してください。
c_{i,j} は、 i 行、 j 列目のマスに書き込んだ整数です。
c_{11} \cdots c_{1W} \vdots c_{H1} \cdots c_{HW}
入力例1
1 2
出力例1
Yes 22
22
が条件を満たす唯一の書き込み方です。55
は連結成分のサイズが全て 5 という条件に違反することに注意してください。
入力例2
1 1
出力例2
No
- 条件を満たす書き込み方が存在しない場合、
No
を出力してください。
Time Limit: 5.252 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
とある国では毎年、それぞれの町で採れた作物を集めた収穫祭をスーパーマーケットで開催しています。
この国には N 個の町があり、それぞれ 0, \ldots, N-1 の番号がついています。 また、0, \ldots, M-1 の番号がついた M 本の道があり、道 i は町 x_i と町 y_i を長さ d_i で双方向に繋いでいます。 すべての町のうち、番号が a_0, \ldots, a_{K-1} の K 個の町にスーパーマーケットがあります。
その年に収穫祭を開催するスーパーマーケットの集合は以下の条件から決定されます。
- 収穫祭に出品する町が、すべての町から 1 つ以上選ばれる
- 作物が新鮮な内に開催するため、選ばれたすべての町からの最短距離が D 以内のスーパーマーケットで開催する
- できる限り多くのスーパーマーケットで開催するため、上記に該当するすべてのスーパーマーケットで開催する
すべてのスーパーマーケットの集合 A' \subseteq \{ a_0, \ldots, a_{K-1} \} について、A' で収穫祭が開催されるような町の選ばれ方の個数を 998244353 で割った余りを計算し、それらのXORを出力してください。
制約
- 1 \leq N \leq 10^5
- 0 \leq M \leq \min \left(N(N-1)/2, 2 \times 10^5 \right)
- 1 \leq K \leq \min(N, 20)
- 1 \leq D \leq 10^9
- 0 \leq a_i \leq N-1
- a_0, \ldots, a_{K-1} は相異なる
- 0 \leq x_i, y_i \leq N-1
- 1 \leq d_i \leq 10^9
- 入力中の値はすべて整数
- 町を頂点、道を辺とする無向グラフを考えたとき、そのグラフは多重辺や自己ループを含まない
入力
入力は以下の形式で標準入力から与えられる。
N M K D a_0 a_1 \ldots a_{K-1} x_0 y_0 d_0 \vdots x_{M-1} y_{M-1} d_{M-1}
出力
答えを出力せよ。
入力例1
3 1 3 1 0 1 2 1 2 1
出力例1
1
- 以下の場合、町 0 のスーパーマーケットで収穫祭が開催されます。
- 町 0 が出品する場合
- 以下の場合、町 1, 2 のスーパーマーケットで収穫祭が開催されます。
- 町 1 が出品する場合
- 町 1, 2 が出品する場合
- 町 2 が出品する場合
- 以下の場合、収穫祭を開催できるスーパーマーケットはありません。
- 町 0, 1 が出品する場合
- 町 0, 2 が出品する場合
- 町 0, 1, 2 が出品する場合
よって、1\ \mathop{XOR}\ 3\ \mathop{XOR}\ 3 = 1 が出力されます。
入力例2
5 4 3 2 1 2 3 0 1 2 1 2 1 2 3 5 3 4 5
出力例2
17
入力例3
4 2 4 2 0 1 2 3 0 1 1 2 3 1
出力例3
9
入力例4
9 9 4 6 1 3 6 8 1 4 4 6 7 1 4 5 3 3 6 2 4 7 5 7 8 1 1 5 3 1 0 2 4 8 1
出力例4
367
Time Limit: 5.252 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
1, \ldots, N の番号がついた N 個の頂点からなる木が与えられます。 1, \ldots, N-1 の番号がついた N-1 本の辺があり、辺 i は頂点 a_i,b_i をつないでいます。
ニワンゴ君は操作を N-1 回行います。i 回目の操作は以下の手順からなります。
- 木の辺を等確率で選ぶ(選ばれた辺を e, e の端点を u,v とする)
- u の次数を x, v の次数を y として xy 点得る
- e を取り除き、u,v を 1 つの頂点にまとめる(すなわち辺の縮約を行う)。
N-1 回の操作によって、ニワンゴ君が得た得点の総和の期待値に (N-1)! をかけた値(これは整数になることが示せます)を 998244353 で割ったあまりを求めてください。
制約
- 2 \leq N \leq 10^{5}
- 1 \leq a_i, b_i \leq N
- 与えられるグラフは木
入力
入力は以下の形式で標準入力から与えられる。
N a_1 b_1 \vdots a_{N-1} b_{N-1}
出力
答えを出力せよ。
入力例1
6 1 4 1 2 1 3 4 5 4 6
出力例1
1640
- 例えば 1 回目の操作で辺 1 が選ばれた場合、9 点を得てグラフは以下の図のように変化します
入力例2
3 1 2 2 3
出力例2
6
入力例3
20 12 10 12 14 12 9 17 9 1 17 1 2 11 2 11 15 13 11 13 4 5 1 20 5 3 4 16 11 3 18 17 8 20 7 6 3 19 2
出力例3
253636877
- 答えを 998244353 で割ったあまりを求めてください。
Time Limit: 2.525 sec / Memory Limit: 1024 MB
配点 : 1400 点
問題文
AtCoder 社のオフィスは N 個の部屋を N - 1 本の廊下で結んだ木構造をしています。 廊下 i は部屋 V_i と部屋 i + 1 を双方向に結んでいます。
あなたはオフィスの N 個の部屋から異なる 3 個の部屋を選び金庫を設置しました。 さらに、各部屋 v に対して、部屋 v とそれぞれの金庫が設置された部屋の距離を計算し、その中央値 M_v を記録しました。 しかし、その後、どの部屋に金庫を設置したか忘れてしまいました。
オフィスの構造および各部屋 v に対する値 M_v が与えられます。 金庫の設置場所として考えられるような異なる 3 個の部屋の組の個数を求めてください。
なお、部屋 x と部屋 y の距離とは、部屋 x から部屋 y へ廊下を通って移動する際に通る廊下の本数の最小値のことです。
制約
- 3 \leq N \leq 100,000
- 1 \leq V_i \leq i (1 \leq i \leq N - 1)
- 1 \leq M_v \leq N - 1 (1 \leq v \leq N)
- 入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N V_1 V_2 \vdots V_{N - 1} M_1 M_2 \vdots M_N
出力
答えを出力せよ。
入力例 1
8 1 2 1 4 1 6 4 2 1 2 1 2 3 4 2
出力例 1
2
条件を満たす部屋の組は (部屋 1, 部屋 3, 部屋 5) と (部屋 1, 部屋 3, 部屋 8) の 2 個あります。
入力例 2
5 1 2 3 4 1 1 1 1 1
出力例 2
0