第2回ドワンゴからの挑戦状本選(オープンコンテスト)

A - 通勤

Time Limit: 2.525 sec / Memory Limit: 246 MB

問題文

ニワンゴくんはdwango社のオフィスに通勤しています。家からオフィスまでの距離はNメートルです。ニワンゴくんは人間ではないので、通勤の方法も少し特殊です。

具体的には、以下の2つの手順を行いオフィスに向かいます:

オフィスに向かってLメートル飛行する
Lの値をx倍にする。ただし、xはニコ数でなければならない。

この 2 つの手順は、好きな順番で、好きな回数だけ行うことができます。ここで、ニコ数とは、10進法で表すとそれぞれの桁が2または5からなる正整数で、隣り合う桁の数字が異なるような数のことです。例えば、2525, 5, 525はニコ数ですが、225, 334, 5255 はニコ数ではありません。

また、Lの値ははじめは1です。

ニワンゴくんは、通勤時間を減らすため、オフィスに向かって合計でちょうどNメートル進むために必要な飛行回数の最小値を求めたいと思っています。あなたの仕事は、ニワンゴくんに代わってこの最小値を求めるプログラムを書くことです。

入力

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

1 行目には、オフィスまでの距離を表す整数 N(1 ≦ N ≦ 10^{18}) が与えられる。

部分点

この問題には部分点が設定されている。

N ≦ 10^5 を満たすデータセットに正解した場合、部分点として 30 点が与えられる。
追加の制約のないデータセットに正解した場合、部分点として追加で 50 点が与えられる。合計で80点となる。

出力

ニワンゴくんの飛行回数の最小値を 1 行に出力せよ。出力の最後には改行を忘れないこと。

入力例1

出力例1

以下の方法で、飛行回数2回で3メートル進むことができます。1回以下で3メートル進む方法はありません。

1メートル飛行する
Lを2倍にする
2メートル飛行する

入力例2

出力例2

入力例3

出力例3

入力例4

出力例4

B - 道迷い

Time Limit: 5.252 sec / Memory Limit: 246 MB

問題文

dwango社に新しいオフィスができました。今日は、そのオフィスで仕事が行われる最初の日です。

社員のニワンゴくんは朝オフィスに行こうとして、オフィスの最寄り駅に着いたところで大変なことに気付きました。なんと、オフィスの場所を知らなかったのです。

dwango社の新しいオフィスはある 1 本の道路上にあり、オフィスの最寄り駅は座標 0 にあります。道路には交差点が N 個あり、ニワンゴくんはその N 個の交差点のうちのどれかにオフィスがあることを知っています。負の座標にオフィスがあるかもしれません。なお、駅のある座標 0 に交差点はないものとします。

仕方がないので、ニワンゴくんはこの道路上を歩き回ってオフィスを探すことにしました。ニワンゴくんは交差点のある座標に着いたとき、またその時のみ、そこにオフィスがあるかどうかがわかります。

さて、ニワンゴくんの上司はニワンゴくんが駅に着いた時刻を知っています。 dwango社の社員はみな単位時間に単位距離進む速度で歩くので、駅からオフィスまでの距離を x として、ニワンゴくんが駅に着いた時刻を0とすると、ニワンゴくんがオフィスに着くのが時刻 x よりあとになると、ニワンゴくんは怒られてしまいます。時刻 x より前になるぶんにはかまいません。

そこでニワンゴくんは、常に一定の速度で走って移動することで、オフィスがどの交差点にある場合でも、駅とオフィスの間の距離が x であるならば時刻 x までにオフィスに到着することを考えました。ニワンゴくんはなるべくゆっくり走りたいので、適切な移動経路を選んで、走る速度を最小にすることにしました。

ニワンゴくんの走る速度としてありうる最小の値を求めてください。

入力

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

N
x_1
.
.
.
x_N

1 行目には、整数 N(1 ≦ N ≦ 1000) が与えられる。
続く N 行には、 i 番目の交差点の位置を表す整数 x_i(-10^9 ≦ x_i ≦ 10^9, x_i ≠ 0) が与えられる。任意の i(1 ≦ i ≦ N-1) に対し、 x_i < x_{i+1} を満たす。

