B - 銀メダル (Silver Medal) 解説 /

実行時間制限: 1 sec / メモリ制限: 64 MB

あなたは高校生向けの国際的なコンテストであと一歩のところで金メダルを逃し、帰国後に自分が受験生であることを発見するに至った。しかしあなたは、受験に必要な N 種類の勉強を全くこなしていない。

集中力に定評のあるあなたは、それぞれの勉強を連続した期間に行うことで、残り W 日の受験勉強を乗り切ることにした。

あなたはこの期間中に N 個の模擬試験を受験することにしている。

各模擬試験は開催日と影響力 d が決まっており、開催日前後 d 日未満の模試をあなたは意識している。そして、その日意識している模試の数があなたのやる気の数値となる。

i 種類目の勉強は i 以上のやる気がある時でないとできない。一日にできる勉強の個数には限りはないので、全ての種類の勉強について、連続して勉強できる最大の日数を調べたい。

課題

W 日間中に N 個の模試が行われる。模試には 0 から N-1 までの異なる整数の番号がつけられている。

それぞれの模試 i には開催日 X[i] と 影響度 D[i] が決まっている。日付 t に対して X[i]-D[i] < t < X[i]+D[i] が成り立つ場合に限り、あなたは日付 t のときに模試 i を意識している。

それぞれの日において、あなたの勉強のやる気はその日にあなたが意識している模試の数である。

あなたがやるべき勉強は N 種類ある。勉強には 1 から N までの異なる整数の番号がつけられている。勉強 k を行えるのはあなたのやる気が k 以上の日だけである。

次のパラメータを持つプロシージャ schedule(W, N, X, D) を実装せよ:

  • W -- 受験勉強の日数。受験勉強中の各日付は0以上W未満の整数で表される。
  • N -- 模試および勉強の数。模試には 0 から N-1、勉強には 1 から N の異なる整数の番号がつけられている。
  • X -- 模試の開催日を表す整数の配列。0 ≦ i < N に対し 0 ≦ X[i] < W を仮定してよい。
  • D -- 模試の影響度を表す整数の配列。0 ≦ i < N に対し 1 ≦ D[i] ≦ W を仮定してよい。X[i]-D[i] < 0X[i]+D[i] ≧ W となることはあるかもしれない。

それぞれの勉強 k について、あなたが勉強 k を連続して行うことのできる最も長い期間を計算し answer(k, L, R) を呼び出せ。L, R はそれぞれ勉強 k を連続して行うことのできる最長の期間の最初の日と最後の日である。勉強 k を行える日が 1 日もない場合は answer(k, 0, 0) と呼び出さねばならない。最長の期間が複数ある場合は L が最も小さいものを選ばねばならない。 answer(k, L, R) はどのような k の順番で呼び出しても構わないが、すべての勉強についてちょうど 1 回ずつ呼び出される必要がある。

なお、あなたは 1 日に何種類でも勉強をすることができるのでそれぞれの勉強について独立に考えてよい。すなわち異なる k の値について、answer(k, L, R) 呼び出しの L, R が表す期間は共通部分を持っていてもよい。

W = 10, N = 3,

X = 4
8
3
D = 2
4
1

の場合を考える。schedule は次のようなパラメータで answer を呼び出す必要がある。(この順番に呼び出す必要はない。)

パラメータ
answer(1, 3, 9)
answer(2, 3, 3)
answer(3, 0, 0)

小課題

小課題 1 (10 点)

  • 1 ≦ W ≦ 50
  • 1 ≦ N ≦ 50

小課題 2 (19 点)

  • 1 ≦ W ≦ 1 000
  • 1 ≦ N ≦ 1 000

小課題 3 (71 点)

  • 1 ≦ W ≦ 1 000 000 000
  • 1 ≦ N ≦ 100 000

実装の詳細

制限

  • CPU 時間制限: 1 秒
  • メモリ制限: 64 MB
    注意: スタックのサイズには決められた制限はない。スタックとして使用されたメモリは、メモリ総使用量に含まれる。

インターフェース (API)

  • 実装フォルダ: silver/ (プロトタイプ: silver.zip)
  • 競技者が実装するファイル: または silver.cpp
  • 提出ファイルのインターフェース: silver.h
  • 採点プログラムのサンプル: grader.cpp
  • 採点プログラムの入力のサンプル: grader.in.1, grader.in.2, ...
    注意:採点プログラムのサンプルは次の書式の入力を読み込む。
    • 1 行目: W, N が空白区切りで書かれている。
    • 2 行目から N+1 行目: 0 ≦ i < N に対し、i+2 行目には X[i]D[i] が空白区切りで書かれている。
  • 採点プログラムの入力のサンプルに対して期待される出力: grader.expect.1, grader.expect.2, ...
    注意:採点プログラムのサンプルは次の書式の出力を書き出す。
    • 1 行目から N 行目: 1 ≦ k ≦ N に対し、k 行目には勉強 k を行える最長の期間を表す整数 L, R が空白区切りで出力される。