AtCoder Regular Contest 023

A - 経過日数

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

駆け出しプログラマーの高橋君は、バイト先の会社で、ある日付から今日の日付(2014 年 5 月 17 日)までの経過日数を計算するプログラムを作る仕事を割り当てられ、悩んでいました。最終的に、高橋君は「ある程度簡単な計算式に落とし込めたら高速化できるに違いない。」という信念のもとにいろいろ調べることで、ネットの海を彷徨っていると以下のような驚くべき公式を見つけました。この式の計算結果は、1 年 1 月 1 日から　y 年m月 d 日までの経過日数を表しているというのです。

ただしこの公式を使う際、ある年1 月と 2 月の場合についてのみは、前年の 13 月,14 月という扱いをすることとします。つまり、たとえば 2012 年 2 月 5 日の場合、y=2011,m=14,d=5 として公式を適用しなければなりません。

例えばこの公式に y=2014,m=5,d=17 を代入すると、735369 となり、1 年 1 月 1 日から2014 年 5 月 17 日までに、735369 日経過したことが分かります。

この公式を応用すれば、任意の2つの日付に対する日数差を計算することができます。例えば、1988 年 7 月 3 日と 2014 年 5 月 17 日の日数差は、(1年1月1日から2014年5月17日までの経過日数)-(1年1月1日から1988年7月3日までの経過日数) なので、735369-725920=9449 と求まります。

残念ながら高橋君は調べるだけで疲れて切ってしまったので、同僚であるあなたが彼の代わりにプログラムを書くことになりました。要するにあなたの仕事は、ある日付から今日の日付(2014 年 5 月 17 日)までの経過日数を計算するプログラムを作ることです。

入力

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

y
m
d

1 行目には、y (1 ≦ y ≦ 2014) が与えられる。
2 行目には、m (1 ≦ m ≦ 12) が与えられる。
3 行目には、d (1 ≦ d ≦ 31) が与えられる。
与えられる日付は2014年5月17日よりも前のものである。また、実際に存在しない日付は与えられない。つまり、m=4,6,9,11 のとき 1≦d≦30 であり、m=1,3,5,7,8,10,12 のとき 1≦d≦31 を満たす。残る m=2 については、y 年が閏年( yが 400 の倍数、もしくは y が 100 の倍数ではない 4 の倍数)であれば 1≦d≦29、閏年でなければ 1≦d≦28 を満たす。

出力

y 年 m 月 d 日から　2014 年 5 月 17 日までに経過した日数を一行に出力せよ。

入力例1

1988
7
3

出力例1

問題文の例です。1988 年 7 月 3 日から　2014 年 5 月 17 日までに9449日経過しています。

入力例2

1
1
1

出力例2

公式では、1 月と 2 月はそれぞれ前年(y-1 年)の 13 月と 14 月として扱わなければならないことに注意してください。

入力例3

2014
5
16

出力例3

入力例4

2012
2
29

出力例4

2012 年 2 月 29 日は閏日です。

B - 謎の人物X

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

高橋君は謎の人物Xに連れ去られてしまい、謎の施設に閉じ込められてしまいました。この施設の床には R 行 C 列のマス目が書かれていて、それぞれのマスには 1 つずつ数字が書かれています。高橋君はこのマス目の 1 行目の 1 列目のマスにいます。

長い時間閉じ込められていたので、高橋君はお腹が減ってきました。謎の人物Xによると、「隣のマスに移動する」ということをちょうど D 回行った後に高橋君がいるマスに書いてある数字と同じ値段のたこ焼きを用意してくれるそうです。あるマスの「隣のマス」とは、そのマスと辺を共有するマスのことを指します。高橋君は出来るだけ値段の高いたこ焼きが食べたいと思ったので、最大でいくらのたこ焼きを食べることが出来るかを考えることにしました。

入力

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

R C D
A_{1,1} A_{1,2} ... A_{1,C}
A_{2,1} A_{2,2} ... A_{2,C}
:
A_{R,1} A_{R,2} ... A_{R,C}

1 行目には、マス目の行数を表した整数 R (2 ≦ R ≦ 1,000) と、マス目の列数を表した整数 C (2 ≦ C ≦ 1,000) と、高橋君が移動しなければならない回数を表した整数 D (1 ≦ D ≦ 2,000) が空白区切りで与えられる。
続く R 行には、マス目に書かれている数字の情報が与えられる。このうちの i 番目の行には C 個の整数が空白区切りで与えられる。このうち j 番目の整数 A_{i,j} (1 ≦ A_{i,j} ≦ 999) は、i 行目の j 列目のマスに書かれている数字が A_{i,j} であることを表す。

部分点

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

R ≦ 100 かつ C ≦ 100 かつ D ≦ 200 を満たすテストケースすべてに正解した場合は 60 点が与えられる。

出力

高橋君が食べることができるたこ焼きの値段の最大値を 1 行に出力せよ。出力の末尾に改行をいれること。

入力例1

出力例1

ちょうど 1 回移動することで行くことが出来るマスは、1 行目の 2 列目のマスか 2 行目の 1 列目のマスだけです。このケースでは、高橋君は最大で 5 円のたこ焼きを食べることが出来ます。

入力例2

