mod7占い (paizaランク S 相当)：Python3解答例

mod7占い (paizaランク S 相当)

背景

あなたは今、「mod7占い」というサービスを始めようと考えています。

mod7占いとは、整数が書かれた複数のカードの中から3枚を選び、そこに書かれた整数の和が7で割り切れるかどうかで運勢を決めようというものです。 カードは必ず異なる3枚を選ぶ必要があり、全てのカードには全て異なる数字が書かれています。

占いというからには、7で割り切れる組み合わせはそれなりに少なくする必要があります。 そこで、適当な複数のカードに対して、カードに書かれた3つの整数を足した和が7で割り切れるような組合せがいくつあるかを計算するプログラムを作成してください。

このPythonコードは、与えられた整数のカードから3枚を選び、その和が7で割り切れる組み合わせの数を効率的に計算するためのものです。
この問題では、与えられた整数のカードから3枚を選び、その和が7で割り切れるような組み合わせの数を求めます。組み合わせを求めるためには、全ての可能な組み合わせをチェックして、その和が7で割り切れるかどうかを判定します。

解法の詳細

1. カードの残りの計算:

   • まず、カードの各値を7で割った余り（mod 7）を計算し、その結果の数をカウントします。
   • 配列 a を使用して、各余りごとのカードの数を記録します。a[0] から a[6] までが、それぞれの余りごとのカウントになります。

2. 和が7で割り切れる組み合わせを列挙:

   • 7つの余り（0から6まで）の中から3つの余りの組み合わせを列挙します。3つの余りの和が7で割り切れるものだけを選びます。

3. 組み合わせの計算:

   • 列挙された組み合わせ（i, j, k）に対して、それぞれのパターンに応じた組み合わせ数を計算します。
   • 以下のような場合分けで計算します：
     • i == j == k: 3つの余りがすべて同じ場合。
     • i == j または j == k または k == i: 2つの余りが同じで、1つが異なる場合。
     • i, j, k がすべて異なる場合。

コードの説明

n = int(input())

# 各余りごとのカード数をカウント
a = [0] * 7
for _ in range(n):
    a[int(input()) % 7] += 1

# 和が7で割り切れる余りの組み合わせを見つける
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:
        # 2つの余りが同じ場合の組み合わせ数
        ans += a[i] * (a[i] - 1) * a[k] // 2
    elif j == k:
        # 2つの余りが同じ場合の組み合わせ数
        ans += a[i] * a[j] * (a[j] - 1) // 2
    elif k == i:
        # 2つの余りが同じ場合の組み合わせ数
        ans += (a[k] - 1) * a[j] * a[k] // 2
    else:
        # 全ての余りが異なる場合の組み合わせ数
        ans += a[i] * a[j] * a[k]

# 結果の出力
print(ans)

例の解説

例えば、入力が以下の場合：

5
1
2
3
4
5

ステップバイステップの説明

1. 余りのカウント:

   • 1 % 7 = 1
   • 2 % 7 = 2
   • 3 % 7 = 3
   • 4 % 7 = 4
   • 5 % 7 = 5
   • すべての余りの数をカウントすると、a = [0, 1, 1, 1, 1, 1, 0]

2. 和が7で割り切れる組み合わせを見つける:

   • (1, 2, 4) は 1 + 2 + 4 = 7 で割り切れます。
   • (2, 3, 2) などの他の組み合わせも同様に計算されます。

3. 組み合わせの計算:

   • (1, 2, 4) のような組み合わせが一つ見つかり、その組み合わせは1つだけです。

4. 出力:

   • 結果は 1 です。

まとめ

このコードは、与えられた整数リストの中から3枚を選び、その和が7で割り切れる組み合わせの数を効率的に計算します。余りを計算してカウントすることで効率的な実装を実現しています。

他の解法の考え方

1. 入力の読み取り:

   • 最初の行にカードの枚数 N が与えられます。
   • 次の N 行には各カードに書かれた整数が1行ずつ与えられます。

2. 3枚のカードを選ぶ全ての組み合わせを生成:

   • Pythonのitertoolsモジュールのcombinations関数を使用して、全ての3枚組み合わせを生成します。

3. 和が7で割り切れるかを判定:

   • 各組み合わせの和を計算し、それが7で割り切れるか（sum % 7 == 0）を判定します。

4. 条件を満たす組み合わせのカウント:

   • 条件を満たす組み合わせの数をカウントします。

実装

以下にPythonでの実装例を示します：

from itertools import combinations

# 入力の読み込み
import sys
input = sys.stdin.read
data = input().splitlines()

# カードの枚数
N = int(data[0])

# カードの整数リスト
cards = list(map(int, data[1:]))

# 組み合わせの数をカウントする変数
count = 0

# 3枚のカードを選ぶ全ての組み合わせについてチェック
for comb in combinations(cards, 3):
    if sum(comb) % 7 == 0:
        count += 1

# 結果の出力
print(count)

サンプル入力と出力

例えば、以下の入力が与えられた場合：

5
1
2
3
4
5

プログラムの出力は以下のようになります：

1

この場合の説明

• 全ての3枚組み合わせは (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5) です。
• 和が7で割り切れるのは (2, 3, 5) のみで、その和は 2 + 3 + 5 = 10 で、10は7で割ると余りが0になります。
• よって、出力は 1 です。

このコードは効率的にすべての組み合わせを探索し、和が7で割り切れる条件を満たす組み合わせの数をカウントします。itertools.combinationsを使用することで、簡潔で読みやすいコードになっています。