2
0

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

要件分析

問題の概要:

  • 与えられたカードの整数から、異なる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つの異なるカードの組み合わせを効率的に数え上げます。各組み合わせに対する処理を最適化し、大規模な入力に対しても適切に動作するように設計されています。

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
0