質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.76%

  • Python

    6872questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    5325questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • Python 2.7

    1205questions

    Python 2.7は2.xシリーズでは最後のメジャーバージョンです。Python3.1にある機能の多くが含まれています。

競技プログラミングの問題(Python)_2

解決済

回答 9

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 535

super_tomato

score 26

下記のサイトの競技プログラミングの問題を解きました。
競技プログラミングの問題
簡単に説明すると、標準入力から2つの値(n,x)を受け取り、1~nから3つの値を取り出し総和がxとなる組み合わせの数を出力せよ。という問題です。
もしお時間があれば、この問題のプログラムを作成していただきぜひ参考にさせていただきたいです。
下記が僕が作成したプログラムです。多くの改善点があると思うので、改善するべきところを指摘していただくだけでも構いません。

while(1):
    comb = []
    count =0
    inp = raw_input().split(" ")
    if inp[0] == "0" and inp[1] == "0":
        break
    for i in range(1,int(inp[0])+1):
        for j in range(1,int(inp[0])+1):
            if i == j:
                break
            sum = i + j
            if sum > int(inp[1]):
                j = int(inp[0])
                break
            for k in range(1,int(inp[0])+1):
                if i == j or i == k or j == k:
                    break
                sum = i + j + k
                if sum > int(inp[1]):
                    k = int(inp[0])
                    break
                if sum == int(inp[1]):
                    if not ([i,j,k] in comb or [i,k,j] in comb or [j,k,i] in comb or [j,i,k] in comb or [k,i,j]  in comb or [k,j,i] in comb):
                        comb.append([i,j,k])
                        count += 1
    print count


以上よろしくお願いします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 9

+7

競プロに適しているか分かりませんが、ジェネレータ関数を使ってみました。
最終的にリストにするので、可読性が若干上がる他はただの自己満足ですが。

from itertools import combinations

def gen_ans(n, x):
    loop_obj = combinations(range(1, n+1), 3)
    for nums in loop_obj:
        if sum(nums) == x: yield nums

while True:
    n, x = map(int, input().split())
    if n == 0 and x == 0:
        break

    print(
        len(list(gen_ans(n, x)))
    )

Python3.6です。Wandbox

追記:実行時間に関して

簡単に計測してみました。Wandbox
リンク先は敬称略、実行順序は投稿順です。また、一部書き換えているところもあります。
計測は割と適当に書いているので、何か間違いがあればお知らせください。

結果を見ると、次のような分析が出来そうです。(こちらは速度順です)

名前 実行時間 combination 枝切り
can110さん .10670 している
makiさん .12985 している
mkgreiさん .89056 使っている している
louis0616 8.22139 使っている
namnium1125さん 8.73007 使っている

kanamarimoさんの回答を含め再計測してみました。
Wandboxでもnumpyが使えないようなので、手元のWin10環境です。

