A - ニコニコ数

Time Limit: 2.525 sec / Memory Limit: 246 MB

問題文

ニコニコ数とは、10進法で表記したときに 2 と 5 が交互にあらわれ、かつ一番上の位が 2 で一番下の位が 5 であるものです。 例えば、 25, 2525, 252525252525252525 などはニコニコ数であり、 467, 5252, 5 などはニコニコ数ではありません。

ニワンゴくんは、 N 以下の正の整数のうち、約数にニコニコ数を持つものがいくつあるかを調べようと思いました。ニワンゴくんに代わって、この問題を解くプログラムを作ってください。

入力

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

N
  • 1 行目には、整数 N(1 ≦ N ≦ 10^9) が与えられる。

出力

N 以下の正の整数のうち、約数にニコニコ数を持つものの個数を 1 行に出力せよ。 出力の最後に改行を忘れないこと。

入力例1

42

出力例1

 1
42 以下でニコニコ数を約数に持つものは 25 だけです。

入力例2

20160123

出力例2

806404
B - 積み鉛筆

Time Limit: 2.525 sec / Memory Limit: 246 MB

問題文

ニワンゴくんは鉛筆を積むのが好きです。今日は以下の方法で鉛筆を積むことにしました。 まず、N本の鉛筆を左右に1列に床に並べます。左からi番目の鉛筆の長さはL_iです。

次に、N-1本の鉛筆を、床に並べた隣り合う2つの鉛筆の間の上に積みます。ただし、上に積む鉛筆の長さは、その下にある2つの鉛筆の長さのうち長い方と等しいです。すなわち、上に積む鉛筆のうち、左からj番目のものの長さをK_jと表すと、 K_j=max\{L_j,L_{j+1}\} が成り立ちます。

https://discovery2016-qual.contest.atcoder.jp/img/other/dwango2016qual/hdfksjghkjsdfhgkjsdhfgkjs/problem4.PNG

例えば、上図のような鉛筆の積み方があります。ここで、円の中に書かれている数は鉛筆の長さを表します。

積んだ鉛筆を上から見たとき、上に積まれたN-1本の鉛筆の長さのみ見え、N本の土台にある鉛筆の長さは分かりません。この状態で、土台となるN本の鉛筆の長さとしてありうるものを考えるゲームをニワンゴくんは思いつきました。 あなたの仕事はこのゲームに正解するプログラムを書くことです。ただし、土台となる鉛筆の長さの組み合わせは存在することが保証されています。

すなわち、N-1個の数からなる数列\{K_j\}が与えられたとき、 K_j=max\{L_j,L_{j+1}\} (1 ≦ j ≦ N-1)がすべてのjについて成り立つような数列\{L_i\}を求めてください。

入出力

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

N
K_1 K_2 … K_{N-1}
  • 1 行目には、土台となる鉛筆の本数 N (2 ≦ N ≦ 10^5)が与えられる。
  • 2 行目には、上に積まれている鉛筆の長さを表すN-1個の整数K_1,...,K_{N-1}が空白区切りで与えられる。
  • 1 ≦ K_i ≦ 10^9(1 ≦ i ≦ N)が成り立つ。

出力

土台となる鉛筆の長さL_1,...,L_Nを空白区切りで1行に出力せよ。出力の末尾には改行をいれること。

入力例1

4
3 5 5

出力例1

1 3 5 4

1, 3, 5, 4の長さの鉛筆を土台として3本の鉛筆を上に積むと、積まれた鉛筆の長さはそれぞれ3, 5, 5となることが分かります。よって、1, 3, 5, 4は答えの条件を満たします。

入力例2

6
4 8 8 2 5

出力例2

4 4 8 2 2 5

入力例3

5
1 2 3 4

出力例3

1 1 2 3 4
C - メンテナンス明け

Time Limit: 2.525 sec / Memory Limit: 246 MB

問題文

データセンターから出ると、外はもう高く太陽が昇っていた。

とにかく眠かった。午前2時頃から始まったニコニコ一斉メンテナンスは、予定通り午前10時頃に終了した。超過勤務ではなかったとはいえ、僕は生活リズムをずらすのがあまり得意ではないので、メンテナンス開始前にあまり睡眠を取れなかったのだ。一刻も早く家に帰って布団にダイブしたい・・・が、その前に電車を寝過ごすことなく無事に帰れるのかという不安があった。

N 個の駅と、 M 路線の電車からなる電車網がある。各路線は上り下り両方向に利用でき、ある路線が同じ駅に2回以上停車することはない。

僕はこの電車網を使って、駅 src から駅 dst へ移動したい。 しかし電車に乗り、その路線の停車駅間を移動しているときはいつでも眠り込んでしまう可能性がある。 眠ってしまった場合、本来降りるはずだった駅を通り過ぎて、その進行方向の終点の駅まで乗り続けてしまう。 終点の駅で目を覚ました後はすっきりするので、それ以降は電車を乗り過ごすことはなく、好きな経路で目的の駅まで移動できるだろう。

