D - 木からパスへ (Tree--->path)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 150 点

問題文

platypusくんは，射的の景品で N 頂点からなる連結な無向木をもらいました． このままでは持ち運びにくいので，木を一つのパスにしたいと思いました． (パスとは，すべての頂点の次数が高々2の木のことです) platypusくんは以下の操作で木をパスにします．

  1. 頂点を好きなだけ追加する
  2. 木の頂点と1.で追加した頂点との間に，好きなだけ無向辺を加える (木の頂点同士，また1.で追加した頂点同士を辺で結ぶことはできない)
  3. 2.でできたグラフから，閉路がなくなるまで好きなだけ辺を削除していき，一つの連結なパスにする

以上の操作で，platypusくんは1.で追加する頂点をなるべく少なくしたいと思いました． 与えられた木を上記の操作でパスにするための最小の頂点追加数を求めるプログラムを作りなさい．

制約

すべてのテストケースは以下の制約を満たします．

  • 2 \leq N \leq 200000
  • 1 \leq u_{i},v_{i} \leq N (1 \leq i \leq N-1)
  • 与えられるグラフは木である．

入力

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

N
u_{1} v_{1}
u_{2} v_{2}
:
u_{N-1} v_{N-1}
  • 1行目には整数 N が書かれている．これは，platypusくんが入手したグラフの頂点数を表している．
  • 続く N-1 行のうち i 行目には二つの整数 u_{i} と v_{i} が空白区切りで書かれている．これは，グラフの i 番目の辺は頂点 u_{i} とv_{i} を結んでいることを表している．

出力

標準出力に，与えられたグラフをパスにするための最小の頂点追加数を一行で出力しなさい．

入力例 1

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

出力例 1

2

2 つの頂点を追加すればよいです． 追加した頂点を X ,Y と呼ぶと， X と 4 ， X と 5 ， Y と 5 ， Y と 6 を辺で結び，最後に 2 と 5 ， 3 と 6 を結ぶ辺をそれぞれ消すと， 6 - Y - 5 - X - 4 - 2 - 1 - 3 - 7というひとつながりのパスが残ります． 1 つの頂点追加のみでこのグラフをパスにすることはできないので，求める答えは 2 です．

入力例 2

5
1 3
3 2
2 5
5 4

出力例 2

0

与えられたグラフはすでにパスのため，答えは 0 です．

入力例 3

9
3 5
4 6
4 2
5 9
8 5
1 2
7 4
3 1

出力例 3

2
E - 石積み (Pyramid Piling)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 150 点

問題文

MMNMMさんは夏祭りに出ていた N 次元石屋さんで N 次元の小石をたくさん買いました．
MMNMMさんはこの N 次元の小石をある正の整数 s について一辺 s の N 次元空間上の三角形状に積みます．ただし，小石を一辺 s の N 次元空間上の三角形状に積むとは，

  • N 次元空間の格子点 (x_1, x_2, ... , x_N) であって， すべての i について x_i \geq 0 が成り立ち，かつ x_1 + x_2 + … + x_N < s が成り立つようなものすべてに1つずつ石を置くように石を積む

ことをいいます．
MMNMMさんは買った石で一辺 s_1 の N 次元空間上の三角形状に石がちょうど積めることがわかり，さらに一辺 s_2 の N-1 次元空間上の三角形状にもちょうど積めることがわかりました．
このとき， s_1 と s_2 (s_1 \neq s_2) としてありえる整数の組を一組出力してください．
ただし，MMNMMさんはか弱いプログラマーなので小石を 10^{100000} 個以上買うことはできず，狭い部屋に住んでいるので一辺 10^{18} 以上の三角形状に小石を積むことはできません．

制約

すべてのテストケースは以下の制約を満たします．

  • 2 \leq N \leq 10^5
  • MMNMMさんが買う小石の数が 10^{100000} 個未満であり， s_1 と s_2 がともに 10^{18} を超えないような解が存在することが保証されている．

入力

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

N
  • 1行目には，整数 N が書かれている．これは，売られている小石が N 次元小石であり，MMNMMさんが N 次元および N-1 次元空間上の三角形状に小石を積んだことを表している．

出力

標準出力に，s_1 と s_2 としてありえる整数の組をこの順に空白を区切りとしてを1行に出力しなさい．
ただし，買う小石の数が 10^{100000} を， s_1 と s_2 が 10^{18} を超えてはならない．

入力例 1

2

出力例 1