名前 実行時間
can110さん .10939
makiさん .10939
kanamarimoさん .17924
mkgreiさん .77519
louis0616 7.57757
namnium1125さん 7.93294

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/23 17:49

    listにしてlenを取るより、mkgreiさんのように1のsumを取った方が良かったかも。

    キャンセル

  • 2018/01/23 17:49

    lenもいけますね。
    sumとどっちが早いのでしょう。

    キャンセル

  • 2018/01/23 18:04 編集

    適当な計測ですけど、あんまり変わらないような気がします。
    >>> timeit('len(list(gen))', setup='gen = (i for i in range(1000))')
    0.3977314133333465
    >>> timeit('sum(1 for _ in gen)', setup='gen = (i for i in range(1000))')
    0.3992119466666679

    あ、CPythonです。

    キャンセル

  • 2018/01/23 18:37

    わざわざ検証していただきありがとうございます。
    誤差の範囲ですが、わずかにlenの方が早いですね。

    キャンセル

  • 2018/01/23 19:12

    can110さんとmakiさんのコード速いですよね。
    combinationを使わないことで枝切りが一層優れています。

    キャンセル

  • 2018/01/23 19:35

    単純な問題は単純に解くのが一番なのでしょうね。
    どこまで単純化出来るか、というのは簡単ではないですが...

    キャンセル

  • 2018/01/23 21:34 編集

    実行時間自体はkanamarimoさんが最速です。

    競技プログラミングではnumpyを使うのは結構悩みどころです。
    計算自体は早いのですが、importに0.1秒ほど持って行かれます…
    これのせいでしょうね…

    もう少し大きなテストデータを使うとnumpy+DPのほうが圧倒的に速いです。

    キャンセル

  • 2018/01/23 21:49 編集

    インポートが計測に含まれないように書いているので、numpyのインポート分は影響していないかと。
    https://wandbox.org/permlink/g294aSkVlJZXj7Oj
    リンク先ではモジュールエラーで確認できませんが。

    それとも計測の仕方に何か問題があるのでしょうか?

    ---
    毎回多少のばらつきはありますが、次の順序は変わりませんでした。
    can110さん, makiさん < kanamarimoさん < mkgreiさん < 私, namnium1125さん

    キャンセル

  • 2018/01/23 21:51

    itertoolsというライブラリーの存在を知りませんでしたので勉強になりました。実行時間の検証もしていただいてありがとうございました。とても参考になります!
    ご回答ありがとうございました。

    キャンセル

  • 2018/01/23 21:59

    理解しました。
    can110さんのテストデータでは以下のようになります。

    can110さんのコード:
    9.059906005859375e-06
    0.0006868839263916016
    0.09459686279296875
    8.535820960998535

    karamarimoさんのコード:
    9.608268737792969e-05
    0.0005450248718261719
    0.0186159610748291
    1.536841869354248

    データセットににも依存しますが、数字が小さいうちは配列初期化などでDPが若干遅くなることがあります。
    今回の設定では
    3 ≤ n ≤ 100
    0 ≤ x ≤ 300
    なので、ほぼいつも素直にやったほうが速いです。

    キャンセル

  • 2018/01/23 21:59

    検証ありがとうございます。
    今回の問題であれば単純な解法が強いですが、3個固定ではなく相異なるm個の計だと
    DPなりメモ化+再帰のほうが速度もプログラムの組みやすさも有利になるかな~と思います。

    キャンセル

  • 2018/01/23 22:24

    柔軟性と言う点では、やはり動的計画法に分があるということですね。
    勉強しないとなぁと改めて思いました。

    キャンセル

checkベストアンサー

+6

リスト内包表記を用いた書き方を推奨して速度的に優れているとおっしゃっている方がいるのですが
リスト作成上必ずしも最適ではないということを言わせていただきたい。

今回は関数のみを作成いたしました

def get_ans(n, x):                                                                                                                                                                                            
    """1 から n までの数の中から、重複無しで3つの数を選び                                                                                                                                                         
    それらの合計が x となる組み合わせの数を求める                                                                                                                                                                  

    プログラム中でi, j, kをそれぞれの組み合わせとして扱う                                                                                                                                                          

    Args:                                                                                                                                                                                                          
        n: Integer 扱える数の最大値                                                                                                                                                                                
        x: Integer 3つの数の目標合計数                                                                                                                                                                             

    Returns:                                                                                                                                                                                                       
        cnt: Integer 条件に一致する組み合わせ数                                                                                                                                                                    
    """                                                                                                                                                                                                            

    cnt = 0                                                                                                                                                                                                        

    # 小さな数から範囲を定める                                                                                                                                                                                     
    # n-2までをiの調査範囲としているのは、j以降で調査対象となるため                                                                                                                                                
    # これは重複調査を防ぐために実施しています                                                                                                                                                                     
    for i in range(1, n-1):                                                                                                                                                                                        
        # iは最小の数1から順に調査するため、jはi+1 ~ n-1までを調べればよい                                                                                                                                         
        for j in range(i+1, n):                                                                                                                                                                                    
            # i, jが与えられたため、残るkの条件を判定する                                                                                                                                                          
            k = x - i - j                                                                                                                                                                                          
            if j < k <= n:                                                                                                                                                                                         
                cnt += 1                                                                                                                                                                                           
    return cnt

