Pythonで好きな日に好きなキャンディーを食べられるか判定するプログラムの作り方

問題の概要

正整数からなる配列 candiesCount が与えられ、candiesCount[i] は i 番目の種類のキャンディーの在庫数を表しているとします。さらに、各要素が [favoriteType_i, favoriteDay_i, dailyCap_i] の3つの値を持つ配列 queries も与えられます。

キャンディーを食べるときは、次のルールを守らなければなりません。

• 0日目からキャンディーを食べ始めます。
• i 番目の種類のキャンディーは、それより前の i−1 種類をすべて食べ終えるまで食べられません。
• すべてのキャンディーを食べきるまで、毎日必ず1個以上のキャンディーを食べます。

これらのルールのもとで、各クエリに対する結果をブール値の配列として返します。i 番目の要素は、「favoriteDay_i 日目に、どの日にも dailyCap_i 個を超えてキャンディーを食べないという条件で、favoriteType_i のキャンディーを食べられるかどうか」を意味します。なお、ルール2を守る限り、同じ日に複数の種類のキャンディーを食べても構いません。

入力例と出力の理由

たとえば、candiesCount = [7,4,5,3,8]、queries = [[0,2,2],[4,2,4],[2,13,100]] が入力された場合、出力は [true, false, true] になります。それぞれの理由は次の通りです。

• [0,2,2]:0日目と1日目にそれぞれ2個ずつ0番目の種類のキャンディーを食べれば、2日目にも0番目の種類のキャンディーを食べられます。
• [4,2,4]:1日に最大4個までしか食べられない場合、毎日4個ずつ食べると、0日目に0番目の種類を4個、1日目に0番目の残り3個と1番目の種類を1個食べることになります。すると2日目に食べられるのは1番目と2番目の種類だけなので、2日目に4番目の種類のキャンディーを食べることはできません。
• [2,13,100]:毎日1個ずつ食べれば、13日目にちょうど2番目の種類のキャンディーを食べられます。

解き方のステップ

この問題は累積和(プレフィックスサム)を使うと効率的に解けます。手順は以下の通りです。

1. sumcandy を candiesCount[0] のみを含むリストとして初期化します。
2. index を 1 とし、index が candiesCount の長さ未満である間、sumcandy[index−1] + candiesCount[index] を sumcandy の末尾に追加し、index を1ずつ増やします。これで累積和の配列が完成します。
3. sumcandy の末尾に 0 を追加します。これにより、typ = 0 のときの sumcandy[typ−1](つまり sumcandy[-1])が 0 として扱えます。
4. res を空のリストとして用意します。
5. queries の各要素 each について、typ = each[0]、day = each[1]、cap = each[2] とします。
6. 「day + 1 > sumcandy[typ]」または「(day + 1) × cap <= sumcandy[typ−1]」が成り立つ場合は res に False を追加し、そうでなければ True を追加します。
7. 最後に res を返します。

判定条件の考え方

この条件式は次のように理解できます。

• 下限のチェック(day + 1 > sumcandy[typ]):day 日目までに最低でも day + 1 個(毎日1個ずつ)のキャンディーを食べることになります。この最小ペースでも typ 番目までのキャンディーをすべて食べ尽くしてしまうなら、day 日目に typ 番目の種類を食べることは不可能です。
• 上限のチェック((day + 1) × cap <= sumcandy[typ−1]):day 日目までに最大で (day + 1) × cap 個のキャンディーしか食べられません。最大ペースでも typ 番目より前の種類を食べ終われないなら、day 日目に typ 番目の種類に到達できません。

この2つの条件のどちらにも当てはまらない場合のみ、目的の日に目的の種類のキャンディーを食べられることになります。

実装例(Python)

理解を深めるために、以下の実装例を見てみましょう。

def solve(candiesCount, queries):
    sumcandy = [candiesCount[0]]
    index = 1
    while index < len(candiesCount):
        sumcandy.append(sumcandy[index-1] + candiesCount[index])
        index += 1
    sumcandy.append(0)
    res = []
    for each in queries:
        typ = each[0]
        day = each[1]
        cap = each[2]
        if day+1 > sumcandy[typ] or (day+1)*cap <= sumcandy[typ-1]:
            res.append(False)
        else:
            res.append(True)
    return res

candiesCount = [7,4,5,3,8]
queries = [[0,2,2],[4,2,4],[2,13,100]]
print(solve(candiesCount, queries))

入力

[7,4,5,3,8], [[0,2,2],[4,2,4],[2,13,100]]

出力

[True, False, True]