10 55

一辺10の三角形状に石を並べると55個の石が必要で，これを一列に並べると一次元の三角形状になります．

入力例 2

3

出力例 2

20 55

どちらもちょうど1540個の石を使います．
F - 冪冪ゲーム (Powerful Fever!)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 150 点

問題文

MMNMMさんは屋台で賭け事をしています．
この賭け事は小さい勝負を繰り返すもので，勝ち続ける限りいくらでも続き，負けた時点で終了になります．
この賭け事には正の整数 a ， M が定まっています．
1回目の勝負に勝つと 1 点がもらえ， n 回目の勝負( n>1 )回目の勝負に勝つと， n-1 回目の勝負でもらった点数 x 点について， a^x 点がもらえます．
勝負に負けると 0 点がもらえます．
賭け事が終了したときの合計点数を M で割ったあまりが最終的なポイントとなり，ポイントに応じて景品がもらえます．
MMNMMさんは賭け事で合計 K 回の勝負をしました(つまり， K-1 回勝ちました)．MMNMMさんの最終的なポイントを求めてください．

制約

すべてのテストケースは以下の制約を満たします．

  • 1 \leq a \leq 10^{18}
  • 1 \leq M \leq 10^9+7 ， M は素数
  • 1 \leq K \leq 10^{18}

入力

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

a M K
  • 1行目には，整数 a ， M ， K がこの順に空白を区切りとして書かれている．これは，賭け事に定められている定数が a と M であり，MMNMMさんが K 回勝負をしたことを表している．

出力

標準出力に，MMNMMさんが賭け事で得たポイントを1行に出力しなさい．

入力例 1

2 19 6

出力例 1

9

1 + 2 + 2^2 + 2^{2^2} + 2^{2^{2^2}} + 0 = 1 + 2 + 4 + 16 + 65536 + 0 = 65559 で， 65559 を 19 で割ったあまりは 9 なので，MMNMMさんは9ポイントを得ることができます．

入力例 2

3 101 3

出力例 2

4

入力例 3

1333 1000000007 8691201001

出力例 3

589246632
G - 屋台衝突 (Food Stall Collision)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 150 点

問題文

夏祭りには N 種類の屋台が鳥居から神社の拝殿に通じる長さ 2N の道にかけて並んでいます． この道は 2N 個の区画に等間隔に分割されていて，鳥居から数えて k 番目の区画を区画 k と呼びます．また， i 番目の屋台を屋台 i と呼びます．

各屋台は，店を開くためにあらかじめ神社に営業許可を取った結果，今年はどの屋台もちょうど 2 つの区画を使ってよいことになりました． 具体的には，屋台 i には，区画 A_{i} と区画 B_{i} の使用許可が下りました． 整数A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N} はすべて異なり，すべての i について A_{i} \lt B_{i} が成立します． 屋台 i は，神社に営業許可を出された区画 A_{i} と B_{i} を行き来する時に， A_{i} \leq p \leq B_{i} を満たすすべての整数 p について，区画 p を一時的に通過する必要があります． このような区画 p を「屋台 i の通路上に存在する」と言います．

屋台 x と屋台 y について，二つの屋台両方の通路上に存在する区画がある場合，商売するうえで支障が生じるかもしれません． そこで，神社は屋台同士の関係を把握するために，すべての x \neq y である屋台の組 x, y について，二つの屋台両方の通路上に存在する区画がある場合，頂点 x と頂点 y を無向辺で結んだ頂点数 N のグラフを作成しました． platypusくんは，夏祭りを最大限に楽しむために，裏ルートでこのグラフを入手しましたが，なんとこのグラフは連結な無向木でした． そこで，この木から元の A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N} を復元しようと思いました．

この木から，元の整数の組 (A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N}) として考えられるものは何通りあるかを答えるプログラムを作成しなさい． ただし，答えは非常に大きくなる可能性があるため， 1000000007 で割った余りを出力しなさい．

制約

すべてのテストケースは以下の制約を満たします．

  • 2 \leq N \leq 200000
  • 1 \leq u_{i},v_{i} \leq N (1 \leq i \leq N-1)
  • 与えられるグラフは連結な無向木である．

入力

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

N
u_{1} v_{1}
u_{2} v_{2}
:
u_{N-1} v_{N-1}
  • 1行目には整数 N が書かれている．これは，platypusくんが入手したグラフの頂点数を表している．
  • 続く N-1 行のうち i 行目には二つの整数 u_{i} と v_{i} が空白区切りで書かれている．これは，グラフの i 番目の辺は頂点 u_{i} と v_{i} を結んでいることを表している．