部分点

この問題には部分点が設定されている。

N ≦ 200 を満たすデータセットに正解した場合、部分点として 70 点が与えられる。
すべてのデータセットに正解した場合、追加で 50 点が与えられ、合計で 120 点となる。

出力

ニワンゴくんの走る最小の速度を 1 行に出力せよ。小数点以下何桁まで出力してもかまわないが、真の値との絶対誤差あるいは相対誤差が 10^{-9} 以下のとき正答とみなされる。

出力の最後には改行を忘れないこと。

入力例1

出力例1

3.00000000000000

ニワンゴくんの動きの例として、以下のものが挙げられます。

速度 3で 2 番目の交差点に移動し、そこがオフィスかどうか判定する。
オフィスでなければ、速度 3 で 3 番目の交差点に移動し、そこがオフィスかどうか判定する。
オフィスでなければ、速度 3 で 4 番目の交差点に移動し、そこがオフィスかどうか判定する。
オフィスでなければ、速度 3 で 1 番目の交差点に移動し、そこがオフィスかどうか判定する。

この行動をとった場合、 1,2,3,4 番目の交差点には順に 3,1/3,1,4/3 単位時間で移動することができるので、問題文の条件を満たします。

入力例2

出力例2

4.14285714285714

入力例3

出力例3

4.37500000000000

C - 電波塔

Time Limit: 2.525 sec / Memory Limit: 246 MB

問題文

dwango社は電波塔を N 基持っており、すべての電波塔は一直線上に並んでいます。この直線を数直線とみなしたとき、 i 番目の電波塔は座標 x_i にあり、高さは h_i です。諸事情により、x_i, h_i はすべて正の偶数です。また、任意の i≠j に対し、 x_i≠x_j,h_i≠h_j を満たします。

各電波塔は、自分より座標が大きく、かつ高さも高いような電波塔のみに情報を送ることができます。

ニワンゴくんはより多くの電波塔を経由して届いた情報が好きです。そのため、整数列 a_1,a_2,...,a_t であって、 x_{a_k} < x_{a_{k+1}} かつ h_{a_k} < h_{a_{k+1}} がすべての 1 ≦ k ≦ t-1 で成り立つようなもののうちの最大の長さと等しい嬉しさを得ます。

dwango社はニワンゴくんのために、新しく電波塔を 1 基作ってあげることにしました。諸事情により、その電波塔のある座標と電波塔の高さはともに正の奇数でなければなりません。

ニワンゴくんの嬉しさが増加するように電波塔を作るとき、その (座標, 高さ) の組としてありうるものはいくつあるか答えてください。

なお、座標が W より大きい場所と、高さが H より高い場所には強力な磁気嵐が発生しているので電波塔はなく、また新しく作ることもできません。

入力

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

N W H
x_1 h_1
.
.
.
x_N h_N

1 行目には、整数 N(1 ≦ N ≦ 252525) と W(4 ≦ W ≦ 10^9, Wは偶数) と H(4 ≦ H ≦ 10^9, Hは偶数) が空白を区切りとして与えられる。
続く N 行には、 i 番目の電波塔の座標と高さを表す整数 x_i(2 ≦ x_i ≦ W-2, x_iは偶数) と h_i(2 ≦ h_i ≦ H-2, h_iは偶数) が空白を区切りとして与えられる。
すべての i(1 ≦ i ≦ N-1) について、 x_i < x_{i+1} を満たす。また、 i ≠ j なら h_i ≠ h_j を満たす。

部分点

この問題には部分点が設定されている。

N ≦ 52 を満たすデータセットに正解した場合、部分点として 20 点が与えられる。
N ≦ 2525 を満たすデータセットにも正解した場合、部分点として追加で 20 点が与えられる。
すべてのデータセットに正解した場合、追加で 80 点が与えられ、合計で 120 点となる。

出力