4 4 100
999 999 999 999
999 999 999 999
999 999 999 999
999 999 999 999

出力例2

このケースでは、高橋君はどのように移動しても 999 円のたこ焼きを食べることが出来ます。

入力例3

3 4 5
700 198 700 198
198 700 198 700
700 198 700 198

出力例3

このケースでは、高橋君はどのように移動しても 198 円のたこ焼きしか食べることが出来ません。

C - タコヤ木

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

高橋君が謎の人物Xからもらったたこ焼きを庭に植えると、たこ焼きの木が生えてきました。高橋君はその木に「タコヤ木」という名前をつけて大切に育てていました。ある日、高橋君はタコヤ木にたこ焼きの実がなっているのを見つけました。そこで高橋君はタコヤ木になったたこ焼きの実の個数を毎日数え、「今までになったたこ焼きの実の個数の合計」を記録していくことにしました。

記録を付け始めてから N 日が経ったある日、高橋君がたこ焼きの実をうっかり記録帳に落としてしまい、N 日分の記録のうちの一部が汚れて読めなくなってしまいました。高橋君はこの記録をなんとか復元したいと思い、まずは何通りの記録がありうるのかを計算してみることにしました。

入力

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

N
A_1 A_2 ... A_N

1 行目には、記録の日数を表した整数 N (1 ≦ N ≦ 2,000) が与えられる。
2 行目には、記録に関する情報を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 A_i (1 ≦ A_i ≦ 10^9 または A_i = -1) は、
- A_i が -1 のときは、i 日目の記録が汚れて読めなくなってしまったことを表す。
- A_i が -1 でないときは、i 日目の記録が読める状態であり、「i 日目までになったたこ焼きの実の個数の合計」が A_i 個であることを表す。
ただし、A_1 と A_N は -1 ではない。
入力データでは、記録として考えられるものが必ず 1 通り以上ありうることが保証されます。

部分点

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

N ≦ 100 かつ A_i ≦ 100 を満たすテストケースすべてに正解した場合は 50 点が与えられる。
A_i ≦ 2,000 を満たすテストケースすべてに正解した場合は 80 点が与えられる。

出力

N 日分の記録としてありうるものの個数を 1,000,000,007 (素数)で割った余りを 1 行に出力せよ。出力の末尾に改行をいれること。

入力例1

3
1 -1 3

出力例1

3 日分の記録としてありうるものは以下の 3 通りです。

1 1 3
1 2 3
1 3 3

記録しているものは「今までになったたこ焼きの実の個数の合計」であるため、ある日の記録が前の日の記録よりも少なくなることはないことに注意して下さい。

入力例2

6
2 -1 -1 9 -1 9

出力例2

入力例3

5
1 -1 -1 -1 1000000000

出力例3

999999972

答えは非常に大きくなることがあるため、1,000,000,007 で割ったあまりを求めることを忘れないで下さい。

D - GCD区間

実行時間制限: 3 sec / メモリ制限: 256 MB

問題文

高橋君は、数列を作って、それに関していろいろ操作を施すのが好きです。特に、区間の和や区間の最大公約数を計算したりといった区間に関していろいろ操作を施すのが大好きです。

そこで、高橋君は、ある数列に関して、区間の最大公約数がとある値 x となるような区間の数を数えることにしました。高橋君は、プログラムを使ってこの問題を解いたのですが、長い数列になればなるほど、時間がとても掛かってしまうことに気づきました。

あなたの仕事は、高橋君のために、数列が長いときでも高速に動作するプログラムを書くことです。また、オマケ機能として、同じ数列に対して、いくつか x の候補があっても、全ての x　について計算できるよう、問い合わせ機能をつけてあげることにしました。

あなたには、長さ n の数列 A=\{a_1,a_2,..,a_n\} が与えられます。また、問い合わせの数 m と、 x_1,x_2,..,x_m も与えられます。それぞれの x_i (1 ≦ i ≦ m) について、区間に含まれる全ての数の最大公約数が x_i となるような区間 [s,t] (1 ≦ s ≦ t ≦ n) の数を出力してください。

例えば、A=\{1,2,4\} のとき、最大公約数が1となる区間は、[1,1],[1,2],[1,3]の3つであり、最大公約数が2となる区間は、[2,2],[2,3] の2つであり、最大公約数が4となる区間は、[3,3] のみです。

入力

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

n　m
a_1
a_2
:
a_n
x_1
x_2
:
x_m

1 行目には、数列の長さを表す整数 n (1 ≦ n ≦ 100,000) と問い合わせの数 m (1 ≦ m ≦ 100,000) がスペース区切りで与えられる。
2 行目から n 行では、数列 Aの値が与えられる。このうち i 行目では数列 A の i 番目の値をそれぞれ表す整数 a_i (1 ≦ a_i ≦ 10^9) が与えられる。
n+2 行目から m 行では調べたい値が与えられる。このうち i 行目では i 番目の問い合わせにおける x の値をそれぞれ表す整数 x_i (1 ≦ x_i ≦ 10^9) が与えられる。

出力

それぞれの問い合わせに対する答えを順番に 1 行目から m 行出力せよ。出力の末尾にも改行をいれること。

入力例1

出力例1

与えられる数列は、問題文中のものです。

入力例2

出力例2

入力例3

出力例3