出力

標準出力に，与えられたグラフと同じグラフが作られるような (A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N}) が何通り存在するかを 1000000007 で割った余りを一行で出力せよ． ただし，platypusくんの勘違いなどによって 0 通りの入力ケースも存在しうることに留意せよ．

入力例 1

3
1 2
1 3

出力例 1

8

この場合，考えられる (A_{1}, A_{2}, A_{3}, B_{1}, B_{2}, B_{3}) は以下の 8 通りあります．

(A_{1}, A_{2}, A_{3}, B_{1}, B_{2}, B_{3}) =
(1,2,4,5,3,6)
(1,2,4,6,3,5)
(1,4,2,5,6,3)
(1,4,2,6,5,3)
(2,1,4,5,3,6)
(2,1,4,6,3,5)
(2,4,1,5,6,3)
(2,4,1,6,5,3)

すべての i について A_{i} \lt B_{i} という制約が存在することに注意しなさい．

入力例 2

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

出力例 2

0

このようなグラフができる (A_{1}, A_{2}, ..., A_{7}, B_{1}, B_{2}, ..., B_{7}) は存在しないため，求める答えは0です．
H - 圧縮おみくじ (Compressed Omikuji)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

platypusくんが神社でおみくじを引いたところ，そこには文字列 S が書かれていました． 文字列 S はアルファベットの小文字，および * という文字から構成されています．

この神社は，回文，すなわち左から読んでも右から読んでも同じ文字列を縁起が良いとしています． platypusくんは，おみくじの縁起の良さを確かめたいと思っています． そこで，以下の操作で文字列 S から回文を構成できるかを判定することにしました．

  1. 英小文字で構成された長さ N の文字列を一つ作る．
  2. 文字列S中のすべての*を1.で選んだ文字列で置き換える．

文字列 S と整数 N が与えられたとき，上記の操作で回文を構成することが可能かを答えるプログラムを作りなさい．

制約

すべてのテストケースは以下の制約を満たします．

  • 1 \leq N \leq 200000
  • 文字列 S は英小文字および * で構成されている
  • 文字列 S は * を一文字以上含む
  • 1 \leq |S| \leq 200000 ( |S| は文字列 S の長さ)

入力

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

N
S
  • 1行目には整数 N が書かれている．これは，platypusくんが操作1.で作る文字列の長さを表している．
  • 2行目には文字列 S が書かれている．これは，platypusくんが引いたおみくじに書かれていた文字列を表している．

出力

標準出力に，回文を構成することが可能な場合は Yes を，不可能な場合は No を一行で出力しなさい．

入力例 1

2
a**

出力例 1

Yes

例えば文字列 ba を作ると，文字列 S は ababa となり，回文を構成することができます．

入力例 2

3
a*b

出力例 2

No

先頭文字が a で末尾文字が b である文字列は回文にはなりえません．

入力例 3

3
*xy**

出力例 3

Yes

入力例 4

2
*xy**

出力例 4

No
I - うっかり者のニム (Careless Nim)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

MMNMMさんはplatypusくんとニム屋の屋台でニムで遊ぶことにしました．
ニムとは，複数の石の山を使って遊ぶゲームで，プレイヤーは先手と後手に分かれます．
プレイヤーは自分の手番に次のことをすることができます．

  • 石の山から一つの山を選び，その山にある石のいくつかを取り去る．

石がなくなり，石を取ることができなくなったプレイヤーが負けです．

platypusくんは十分頭がいいので常に最良の手を打ちます．
しかし，MMNMMさんはうっかり者なので確率 1 - p/q で最良の手を打ち，確率 p/q で最悪の手を打ちます．(どちらになるかは毎手番ごとに独立に判定されます)
2人はこの事実を知っています．
ここで，最良の手とは自分の打てる手のうち，それを打ったときに勝つ確率が最大となるものであり，最悪の手とはそれを打った時に勝つ確率が最小となるものです．

MMNMMさんは先手です．
MMNMMさんがplatypusくんに勝てる確率を既約分数 P/Q で表します．
このとき， 0 以上 10^9+7 未満の整数 M であって MQ と P をそれぞれ 10^9 + 7 で割ったあまりが等しいようなもの (つまり，p = 10^9 + 7 での Q の \mathbb{Z}/p\mathbb{Z} における逆元 Q^{-1} に対する PQ^{-1}) がただ1つ存在します．
M を求めてください．