ニワンゴくんの嬉しさを増加させるような新しい電波塔の位置の (座標, 高さ) の組としてありうるものの個数を表す整数を 1 行に出力せよ。出力が 32 ビット符号付き整数の範囲に収まらない可能性があることに注意すること。

出力の最後には改行を忘れないこと。

入力例1

2 6 6
2 4
4 2

出力例1

(座標,高さ) の組としてありうるものは、 (1,1),(1,3),(3,1),(3,5),(5,3),(5,5) の 6 つです。

入力例2

出力例2

入力例3

出力例3

入力例4

5 252525252 555255252
25252 52525252
22225252 2225252
55252252 552222222
252522222 52
252525222 555222222

出力例4

7475142133811101

D - 木

Time Limit: 2.525 sec / Memory Limit: 246 MB

問題文

N頂点からなる重み付き無向木が与えられます。頂点は1からNまで番号付けられています。

はじめ、すべての辺の重みは1です。頂点u,vに対し、dist(u,v)をuとvを結ぶ最短経路の辺の重みの総和と定めます。

また、頂点u,vに対し、

f(u,v)=max\{dist(u2,v2)|dist(u,v2)=dist(u,v)+dist(v,v2) かつ dist(v,u2)=dist(v,u)+dist(u,u2)\}

と定めます。すなわち、頂点u,vを互いに遠ざける方向へのみ動かしたときの距離の最大値と定めます。

「木全体のコスト」を

∑_{u∈ \{1,...n\} ,v ∈ \{1,...,n\} , u < v} f(u,v)

と定めます。

それぞれの辺に対し、その辺の重みを2としたときに「木全体のコスト」がどれだけ増えるか出力するプログラムを作成してください。

入力

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

N
p_1 p_2 ... p_{N-1}

1 行目には、木の頂点を表す整数 N(2 ≦ N ≦ 252525) が与えられる。
2 行目には、木の辺を示す整数がN-1個空白区切りで与えられる。i(1 ≦ i ≦ N-1)番目の整数は、頂点p_i(1 ≦ p_i ≦ i)と頂点i+1を結ぶ木の辺の辺があることを表す。

部分点

この問題には部分点が設定されている。

N ≦ 300 を満たすデータセットに正解した場合、部分点として 30 点が与えられる。
N ≦ 3000 を満たすデータセットに正解した場合、部分点として追加で 50 点が与えられる。合計で80点となる。
追加の制約のないデータセットに正解した場合、部分点として追加で 160 点が与えられる。合計で240点となる。

出力

N-1個の整数を空白区切りで1行に出力せよ。

i(1 ≦ i ≦ N-1)番目の整数は、辺(p_i,i+1)の重みを2としたときの「木全体のコスト」の増加を表す。

行末に余計な空白を入れないこと。また、出力の最後には改行を忘れないこと。

入力例1

5
1 1 2 2

出力例1

9 9 7 7

辺(1,2), (1,3)の重みを2としたとき、

1≦ u<v≦ Nを満たす(u,v)の組はN*(N-1)/2=10個あります。

(u,v)≠(4,5)のときf(u,v)は1増加し、(u,v)=(4,5)のときf(u,v)は変化しません。そのため、「木全体のコスト」は9増加します。

辺(2,4)の重みを2としたとき、

(u,v)=(2,4),(1,4),(3,4),(4,5),(1,3),(1,2),(2,3)のときf(u,v)は1増加し、これら以外のときf(u,v)は変化しません。そのため、「木全体のコスト」は7増加します。

辺(2,5)の重みを2としたとき、

(u,v)=(2,5),(1,5),(3,5),(4,5),(1,3),(1,2),(2,3)のときf(u,v)は1増加し、これら以外のときf(u,v)は変化しません。そのため、「木全体のコスト」は7増加します。

入力例2

8
1 1 2 3 1 4 3

出力例2

24 23 24 18 7 24 18

入力例3

5
1 1 1 1

出力例3

7 7 7 7

入力例4

10
1 2 2 2 3 3 4 5 6

出力例4

9 35 25 25 30 9 25 25 30