【Python3】mod7占い (paizaランク S 相当)：アルゴリズム付きの解説

まず、問題の要件を詳しく分析し、アルゴリズムを設計します。

要件分析

問題の概要:

• 与えられたカードの整数から、異なる3枚を選んでその和が7で割り切れる組み合わせの数を求める。

入力:

• 最初の行にカードの枚数 N が与えられる。
• 次の N 行に各カードの整数が与えられる。

出力:

• 和が7で割り切れる3つの異なるカードの組み合わせの数を一行で出力する。

アルゴリズム設計

1. 入力の読み取りと初期化

   • N を読み取る。
   • カードの整数をリスト a に格納する。

2. カードの整数の分類

   • 各整数を7で割った余りを計算し、余りごとにカウントするリスト a_mod を作成する。a_mod[i] は余りが i である整数の個数を表す。

3. 組み合わせの列挙

   • 余りが (i, j, k) で、その和が7で割り切れるすべての組み合わせを列挙する。

4. 組み合わせの数え上げ

   • 各組み合わせに対して、条件に従って組み合わせの数を計算する。
   • 特殊なケース (例えば、i == j == k) などを考慮して計算する。

擬似コード

擬似コードのステップ:

ステップ1: 入力の読み取りと初期化

n = int(input())
a = [int(input()) for _ in range(n)]

ステップ2: カードの整数の分類

a_mod = [0] * 7
for num in a:
    a_mod[num % 7] += 1

ステップ3: 組み合わせの列挙

mod7_combinations = []
for i in range(7):
    for j in range(i, 7):
        for k in range(j, 7):
            if (i + j + k) % 7 == 0:
                mod7_combinations.append((i, j, k))

ステップ4: 組み合わせの数え上げ

ans = 0
for comb in mod7_combinations:
    i, j, k = comb
    if i == j == k:
        ans += a_mod[i] * (a_mod[i] - 1) * (a_mod[i] - 2) // 6
    elif i == j:
        ans += a_mod[i] * (a_mod[i] - 1) // 2 * a_mod[k]
    elif j == k:
        ans += a_mod[i] * a_mod[j] * (a_mod[j] - 1) // 2
    elif k == i:
        ans += a_mod[i] * a_mod[j] * (a_mod[k] - 1) // 2
    else:
        ans += a_mod[i] * a_mod[j] * a_mod[k]

完成したコード

以下に完成したPythonコードを示します。

# utf-8
n = int(input())

a = [0] * 7
for _ in range(n):
    a[int(input()) % 7] += 1

mod7 = []
for i in range(7):
    for j in range(i, 7):
        for k in range(j, 7):
            if (i + j + k) % 7 == 0:
                mod7.append((i, j, k))

ans = 0
for group in mod7:
    i, j, k = group
    if i == j == k:
        ans += a[i] * (a[i] - 1) * (a[i] - 2) // 6
    elif i == j:
        ans += a[i] * (a[i] - 1) * a[k] // 2
    elif j == k:
        ans += a[i] * a[j] * (a[j] - 1) // 2
    elif k == i:
        ans += (a[k] - 1) * a[j] * a[k] // 2
    else:
        ans += a[i] * a[j] * a[k]

print(ans)

結論

このアルゴリズムは、各カードの整数を7で割った余りを使って、和が7で割り切れる3つの異なるカードの組み合わせを効率的に数え上げます。各組み合わせに対する処理を最適化し、大規模な入力に対しても適切に動作するように設計されています。