制約

すべてのテストケースは以下の制約を満たします．

  • 1 \leq N \leq 10^5
  • 1 \leq a_i \leq 10^{12}
  • 0 \leq p \leq q \leq 10^9
  • 1 \leq q
  • p と q は互いに素である

入力

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

N p q
a_1 a_2 ... a_N
  • 1行目には，整数 N ， p ， q がこの順に空白を区切りとして書かれている．これは，ニム山が N 個あり，MMNMMさんが最悪の手を p/q の確率で打つことを表している．
  • 2行目には，整数 a_i (1 \leq i \leq N) がこの順に空白を区切りとして書かれている．これは， i 番目のニム山にははじめ a_i 個の石があることを表している．

出力

標準出力に，MMNMMさんがplatypusくんに勝てる確率を P/Q としたときの，\mathbb{Z}/p\mathbb{Z} における P \times Q^{-1} を1行に出力しなさい．

入力例 1

1 1 2
3

出力例 1

500000004

一回目でMMNMMさんがすべての石をとれなければ負けるので，MMNMMさんが勝つ確率は 1/2 です．
1 と 2 \times 500000004 を 10^9+7 で割ったあまりは等しいので，500000004を出力してください．

入力例 2

3 1 2
1 1 1

出力例 2

1

入力例 3

4 1 10
3 2 5 4

出力例 3

0

入力例 4

10 1 100
3 14 15 9 2 6 5 35 8 9

出力例 4

135181044
J - 楽しい結界作り (Making Barriers Is Fun)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

神の使いであるMMNMMさんは，夏祭りの騒ぎで悪霊が住み着かないように境内に結界を張ることにしました．

境内には N 個の灯籠があり， i 個目の灯籠は座標 (X_{i},Y_{i}) に存在します．同じ座標に二つの灯籠が存在することはありません．

MMNMMさんは以下の2つの結界の貼り方を好きな順番で何回でも行うことができます．

  • X座標またはY座標が等しい二つの灯籠を端点とした線分上に結界を張る．
  • 既に存在する結界と灯籠について，灯籠からその結界に垂線を下ろして，その足が結界上に存在する場合，灯籠と垂線の足を結ぶ線分上に新たな結界を張る．

MMNMMさんは，上の二つの操作によってなるべく結界が貼られている線分の長さの和を大きくしようとしています．(異なる二つの結界が同じ線分を共有している場合，重なった部分の長さを複数回足し合わせないことに注意しなさい．詳しくは入出力例の解説を参照しなさい．)

N 個の灯籠の座標が与えられたとき，MMNMMさんが張れる結界を通る線分の長さの和を求めるプログラムを作りなさい．

制約

すべてのテストケースは以下の制約を満たします．

  • 2 \leq N \leq 200000
  • -1000000000 \leq X_{i},Y_{i} \leq 1000000000 (1 \leq i \leq N)
  • i \neq j ならば X_{i} \neq X_{j} または Y_{i} \neq Y_{j}

入力

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

N
X_{1} Y_{1}    
X_{2} Y_{2}    
:
X_{N} Y_{N}
  • 1行目には整数 N が書かれている．これは，神社の境内に存在する灯籠の個数を表している．
  • 続く N 行のうちの i 行目には二つの整数 X_{i} と Y_{i} が空白区切りで書かれている．これは i 番目の灯籠が座標 (X_{i},Y_{i}) に存在することを示している．

出力

標準出力に結界の長さの総和を出力しなさい．

入力例 1

3
0 0
1 2
2 0

出力例 1

4
  1. 1番目の灯籠と3番目の灯籠はY座標が等しいため，MMNMMさんは座標 (0,0) と (2,0) を端点とした線分上に結界を張れます．
  2. 2番目の灯籠から，1. で張った結界へ下ろした垂線の足は，1. で張った結界上に存在するため，MMNMMさんは座標 (1,0) と (1,2) を端点とした線分上に結界を張れます．

これ以外の位置に結界を張ることはできないので，求める結界の長さの和は2+2=4となります．

入力例 2

5
1 1
4 3
1 3
2 2
3 1

出力例 2

13

最終的に，図に示されている直線群上に結界が張られることになります．

入力例 3

4
123 456
789 12
345 678
901 234

出力例 3

0

結界を張ることができない灯籠の位置が存在することにも注意しなさい．