2011-11-14

プログラミングコンテストチャレンジブックをPythonで書く

プログラミングコンテストチャレンジブックっていう本があります。これがけっこう面白くて、具体的な問題を解決する方法を考えるの脳の訓練になります。

プログラミングコンテストチャレンジブック

プログラミングコンテストチャレンジブック

解答はC++で書かれているので、それをPythonで書くとどうなるのかを考えながらコツコツやってます。

とりあえず、最初の問題をやってみました。

問題はこんな感じです。

[問題]

数字が書かれたn枚の紙切れが袋に入っています。この袋から紙切れを取り出し、数字を見て袋に戻します。これを4回繰り返して、数字の和がmになっていれば勝ちです。このゲームで、紙切れに書かれている数字がk[1],k[2],k[3]......である時、和がmになり本当に勝てる可能性があるのか調べなさい。勝つ可能性があるならYES、なければNOを出力する。

[制約]
1≦n≦50
1≦m≦10**8
1≦k[i]≦10**8

ということで、書いたのがこれ。この問題解くのに1時間以上かかったよ。


#!/usr/bin/env python
#-*- encoding: utf-8 -*-
m = int(raw_input('the sum: '))
n = int(raw_input('the number of cards: '))
k = [0] * n

for num in range(n):
    k[num] = int(raw_input('%s: ' % num))

def check():
    for a in range(n):
        for b in range(n):
            for c in range(n):
                for d in range(n):
                    if k[a] + k[b] + k[c] + k[d] == m:
                        return 'YES'

f = check()
if not f:
    f = 'NO'
print f

4重ループの所で、1つでもマッチした場合に、全てのループを抜ける方法が分からなくて、関数にしてreturnで処理しました。breakだと上の階層のループまで抜けられない。

もっといい書き方があると思うので、どんどんコメントもらえれば嬉しいです。

2 件のコメント:

ひよこ3分07秒 さんのコメント...

https://gist.github.com/1389044
試してないのでちゃんと出来てるかわかりませんがこれでどうでしょう。

Minoru Monji さんのコメント...

ひよこ3分07秒さんへ

コメントありがとうございます。

itertoolsっていうのを初めて知りました。まだまだプログラミングの勉強を始めたばかりで未熟者です。

itertoolsの使い方を勉強しようと思います。ありがとうございました。

コメントを投稿