ipythonによる簡易的な実行時間計測

# mkgrei様 python的最適化の方を利用させていただきました。

In [31]: %time get_ans(123, 456)
CPU times: user 61.9 ms, sys: 0 ns, total: 61.9 ms
Wall time: 62.6 ms
Out[31]: 0

In [32]: %time get_ans(345, 678)
CPU times: user 1.43 s, sys: 0 ns, total: 1.43 s
Wall time: 1.43 s
Out[32]: 10579

# LouiS0616様
In [34]: %time get_ans(123, 456)
CPU times: user 64.3 ms, sys: 0 ns, total: 64.3 ms
Wall time: 64.7 ms
Out[34]: 0

In [35]: %time get_ans(345, 678)
CPU times: user 1.44 s, sys: 7.3 ms, total: 1.45 s
Wall time: 1.57 s
Out[35]: 10579

# 私が作成したもの
In [37]: %time get_ans(123, 456)
CPU times: user 731 µs, sys: 0 ns, total: 731 µs
Wall time: 735 µs
Out[37]: 0

In [38]: %time get_ans(345, 678)
CPU times: user 7.29 ms, sys: 1 µs, total: 7.29 ms
Wall time: 7.45 ms
Out[38]: 10579

なぜこうなるかと申しますと、リストを作成するコストを使っていないからです。
リスト内包表記はたしかに速いですが、リスト内包表記を使えば必ずしも速くなるというのは誤りです。

 追記

