初めに
paizaスキルチェック基本問題を解いていたのですが、模範解答がなかったので自分で作ってみました。
言語はPython3です。
問題
Paizaの練習問題 mod7占い (paizaランク S 相当)
https://paiza.jp/works/mondai/skillcheck_sample/mod7?language_uid=python3
ログインしないと問題文が見れませんでした。
登録は無料ですぐにできるので、とりあえず登録してみることをおススメします。
ダメな解答コード
- 三重ループ
- 計算量: O(n^3)
- 大規模データではタイムオーバーで失敗してしまいます。
mod7_v1.py
n = int(input())
cards = [int(input())%7 for i in range(n)]
total = 0
for n1 in range(len(cards)):
for n2 in range(n1+1,len(cards)):
for n3 in range(n2+1, len(cards)):
if (cards[n1]+cards[n2]+cards[n3])%7==0:
total+=1
print(total)
ダメな解答コードその２
上記と同じ理由でダメです。
mod7_v2.py
import itertools
n = int(input())
cards = [int(input())%7 for i in range(n)]
total = 0
for num_set in itertools.combinations(cards, 3):
if sum(num_set)%7==0:
total += 1
print(total)
解答コード
- 足す前に剰余を取っても、結果は同じ
- (A+B+C)%7 は、(A%7 + B%7 + C%7)%7 と等しい
- 0~6の値のみ与えられたと考えてよい。
- 3つの値を選ぶ組み合わせは777 = 343
mod7.py
n = int(input())
cards = [int(input())%7 for i in range(n)]
total = 0
for n1 in range(7):
for n2 in range(7):
for n3 in range(7):
if (n1 + n2 + n3) %7 == 0:
c1 = cards.count(n1)
c2 = cards.count(n2)
c3 = cards.count(n3)
if n2 == n1:
c2 -= 1
if n3 == n1:
c3 -= 1
if n3 == n2:
c3 -= 1
pat = c1*c2*c3
total += pat
print(total//6)
参考
まとめ
いろいろ試行錯誤した結果、かなりシンブルになったので一人で感動してました。
今はこの感動を誰かに伝えられる語彙力と解説力が欲しいです。