厄介なことに、僕は仕事中にエナジードリンクを飲んでしまっていて、まだ体からカフェインが抜けていない。つまり、移動中のどのタイミングに眠り込んでしまうかは全く予想できないのだ。

うまく移動経路を選んで、最も悪いタイミングで眠り込んだときの最終的な移動時間が最小になるようにしたい。そのような場合の移動時間はいくらだろうか？

入力

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

N M src dst
L_{0}
s_{0,0} s_{0,1} ... s_{0,L_{0}-1}
w_{0,0} w_{0,1} ... w_{0,L_{0}-2}
L_{1}
s_{1,0} s_{1,1} ... s_{1,L_{1}-1}
w_{1,0} w_{1,1} ... w_{1,L_{1}-2}
:

最初の行に N, M, src, dst (0 \leq src, dst < N) が与えられ、続く行に路線の情報が与えられる。

各路線の情報は3行で与えられる。 最初の行にはその路線に含まれる駅の数 L_{i} が与えられる。 2行目にはその路線が停車する駅が順に与えられる。 3行目には駅間の移動所要時間を表す L_{i} - 1 個の整数が与えられ、その j 番目の数はその路線の j 番目の駅と j+1 番目の駅の間の所要時間を示す（どちらの駅からどちらの駅に向かう場合でも所要時間は等しい）。路線の j 番目の駅から j+1 番目の駅への移動中に寝過ごした場合は L_{i} - 1 番目の駅まで移動することになり、路線の j+1 番目の駅から j 番目の駅への移動中に寝過ごした場合は 0 番目の駅まで移動することになる。同じ駅間を直接繋ぐ路線は複数あるかもしれないし、そのような場合には路線によって所要時間が異なるかもしれないことに注意せよ。

入力は以下の制約を満たす。

  • 2 \leq N \leq 25,252
  • 2 \leq L_{i} (0 \leq i < M)
  • L_{0} + L_{1} + ... + L_{M-1} \leq 252,525
  • 1 \leq w_{i,j} \leq 2,525
  • src \neq dst
  • どの路線も同じ駅に2回以上停まることはない。すなわち、j \neq k ならば s_{i,j} \neq s_{i,k}
  • src と dst 間の経路は1つ以上存在する

配点

部分点が設定されており、50 点分のデータセットは追加で以下の制約を満たす。

  • N \leq 252
  • L_{0} + L_{1} + ... + L_{M-1} \leq 525
  • w_{i,j} \leq 25

出力

問題文中で問われる移動時間を1行に出力せよ。出力の最後に改行を忘れないこと。

入力例1

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

出力例1

6

駅 0 から 1 に移動するときに寝過ごしてしまう可能性があるため、最適な経路は 0 - 1 - 2 - 1 - 3 となり、そのコストは 6 である。

入力例2

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

出力例2

8

入力例1と同形の電車網だが、駅間の移動時間だけが異なる。これにより、駅 0 - 1 間で寝過ごすよりも 1 - 3 間で寝過ごす方が所要時間が長くなってしまう。

移動中のどのタイミングで眠り込んでしまうかはコントロールできないことに注意せよ。 駅 0 - 1 - 2 間をどのように移動したとしても、ここで寝過ごすような経路を考えることはできない。駅 3 に辿り着くためには必ず駅 1 - 3 間を移動しなければならず、ここで寝過ごした方が悪い結果が得られてしまうためである。

入力例3

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

出力例3

2

最初の路線を使うと、寝過ごした場合に遠くまで運ばれてしまう。2つ目の路線は終着駅が目的地なので、どこで寝過ごそうとも時間 2 で目的地に辿り着くことが保証される。

D - 庭園

Time Limit: 2.525 sec / Memory Limit: 246 MB

問題文

dwango社は広い庭を持っています。この庭は南北にH行・東西にW列の1m四方の区画に分かれています。 北からi、西からj番目にある区画を区画(i,j)と表すことにします。 庭にはたくさんの花が咲いており、それぞれの区画についてその区画にある花の見栄えのよさを表す整数が定まっています。区画(i,j)の花の見栄えのよさを B_{i,j}と表すことにします。

少なくとも1つの区画からなる長方形を2つ決め、その2つの長方形を柵で囲い、柵で囲われていない場所を道にすることで、庭をきれいなものにしようとと考えました。ここで、2つの長方形の両方に含まれる区画があってはいけませんが、柵が重なるのは問題ありません。

庭全体のきれいさは、どちらかの長方形で囲われている区画の見栄えのよさの総和です。

理想の庭園を作るため、まずきれいさの最大値を求めることとなりました。 庭全体のきれいさの最大値を求めるプログラムを作成してください。

入出力

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

