Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

Pythonでmod7占い (paizaランク S 相当)を解く

More than 1 year has passed since last update.

初めに

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)

ダメな解答コードその2

上記と同じ理由でダメです。

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つの値を選ぶ組み合わせは7*7*7 = 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)

参考

https://www.slideshare.net/paiza_official/mod7-note

まとめ

いろいろ試行錯誤した結果、かなりシンブルになったので一人で感動してました。
今はこの感動を誰かに伝えられる語彙力と解説力が欲しいです。

rA9-S
pythonで機械学習を勉強しています。まずは備忘録として使用していこうかと思います。 初心者ですので何か間違っているところがあれば優しく教えて下さるとありがたいです。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away