持っている寿司のリストLと種類ごとの寿司の個数Cを用意する
- おいしさの高い順にソートする
- 寿司を順番に見ていく。
- すでに持っている寿司がK皿であるなら、
- すでにその種類の寿司を持っているなら無視する。(K皿でない場合は無視してはいけない。)
- Lを後ろから見ていき(j)、C[L[j][種類]]>1となっているものを探す。L[j]を取り除く。C[L[j][種類]]を1減らす。
- 見ている寿司をLに加える
このとき、「後ろから見てい」くインデックスjを最初にK-1で初期化したあとは初期化しないようにする。こうすることで、Lの各要素はたかだか1回しか舐められないことになり、十分高速となる。 なおjが0未満になったら「順番に見ていく」こと自体を打ち切ることでプログラムが簡潔になる。
最初以外初期化が必要ないのは、あとから追加された寿司を取り除くことは絶対にないからである。