H W
B_{1,1} B_{1,2} … B_{1,W}
:
B_{H,1} B_{H,2} … B_{H,W}
  • 1 行目には、それぞれ庭園の南北、東西方向の長さである H, W (2 ≦ H ≦ 300, 2 ≦ W ≦ 300) が空白区切りで与えられる。
  • 1+i (1 ≦ i ≦ H)行目には、北からi番目の区画の見栄えのよさを表すW個の整数 B_{i,1}, ...,B_{i,W} が空白区切りで与えられる。
  • -10^9≦B_{i,j}≦10^9 (1 ≦ i ≦ H, 1 ≦ j ≦ W) が成り立つ。

配点

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

  • H ≦ 50, W ≦ 50 を満たすデータセットに正解した場合は 50 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に50点が与えられる。

出力

2つの長方形を決めたときの、庭全体のきれいさの最大値を1行に出力せよ。出力の末尾にも改行をいれること。

入力例1

3 3
1 1 1
1 1 1
1 1 1

出力例1

9

2つの長方形で庭全体を覆うと、きれいさは最大の9となります。

入力例2

3 3
-1 -1 -1
-1 -1 -1
-1 -1 -1

出力例2

-2

残念ながらきれいさが負となるときもあります。長方形は少なくとも1つの区画を含まなければいけないことに注意してください。

入力例3

2 3
5 -1 8
-1 4 -1

出力例3

16

例えば、以下のような囲み方があります。

https://discovery2016-qual.contest.atcoder.jp/img/other/dwango2016qual/hdfksjghkjsdfhgkjsdhfgkjs/problem2.PNG

入力例4

4 4
5 2 -3 2
3 8 -3 -10
4 5 3 2
-5 -3 3 5

出力例4

40
E - 花火

Time Limit: 2.525 sec / Memory Limit: 246 MB

問題文

ニワンゴくんは花火が大好きです。今夜ニワンゴくんが会社から家に帰るとき、ちょうど花火大会が行われていました。

会社からニワンゴくんの家までの道は直線であり、数直線とみなすことができます。会社の座標は 0 、ニワンゴくんの家の座標は L です。

今夜打ちあがる花火は全部で N 発であり、 i(1 ≦ i ≦ N) 発目の花火は時刻 t_i に位置 P_i(0 ≦ P_i ≦ L) で打ちあがります。

ニワンゴくんは会社から家への道を任意の速度で歩くことができますが、引き返すことはしません。ただし、途中で立ち止まることはできます。

ニワンゴくんは花火をなるべく近くで見たいと思っています。 そのため、ニワンゴくんは、すべての花火に対して、その打ち上げ時刻にニワンゴくんのいる座標と花火の打ちあがる座標の差の絶対値の合計をなるべく小さくしたいです。

すなわち、ニワンゴくんが時刻 t にいる座標を f(t) とすると、ニワンゴくんは実数から実数への広義単調増加な関数 f(t) をうまく設定し、すべての i に対しての |f(t_i)-P_i| の和を小さくしたいです。

ニワンゴくんに代わってこの問題を解いてください。

入力

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

N L
t_1 P_1
.
.
.
t_N P_N
  • 1 行目には、整数 N(1 ≦ N ≦ 10^5) と L(1 ≦ L ≦ 10^5) が空白を区切りとして与えられる。
  • 続く N 行には、 i 番目の花火の打ち上げ時刻と位置を表す整数 t_i(1 ≦ t_i ≦ 10^5) と P_i(0 ≦ P_i ≦ L) が空白を区切りとして与えられる。
  • すべての i(1 ≦ i ≦ N-1) について、 t_i ≦ t_{i+1} を満たす。また、 t_i = t_{i+1} なら P_i ≦ P_{i+1} を満たす。
  • 同じ時刻に、同じ位置で花火が打ちあがることもある。

部分点

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

  • N ≦ 2000, L ≦ 2000, t_i ≦ 2000 を満たすデータセットに正解した場合、部分点として 30 点が与えられる。

出力

すべての花火に対して、その打ち上げ時刻にニワンゴくんがいる座標と花火の打ちあがる座標の差の絶対値の総和の最小値を 1 行に出力せよ。 なお、この値が整数値になることは証明できる。 出力が 32 ビット符号付き整数の範囲に収まらない可能性があることに注意すること。

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

入力例1

5 10
1 2
1 4
3 8
4 7
5 1

出力例1

9

時刻 1 に座標 3 へ、時刻 3 に座標 7 へ、時刻 6 に家のある座標 10 に移動することで、打ち上げ時刻にニワンゴくんがいる座標と花火の打ちあがる座標の差の絶対値の総和を 9 にすることができます。それより小さい値にすることはできないので、 9 を出力します。

入力例2

4 10
1 4
1 4
2 1
3 9

出力例2

3

同時に、同じ座標で花火が打ちあがることもあります。

入力例3

10 20
2 15
3 4
3 14
4 11
6 0
7 7
8 8
8 8
8 12
9 10

出力例3

33