第二回 アルゴリズム実技検定 M問題メモ
M - Cafeteria（食堂）
問題
- ある食堂では、$D$ 日周期で $C_1,C_2,...,C_D$ の順にメニューが繰り返される（明日が $C_1$）
- $N$ 人の社員それぞれについて、以下の問いに答えよ
- 社員 $i$ は料理 $K_i$ を好む
- 今日から $F_i$ 日後に初めて食堂を利用し、以下のルールに従って $T_i$ 回食堂を利用する
- ルール
- $F_i$ 日以降、好みの料理が出される日は必ず利用する
- それ以外の日は、前回の利用が $L$ 日前であれば利用する
- 社員 $i$ が食堂で好みの料理を食べる回数を求めよ
- $1 \le N,D,C_i,K_i \le 10^5$
- $1 \le L,T_i \le 10^9$
- $1 \le F_i \le D$
例
K = 1 好みの料理
F = 7 初めての利用日
L = 2 好みでなくても2日毎に利用
T = 12 回目の利用まで
i 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
----------------------------------------------------------------
C 4 4 4 3 1 1 5 2 2 1 4 4 4 3 1 1 5 2 2 1 4 4 4 3 1 1 5 2 2 1
x x o x x o o x o x x o
x: 好みでないが利用
o: 好みで利用
解法
地道に要件を考えて実装していく。決して高度なアルゴリズムが必要なわけでは無いが、整理に手間取る問題。
まず、好みの料理がメニューに無いかわいそうな社員は計算するまでもなく0なので、その場合は除く。
$L$ が全ての社員で共通なので、何らかの事前計算を考える。
すると、各料理について、（$T_i$ が十分に大きければ）その料理を好む人が1周期で利用するパターンは同じになると気付く。
C 4 4 4 3 1 1 5 2 2 1 4 4 4 3 1 1 5 2 2 1 4 4 4 3 1 1 5 2 2 1 4 4 4 3 1 1 5 2 2 1 ...
x x o x x o o x o x x o o x o x x o o x o ...
`-----------------' `-----------------' `-----------------'
なので、以下の3つに分けて、総利用回数と好みの利用回数を考えればよさそう。
- 最初の1周期
- ↑↓の間のループ
- 最後の1周期
以下、ある1つの料理（1）に絞って考える。他の料理も同様に事前計算する。また、$C_i$ を0-indexedとする。
ループ部分
順番は前後するが、ここから考える。
（ループ部分の計算だけを考えると）以下のデータがあればよい。
- $t$: 1周期での総利用回数
- $p$: そのうち好みの利用回数
- $r_i$: $T_i$ から最初の1周期を除いた残り利用回数（これは社員依存）
$r_i / t = d あまり m$ なら $d$ 周期ループするので、好みは $d \times p$ 回食べ、最後の周期に $m$ 回残すこととなる。
好みの料理が出てくる日と日の間に $x$ 日空いていれば、$\dfrac{x}{L}$ 回、好みでなくても利用するので、 好みの料理が出てくるindexと、その間隔を調べていけばよい。
- ※周期の1番最初は、「前の周期で最後に好みの料理が提供されてから」の日数とする
L = 2
... 2 1 4 4 4 3 1 1 5 2 2 1 t: 1周期での利用回数: 6
o x x o o x o p: 好みが提供される回数: 3
`-----------------'
|<----------|<|<------|
中4日=2回 | 中3日=1回
中0日=0回
最初の1周期
一番厄介。
この場合だけ、他の周期とは異なる箇所で利用する可能性がある。
0 1 2 3 4 5 6 7 8 9
4 4 4 3 1 1 5 2 2 1
ループ中の周期 x x o o x o
Fi=6 の場合の利用 x x o
初めて好みの料理が提供される日でリセットされて、それ以降は軌道に乗る。 なので、初めての好みがいつか、というのを求められるようにしておきたい。
料理毎に以下のデータを持っておけばよい。
- $S_i$: 1周期の内、$i$ 番目の好みの料理が何日目に提供されるか
- $U_i$: 1周期の $i$ 番目の好みを食べるには、周期の最初から数えて何回の利用が必要か
- 「前回の利用から」何回の利用が必要かをまず求めて、累積和を取る
i 0 1 2 3 4 5 6 7 8 9
----------------------
4 4 4 3 1 1 5 2 2 1
x x o o x o
S: [4, 5, 9]
U: [3, 4, 6]
ここから最初の周期の利用回数を得るには、
Fi = 6
まず、好みに1周目でありつけない場合は、"0周目"から始まったとし、Fi ← Fi - D としておく。
S: [4, 5, 9] Sから二分探索で Fi を探し、初めて好みを食べる日を得る
~
idx=2
Fi と S[idx] の差から初めて好みを食べるまでに利用する回数 g を計算（今回は2）
g = (S[idx] - Fi - 1) // 2 + 1
※初回利用が好みの料理、つまりFi=S[idx]の場合、
Pythonでは -1//2 = -1 になるのでよいが、適宜 g=0 になるように調整する
もし Ti < g なら、好みを食べるまで行き着かないので答えは0
初めて好みを食べて、g+1 回目の利用（残り Ti-g-1 回）
周期の最後の好みまで利用するための追加必要回数 q を計算（今回は0）
q = (1周期の総利用回数: U[-1]) - U[idx]
もし Ti-g-1 <= q なら、1周期目で終了するので、
U から U[idx]+Ti-g-1 を二分探索して、何回目の料理まで食べられるかを得て、答えとする
1周期目で好みを食べた回数: len(S) - idx
残り利用回数: Ti-g-1-q → ループ部分の計算に引き継ぐ
最後の周期
$U$ から残り利用回数を二分探索して、何回目の好みまで食べられるかを得る。
3つの合計が、答えとなる。
周期性のあるものに対して、「最初」「最後」「その間」に分けて考えるとよいのは、たまにある。
事前計算に $O(D)$、社員毎のクエリに計 $O(N \log{D})$ かかる。
ダブリングでも解けたらしい。そちらの方が、問題依存な部分が少なく、パターン化して実装できたりするのだろうか。
