第二回 アルゴリズム実技検定 M問題メモ

M - Cafeteria(食堂)

問題

  • ある食堂では、$D$ 日周期で $C_1,C_2,\ldots,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})$ かかる。

ダブリングでも解けたらしい。そちらの方が、問題依存な部分が少なく、パターン化して実装できたりするのだろうか。

programming_algorithm/contest_history/atcoder/2020/0418_past202004.txt · 最終更新: 2020/05/05 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0