皆様の回答出力用関数名がget_ansとなっていたため、わかりやすいよう。同じ関数名にしました。
def get_pair_cnt(n, x): -> def get_ans(n, x):

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/23 18:27

    確かに全く検証せず断言的に書いてしまったかもしれません。申し訳ありません。m(_ _)m

    同時にcombinations無しの解法を載せておられて脱帽です。(^ ^;

    キャンセル

  • 2018/01/23 18:44 編集

    そうなんですよね。
    このような単純なケースだとfor文まわしても内包表記でやっても変わらないです。
    (http://shkh.hatenablog.com/entry/2013/01/04/181805)

    私のコードでは上の2つは3重ループを回しているのと同じですので、すごく遅いです。
    makiさんのコードは私の最後のコードと同じで2重ループです。

    このような単純なケースでは内包表記は1行で書ける自己満足でしかないのです。
    とほほ。

    キャンセル

  • 2018/01/23 19:38 編集

    記事のタイトルからdisられるのかなと思ったらそうでもないんですね(^ ^;
    (そういう意味じゃないのはわかっています)

    確かに自己満ですね。ただネストとか重ねなければ個人的には可読性は大して変わらないと思います。

    appendを使うシーンがあればなるべくmapか内包表記を検討してみるという感じでしょうか?

    キャンセル

  • 2018/01/23 19:52 編集

    @namnium1125 さん
    入力部分は次のように書くと高速化が期待できるかもしれませんね。
    import sys
    inputs = [
    __[e for e in map(int, row.split())] for row
    __in sys.stdin.readlines()
    ][:-1]
    註:空白をアンダーバーで代替しています。

    キャンセル

  • 2018/01/23 20:09

    確かに私自身が繰り返しでappend使ってますもんね…(コメントをもらって気づきました)、両方0という条件に囚われたかもしれません。

    ちょっと改良したものを載せてみます。

    キャンセル

  • 2018/01/23 21:47

    個人的に分かりやすいコードで実行時間の検証もしていただいてありがとうございました!コードを改良するのに一番参考にさせていただいたのでベストアンサーとさせていただきました。
    ご回答ありがとうございました。

    キャンセル

+6

まず、基本的なこととして

  • 説明コメントを書きましょう。コードだけだと他人には何をしているのか分かりにくいです。書いた本人でも後で何をしているのか分からなくなることがあります。
    とくに、後半のif文、長くて何をしているのか分かりにくいので、何をしているのか?というコメントを書きましょう。

  • 変数名は分かりやすいものをつけましょう。たとえばinp[0]よりも問題文で使われているnの方が分かりやすいです。

  • intへの変換は最初に行いましょう。各処理中に何度もint(~)とするのは無駄です。

次に、ロジックについてですが
各値の取りうる範囲に条件がないか(探索範囲を絞れないか)?を考えるようにしましょう。
たとえば題意より解が存在するのはn3以上、x6以上かつn + n-1 + n-2以下であることが明らかです(理由は考えてみましょう)

また、重複なしの3つの数をs1,s2,s3とすると、その取り出す順番は不問なのでs1 > s2 > s3という条件を設けることができます。これらの条件により、ループ範囲の削減と重複チェックそのものが不要になります。

最後に。
あるs1s2が決まった場合、s1+s2+s3=xを満たすs3は1つに決まるので…

def gen_ans1(n,x):
    for s1 in reversed(range( 3, n+1)):
        for s2 in reversed(range( 2, s1)):
            s3 = x - (s1 + s2)
            if s3 >= 1 and s3 < s2: # 制約条件
                yield (s1,s2,s3)

for (n,x) in [(5,9),(100,123),(1000,1234),(10000,12345)]:
    ret = list(gen_ans1(n,x))
    print(n,x,len(ret))


さすがにn=10000くらいだと時間かかりますね…

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/23 21:58

    ごもっともなご指摘ありがとうございました。人に見せることを意識せず質問にコードを載せていました...とてもお恥ずかしいです...。今後気を付けていこうと思います。数学的に考えると簡潔なコードにすることができますね!とても勉強になりました。
    ご回答ありがとうございました。

    キャンセル

  • 2018/01/23 22:06

    「改善するべきところを指摘」という質問でしたので、思ったことをそのまま回答しました。
    が、私自身のコードの書き方に対する自戒も含まれます。適切な命名とコメント、なかなかできないんですよね…

    キャンセル

+3

満たさないものを弾くのではなく、数え上げた方が探索空間が少ないです。
(nC3とn^3どっちが大きいのかという話です。)

たとえば、
https://docs.python.jp/3/library/itertools.html#itertools.combinations
コンビネーションを使えば、3つの数字が同じになるものは探索しなくてすみます。
(実際は探索空間が6分の1くらいに減るのですが)

それとinp[0]>inp[1]は探索しなくて良いはずです。


たとえばこんなやつ。

from itertools import combinations as comb
def get_ans(m, n):
    ans = 0
    for nums in comb(list(range(1, min(m+1,n-2))), 3):
        if sum(nums) == n:
            ans += 1
    print(ans)

while True:
    m, n = (int(x) for x in input().split())
    if m==0 and n==0:
        quit()
    get_ans(m, n)

python的最適化。

from itertools import combinations as comb
def get_ans(m, n):
    ans = sum(1 for nums in comb(range(1, min(m+1,n-2)), 3) if sum(nums)==n)
    return ans

while True:
    m, n = (int(x) for x in input().split())
    if m==0 and n==0:
        quit()
    ans = get_ans(m, n)
    print(ans)

大変遅かったのでnC2にすることにしました。
可読性は落ちましたが、m倍早くなりました。
たぶんね。

from itertools import combinations as comb
def get_ans(m, n):
    ans = sum(1 for nums in comb(range(1, min(m+1,n-2)), 2) if ((n-sum(nums)>0) and (n-sum(nums)>max(nums)) and (n-sum(nums)<=m)))
    return ans

while True:
    m, n = (int(x) for x in input().split())
    if m==0 and n==0:
        quit()
    ans = get_ans(m, n)
    print(ans)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/23 17:27 編集

    rangeオブジェクトをリストに直す必要はないんじゃないかな、と思いました。

    キャンセル

  • 2018/01/23 17:29

    必要なかったですね。
    最適化したコードに反映しておきます。

    キャンセル

  • 2018/01/23 22:01

    conbinations関数という便利な関数があったんですね。勉強になりました!
    なんどもコードを更新していただいてありがとうございました!とても勉強になります。
    ご回答ありがとうございました。

    キャンセル

+3

処理的には比較的分かりやすいですが、速さを求めるのであれば、
j1からではなくてi+1から始めて問題ないです。
そうするとi == jの分岐も不要になります。
同じようにkj+1から始めると次の分岐と最後の分岐も必要なくなります。
iが一番小さい数字でkが一番大きい数字という前提が出来るので、
数字の前後関係を見る必要がなくなるからです。

また3n-3 < xの場合、解が出ないのでループさせません。
(n-3から連続する3つの和よりxのほうが大きい、同じようにxが4以下ならループの必要ないですね)

結構修正が必要ですが、1からインクリメントするよりnからデクリメントしたほうが、
おそらく多くのケースでbreakの条件に早く到達するので、
そちらのほうがいいかなぁ。

といったところです。
Python書いたことないのでコメントだけです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/23 21:54

    まず数学的に考えることはとても大事ですね!僕は惰性でコードを書いてしまって複雑なコードになってしまうことが多いので、とても勉強になりました。
    ご回答ありがとうございました。

    キャンセル

+3

そのサイトではnumpyが使えないですが、試しにnumpyのarrayを用いて動的計画法で解くプログラムを作ってみました。

import numpy as np

def countCombinationsNumpy(n, x, size=3):
    dp = np.zeros((x + 1, size + 1), dtype=int)
    dp[0, 0] = 1
    for i in range(1, n + 1):
        dp[i:, 1:] += dp[:-i, :-1]
    return dp[-1, -1]

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/23 21:45

    ご回答ありがとうございます!動的計画法ですか!まだコードを理解できていませんが勉強になります!

    キャンセル

  • 2018/01/23 22:34

    dp[j][k]は、「k 個選んで合計 j になる組み合わせが何通りあるか」を表しています。
    使える数字が「1から i までの数字」で、この i を1つずつ増やしていきます。
    最初は使える数字が1つもないので、0個選んで合計0になる方法が1通りのみで、他は全部0通りです。
    for loop のところは dp の表を紙にでも書いてみるとご理解いただけると思います(というか文字で説明するのが難しいので端折ってますすみません)。

    キャンセル

  • 2018/01/23 22:54 編集

    ポイントは、「1から i までの数字で k 個選んで合計 j になる」には、「1から (i-1) までの数字で k 個選んで合計 j になる」か「1から (i-1) までの数字で k-1 個選んで合計 j - i にし、さらに新しく i を追加して 合計 j にする」しかないということです。なので i が使用可能になると、dp[j][k] を (dp[j][k] + dp[j-i][k-1]) に更新すればいいということになります。

    キャンセル

  • 2018/01/24 09:44 編集

    追加の解説ありがとうございます。すみません、動的計画法について勉強不足で理解ができないところがあります...。「dp[i:, 1:] += dp[:-i, :-1]」この部分がいまいち理解できないのですがもしよろしければ解説をお願いします。m(__)m

    キャンセル

  • 2018/01/24 10:06 編集

    「1から i までの数字で k 個選んで合計 j にする方法の数」は「1から (i-1) までの数字で k 個選んで合計 j にする方法の数」と「1から (i-1) までの数字で k-1 個選んで合計 j - i にする方法の数」の和で計算できることは分かりますか?なので、数字 i が使用可能になって更新された後の dp を dp' とすると、
    dp'[j][k] = dp[j][k]+dp[j-i][k-1]
    になります(dp[j-i][k-1] はインデックスが範囲外なら 0 とみなす)。

    キャンセル

  • 2018/01/24 10:13

    ありがとうございます。理解できました。
    すみません、karamarioさんのコメントを読む前にコメントを編集してしまったのですが、
    コードの「dp[i:, 1:] += dp[:-i, :-1]」の部分が理解できないのですが解説お願いできますか?

    キャンセル

  • 2018/01/24 10:24 編集

    dp'[j][k] = dp[j][k]+dp[j-i][k-1]
    なので dp[j-i][k-1] だけ増やせばいいということになります。
    これを dp 行列全体でやろうとすると、dp を (i, 1) だけ右下にずらしたものを元の dp に足し合わせることでできます。
    紙に書いてみると分かりやすいと思いますが、
    dp[i:, 1:] は dp の (i, 1) から右下までの長方形の部分です。
    dp[:-i, :-1] は dp から下 i 行と右 1 列を削ぎ落としたものです。
    なので、dp[i:, 1:] += dp[:-i, :-1] とすれば、 dp を (i, 1) だけ右下にずらしたものが足し合わされることになります。

    キャンセル

  • 2018/01/24 11:06

    詳しい解説ありがとうございます。そもそもdp[j][k]はどのように決まるのかと思ったのですが、これは行列の加算を行っていく過程で求まっているということですか?

    キャンセル

  • 2018/01/24 11:32

    すみません、ご質問の意味がよく分からないのですが、
    初期値として、dpは[0][0]で1、それ以外は0 になっていますので、あとは dp[i:, 1:] += dp[:-i, :-1] で値を更新していくだけです。

    キャンセル

  • 2018/01/24 12:01

    すみません、説明不足でした。
    i行列目の処理を行うときにはすでにi行列目の値が0ではない要素はi-1以下の処理で値が入れられているのかという質問でした。更新される要素とされない要素があるので、更新されずに値が0ではない要素はもともと値が入っているのかと思ったのですが...。的外れな質問かもしれません。

    キャンセル

  • 2018/01/24 12:12

    i 行列目というのは dp[i] のことでしょうか?

    キャンセル

  • 2018/01/24 12:18 編集

    すみません、誤字ですね。i行目,dp[i]のことです。

    キャンセル

  • 2018/01/24 12:50

    dp[i:, 1:] += dp[:-i, :-1] による dp の更新が行ごとに行われると仮定すると、どの行を先に処理するかという順番によって結果が変わってしまう、ということでしょうか?実際にはそうではなく一気に加算されるのでその心配はありません。
    こう書いたほうが分かりやすいでしょうか。

    for i in range(1, n + 1):
    __dp2 = np.copy(dp) # dp のコピー
    __dp2[i:, 1:] += dp[:-i, :-1]
    __dp = dp2

    キャンセル

  • 2018/01/24 12:55

    例をあげると、dp'[5][2]=dp[5][2]+dp[0][1]のdp[5][2]はどのタイミングで値が入るのでしょう?
    dp[0][1]は0なのでこのとき更新は行われません。よってもともとdp[5][2]に入っていた値が正しい値となると思うんですが。

    キャンセル

  • 2018/01/24 13:16 編集

    「どのタイミングで値が入る」とは、0でなくなるのはいつかということでしょうか?
    もちろん dp[5][2] の初期値は 0 ですが、for loop を回るうちに値が増えていきます。
    いつ 0 でなくなるかはやってみなければ分かりません。

    ↓n=5, x=10 で dp を出力してみた結果です。
    https://pastebin.com/pzfY9b8P
    i=3が終わって初めて dp[5][2] は 1 になりました。

    > よってもともとdp[5][2]に入っていた値が正しい値となると思うんですが。

    はい、そうです。

    キャンセル

  • 2018/01/24 13:26

    そうですよね。ちょっとした確認のつもりだったのですが、お手数をおかけしました。ありがとうございました!

    キャンセル

+2

私もmkgrei様と同様にcombinationsを作って組んでみました。

from itertools import combinations

inputs = []
n,x = map(int,input().split())
while n != 0 or x != 0:
     inputs.append((n,x))
     n,x = map(int,input().split())

for n,x in inputs:
    print(len([c for c in combinations(range(1,n+1),3) if sum(c) == x]))

これで上手くパスできました。

前回もそうですけど私は入力は一気に受け取る派です。
またかっこつけで内包表記にしていますが、内包表記は速度的にも速くなる速くなることもあるそうなので競プロだとオススメかもしれません。

combinations縛りももし可能だったらトライしてみようと思います。

Python 3.6.1

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/23 21:53

    一見するとリスト内包表記のほうが速そうですが、遅くなることもあるみたいですね。勉強になりました!
    今回もご回答していただきありがとうございました。

    キャンセル

+1

つい熱くなってしまい、失礼しました。
話の本筋に戻りますと、主様のコードは失礼ながら無駄が多く感じます。
やりたいことは何となく分かるのですが、少し工夫するだけでコードもきれいになりますし、可読性も向上します。

また、複雑なコードを人に見せるときは、随所にコメントをいれていただけると、なぜそうしたのかがわかりやすいです。
これが競技プログラミングという性質上、本来コメントは不要とは思いますが、質問の際にはそうしていただけると助かります。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

コードを下記のように改良しました。自分の元のコードがいかにムダが多かったか思い知らされました...
そしてみなさんとてもありがたいご回答をしていただきありがとうございました。ベストアンサーを一人に決めるのは少し心苦しいかったのですが一番参考にさせていただいた方を選ばせてもらいました。
みなさん、本当にありがとうございました。
また競プロの問題で質問させていただくと思うので、もしお時間があれば是非またご回答宜しくお願い致します。

# coding: UTF-8
def find_comb(n,x):
    count = 0
    #探索
    for i in range(1,n-1):
        for j in range(i+1,n):
            k = x - i - j #←がi < j < k <= nを満たせばその時点で総和がxとなる
            if  j < k <= n:
                count += 1
    print count
while(1):
    n,x = map(int, raw_input().split(" "))
    if n == 0 and x == 0:
        break
    find_comb(n,x)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/23 22:17

    参考にしていただけたようで何よりです。
    他の方々が扱っているテクニックも実戦でよくあらわれるものです
    ですが、単純なものであればこのような形のものが有力かと思われます。

    私自身も各回答者の回答を見て勉強となるところがありました。
    元々数学家畑の人間だったので、学生時代を思い出しながら楽しくやらせていただきました。

    ありがとうございます。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.76%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 受付中

    ある範囲の整数の和を求めるプログラム

    1から10までの整数の和を求める簡単なプログラムを作っています。 たとえばこれをC言語で実装する場合はfor文を使うのが一般的かと思います。 しかしPythonのfor文はC言語

  • 解決済

    【Python】標準入出力におけるリスト格納について

    前提・実現したいこと ここに質問したいことを詳細に書いてください (例)PHP(CakePHP)で●●なシステムを作っています。 ■■な機能を実装中に以下のエラーメッセージが

  • 解決済

    不正解の理由が分からない(2次元配列問題)

    会津オンラインジャッジ(AOJ)にコードを提出するとWrong Answerとなってしまいます。 Pycharm上で同内容を実行してみると正解しているように見えます。 何が原因

  • 受付中

    ターミナルで実行するのに時間がかかりすぎる

    ターミナルで実行するのに時間がかかりすぎます。 画像圧縮のアルゴリズムを書いています。 N × N ピクセルのグレースケール画像があり各ピクセルの画素値は 0 から 255

  • 受付中

    バブルソートでカウントができない

    バブルソートでカウントができないです。 バブルソートを実装したいです。 num_arrayを何回入れ替えたら元の順序である[1,2,3,4,5]に戻るかをcountでカウントして出

  • 解決済

    Python 内包表記

    jupyter notebookでとある数列を求めるプログラムを作りました。 for文の中にあるfor文(for j in range(compare.size + 1)...)を

  • 解決済

    Pythonのsumよるテキストファイルの行数カウント方法の仕組みについて

    前提 sumによるテキストファイルの行数カウント方法の仕組みが知りたい お世話になります。 テキストファイルの行数をカウントしようと思い、当初は以下の方法で実装していました。

  • 解決済

    Python 数字当てゲーム

    前提・実現したいこと while文でループした数を変数loopに代入したい 発生している問題・エラーメッセージ while文でループした回数を調べる方法がわからない 該当の

同じタグがついた質問を見る

  • Python

    6872questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    5325questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • Python 2.7

    1205questions

    Python 2.7は2.xシリーズでは最後のメジャーバージョンです。Python3.1にある機能の多くが含まれています。