Q&A
確かに全く検証せず断言的に書いてしまったかもしれません。申し訳ありません。m(_ _)m
同時にcombinations無しの解法を載せておられて脱帽です。(^ ^;
下記のサイトの競技プログラミングの問題を解きました。
競技プログラミングの問題
簡単に説明すると、標準入力から２つの値(n,x)を受け取り、1~nから3つの値を取り出し総和がxとなる組み合わせの数を出力せよ。という問題です。
もしお時間があれば、この問題のプログラムを作成していただきぜひ参考にさせていただきたいです。
下記が僕が作成したプログラムです。多くの改善点があると思うので、改善するべきところを指摘していただくだけでも構いません。
python
1while(1): 2 comb = [] 3 count =0 4 inp = raw_input().split(" ") 5 if inp[0] == "0" and inp[1] == "0": 6 break 7 for i in range(1,int(inp[0])+1): 8 for j in range(1,int(inp[0])+1): 9 if i == j: 10 break 11 sum = i + j 12 if sum > int(inp[1]): 13 j = int(inp[0]) 14 break 15 for k in range(1,int(inp[0])+1): 16 if i == j or i == k or j == k: 17 break 18 sum = i + j + k 19 if sum > int(inp[1]): 20 k = int(inp[0]) 21 break 22 if sum == int(inp[1]): 23 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): 24 comb.append([i,j,k]) 25 count += 1 26 print count
以上よろしくお願いします。
回答9件
0
競プロに適しているか分かりませんが、ジェネレータ関数を使ってみました。
最終的にリストにするので、可読性が若干上がる他はただの自己満足ですが。
Python
1from itertools import combinations 2 3def gen_ans(n, x): 4 loop_obj = combinations(range(1, n+1), 3) 5 for nums in loop_obj: 6 if sum(nums) == x: yield nums 7 8while True: 9 n, x = map(int, input().split()) 10 if n == 0 and x == 0: 11 break 12 13 print( 14 len(list(gen_ans(n, x))) 15 )
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 08:46
編集2018/01/23 10:33
総合スコア35660
0
ベストアンサー
リスト内包表記を用いた書き方を推奨して速度的に優れているとおっしゃっている方がいるのですが
リスト作成上必ずしも最適ではないということを言わせていただきたい。
今回は関数のみを作成いたしました
python
1def get_ans(n, x): 2 """1 から n までの数の中から、重複無しで３つの数を選び 3 それらの合計が x となる組み合わせの数を求める 4 5 プログラム中でi, j, kをそれぞれの組み合わせとして扱う 6 7 Args: 8 n: Integer 扱える数の最大値 9 x: Integer 3つの数の目標合計数 10 11 Returns: 12 cnt: Integer 条件に一致する組み合わせ数 13 """ 14 15 cnt = 0 16 17 # 小さな数から範囲を定める 18 # n-2までをiの調査範囲としているのは、j以降で調査対象となるため 19 # これは重複調査を防ぐために実施しています 20 for i in range(1, n-1): 21 # iは最小の数1から順に調査するため、jはi+1 ~ n-1までを調べればよい 22 for j in range(i+1, n): 23 # i, jが与えられたため、残るkの条件を判定する 24 k = x - i - j 25 if j < k <= n: 26 cnt += 1 27 return cnt
ipythonによる簡易的な実行時間計測
python
1# mkgrei様 python的最適化の方を利用させていただきました。 2 3In [31]: %time get_ans(123, 456) 4CPU times: user 61.9 ms, sys: 0 ns, total: 61.9 ms 5Wall time: 62.6 ms 6Out[31]: 0 7 8In [32]: %time get_ans(345, 678) 9CPU times: user 1.43 s, sys: 0 ns, total: 1.43 s 10Wall time: 1.43 s 11Out[32]: 10579 12 13# LouiS0616様 14In [34]: %time get_ans(123, 456) 15CPU times: user 64.3 ms, sys: 0 ns, total: 64.3 ms 16Wall time: 64.7 ms 17Out[34]: 0 18 19In [35]: %time get_ans(345, 678) 20CPU times: user 1.44 s, sys: 7.3 ms, total: 1.45 s 21Wall time: 1.57 s 22Out[35]: 10579 23 24# 私が作成したもの 25In [37]: %time get_ans(123, 456) 26CPU times: user 731 µs, sys: 0 ns, total: 731 µs 27Wall time: 735 µs 28Out[37]: 0 29 30In [38]: %time get_ans(345, 678) 31CPU times: user 7.29 ms, sys: 1 µs, total: 7.29 ms 32Wall time: 7.45 ms 33Out[38]: 10579
なぜこうなるかと申しますと、リストを作成するコストを使っていないからです。
リスト内包表記はたしかに速いですが、リスト内包表記を使えば必ずしも速くなるというのは誤りです。
追記
皆様の回答出力用関数名がget_ansとなっていたため、わかりやすいよう。同じ関数名にしました。
def get_pair_cnt(n, x): -> def get_ans(n, x):
投稿2018/01/23 09:14
編集2018/01/23 09:34
総合スコア72
そうなんですよね。
このような単純なケースだとfor文まわしても内包表記でやっても変わらないです。
(http://shkh.hatenablog.com/entry/2013/01/04/181805)
私のコードでは上の２つは3重ループを回しているのと同じですので、すごく遅いです。
makiさんのコードは私の最後のコードと同じで2重ループです。
このような単純なケースでは内包表記は1行で書ける自己満足でしかないのです。
とほほ。
記事のタイトルからdisられるのかなと思ったらそうでもないんですね(^ ^;
(そういう意味じゃないのはわかっています)
確かに自己満ですね。ただネストとか重ねなければ個人的には可読性は大して変わらないと思います。
appendを使うシーンがあればなるべくmapか内包表記を検討してみるという感じでしょうか？
@namnium1125 さん
入力部分は次のように書くと高速化が期待できるかもしれませんね。
import sys
inputs = [
__[e for e in map(int, row.split())] for row
__in sys.stdin.readlines()
][:-1]
註：空白をアンダーバーで代替しています。
確かに私自身が繰り返しでappend使ってますもんね…(コメントをもらって気づきました)、両方0という条件に囚われたかもしれません。
ちょっと改良したものを載せてみます。
個人的に分かりやすいコードで実行時間の検証もしていただいてありがとうございました！コードを改良するのに一番参考にさせていただいたのでベストアンサーとさせていただきました。
ご回答ありがとうございました。
0
まず、基本的なこととして
- 説明コメントを書きましょう。コードだけだと他人には何をしているのか分かりにくいです。書いた本人でも後で何をしているのか分からなくなることがあります。
とくに、後半のif文、長くて何をしているのか分かりにくいので、何をしているのか？というコメントを書きましょう。
-
変数名は分かりやすいものをつけましょう。たとえば
inp[0]よりも問題文で使われているnの方が分かりやすいです。 -
intへの変換は最初に行いましょう。各処理中に何度もint(～)とするのは無駄です。
次に、ロジックについてですが
各値の取りうる範囲に条件がないか（探索範囲を絞れないか）？を考えるようにしましょう。
たとえば題意より解が存在するのはnは3以上、xは6以上かつn + n-1 + n-2以下であることが明らかです（理由は考えてみましょう）
また、重複なしの３つの数をs1,s2,s3とすると、その取り出す順番は不問なのでs1 > s2 > s3という条件を設けることができます。これらの条件により、ループ範囲の削減と重複チェックそのものが不要になります。
最後に。
あるs1とs2が決まった場合、s1+s2+s3=xを満たすs3は１つに決まるので…
Python
1def gen_ans1(n,x): 2 for s1 in reversed(range( 3, n+1)): 3 for s2 in reversed(range( 2, s1)): 4 s3 = x - (s1 + s2) 5 if s3 >= 1 and s3 < s2: # 制約条件 6 yield (s1,s2,s3) 7 8for (n,x) in [(5,9),(100,123),(1000,1234),(10000,12345)]: 9 ret = list(gen_ans1(n,x)) 10 print(n,x,len(ret))
さすがにn=10000くらいだと時間かかりますね…
投稿2018/01/23 07:58
編集2018/01/23 09:22
総合スコア38262
ごもっともなご指摘ありがとうございました。人に見せることを意識せず質問にコードを載せていました...とてもお恥ずかしいです...。今後気を付けていこうと思います。数学的に考えると簡潔なコードにすることができますね！とても勉強になりました。
ご回答ありがとうございました。
「改善するべきところを指摘」という質問でしたので、思ったことをそのまま回答しました。
が、私自身のコードの書き方に対する自戒も含まれます。適切な命名とコメント、なかなかできないんですよね…
0
そのサイトではnumpyが使えないですが、試しにnumpyのarrayを用いて動的計画法で解くプログラムを作ってみました。
python
1import numpy as np 2 3def countCombinationsNumpy(n, x, size=3): 4 dp = np.zeros((x + 1, size + 1), dtype=int) 5 dp[0, 0] = 1 6 for i in range(1, n + 1): 7 dp[i:, 1:] += dp[:-i, :-1] 8 return dp[-1, -1]
投稿2018/01/23 10:10
編集2018/01/23 10:16
総合スコア2551
ご回答ありがとうございます！動的計画法ですか！まだコードを理解できていませんが勉強になります！
dp[j][k]は、「k 個選んで合計 j になる組み合わせが何通りあるか」を表しています。
使える数字が「1から i までの数字」で、この i を1つずつ増やしていきます。
最初は使える数字が1つもないので、0個選んで合計0になる方法が1通りのみで、他は全部0通りです。
for loop のところは dp の表を紙にでも書いてみるとご理解いただけると思います(というか文字で説明するのが難しいので端折ってますすみません)。
ポイントは、「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]) に更新すればいいということになります。
追加の解説ありがとうございます。すみません、動的計画法について勉強不足で理解ができないところがあります...。「dp[i:, 1:] += dp[:-i, :-1]」この部分がいまいち理解できないのですがもしよろしければ解説をお願いします。m(__)m
「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 とみなす)。
ありがとうございます。理解できました。
すみません、karamarioさんのコメントを読む前にコメントを編集してしまったのですが、
コードの「dp[i:, 1:] += dp[:-i, :-1]」の部分が理解できないのですが解説お願いできますか？
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) だけ右下にずらしたものが足し合わされることになります。
詳しい解説ありがとうございます。そもそもdp[j][k]はどのように決まるのかと思ったのですが、これは行列の加算を行っていく過程で求まっているということですか？
すみません、ご質問の意味がよく分からないのですが、
初期値として、dpは[0][0]で1、それ以外は0 になっていますので、あとは dp[i:, 1:] += dp[:-i, :-1] で値を更新していくだけです。
すみません、説明不足でした。
i行列目の処理を行うときにはすでにi行列目の値が0ではない要素はi-1以下の処理で値が入れられているのかという質問でした。更新される要素とされない要素があるので、更新されずに値が0ではない要素はもともと値が入っているのかと思ったのですが...。的外れな質問かもしれません。
i 行列目というのは dp[i] のことでしょうか？
すみません、誤字ですね。i行目,dp[i]のことです。
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
例をあげると、dp'[5][2]=dp[5][2]+dp[0][1]のdp[5][2]はどのタイミングで値が入るのでしょう？
dp[0][1]は0なのでこのとき更新は行われません。よってもともとdp[5][2]に入っていた値が正しい値となると思うんですが。
「どのタイミングで値が入る」とは、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]に入っていた値が正しい値となると思うんですが。
はい、そうです。
そうですよね。ちょっとした確認のつもりだったのですが、お手数をおかけしました。ありがとうございました！
0
処理的には比較的分かりやすいですが、速さを求めるのであれば、
jは1からではなくてi+1から始めて問題ないです。
そうするとi == jの分岐も不要になります。
同じようにkもj+1から始めると次の分岐と最後の分岐も必要なくなります。
iが一番小さい数字でkが一番大きい数字という前提が出来るので、
数字の前後関係を見る必要がなくなるからです。
また3n-3 < xの場合、解が出ないのでループさせません。
（n-3から連続する3つの和よりxのほうが大きい、同じようにxが4以下ならループの必要ないですね）
結構修正が必要ですが、1からインクリメントするよりnからデクリメントしたほうが、
おそらく多くのケースでbreakの条件に早く到達するので、
そちらのほうがいいかなぁ。
といったところです。
Python書いたことないのでコメントだけです。
投稿2018/01/23 08:01
総合スコア1400
まず数学的に考えることはとても大事ですね！僕は惰性でコードを書いてしまって複雑なコードになってしまうことが多いので、とても勉強になりました。
ご回答ありがとうございました。
0
満たさないものを弾くのではなく、数え上げた方が探索空間が少ないです。
（nC3とn^3どっちが大きいのかという話です。）
たとえば、
https://docs.python.jp/3/library/itertools.html#itertools.combinations
コンビネーションを使えば、３つの数字が同じになるものは探索しなくてすみます。
（実際は探索空間が6分の1くらいに減るのですが）
それとinp[0]>inp[1]は探索しなくて良いはずです。
たとえばこんなやつ。
python
1from itertools import combinations as comb 2def get_ans(m, n): 3 ans = 0 4 for nums in comb(list(range(1, min(m+1,n-2))), 3): 5 if sum(nums) == n: 6 ans += 1 7 print(ans) 8 9while True: 10 m, n = (int(x) for x in input().split()) 11 if m==0 and n==0: 12 quit() 13 get_ans(m, n)
python的最適化。
python
1from itertools import combinations as comb 2def get_ans(m, n): 3 ans = sum(1 for nums in comb(range(1, min(m+1,n-2)), 3) if sum(nums)==n) 4 return ans 5 6while True: 7 m, n = (int(x) for x in input().split()) 8 if m==0 and n==0: 9 quit() 10 ans = get_ans(m, n) 11 print(ans)
大変遅かったのでnC2にすることにしました。
可読性は落ちましたが、m倍早くなりました。
たぶんね。
python
1from itertools import combinations as comb 2def get_ans(m, n): 3 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))) 4 return ans 5 6while True: 7 m, n = (int(x) for x in input().split()) 8 if m==0 and n==0: 9 quit() 10 ans = get_ans(m, n) 11 print(ans)
投稿2018/01/23 07:52
編集2018/01/23 08:54総合スコア8560
rangeオブジェクトをリストに直す必要はないんじゃないかな、と思いました。
必要なかったですね。
最適化したコードに反映しておきます。
conbinations関数という便利な関数があったんですね。勉強になりました！
なんどもコードを更新していただいてありがとうございました！とても勉強になります。
ご回答ありがとうございました。
0
私もmkgrei様と同様にcombinationsを作って組んでみました。
python
1from itertools import combinations 2 3inputs = [] 4n,x = map(int,input().split()) 5while n != 0 or x != 0: 6 inputs.append((n,x)) 7 n,x = map(int,input().split()) 8 9for n,x in inputs: 10 print(len([c for c in combinations(range(1,n+1),3) if sum(c) == x]))
これで上手くパスできました。
前回もそうですけど私は入力は一気に受け取る派です。
またかっこつけで内包表記にしていますが、内包表記は速度的にも速くなる速くなることもあるそうなので競プロだとオススメかもしれません。
combinations縛りももし可能だったらトライしてみようと思います。
Python 3.6.1
投稿2018/01/23 08:44
編集2018/01/23 09:29総合スコア2043
一見するとリスト内包表記のほうが速そうですが、遅くなることもあるみたいですね。勉強になりました！
今回もご回答していただきありがとうございました。
0
コードを下記のように改良しました。自分の元のコードがいかにムダが多かったか思い知らされました...
そしてみなさんとてもありがたいご回答をしていただきありがとうございました。ベストアンサーを一人に決めるのは少し心苦しいかったのですが一番参考にさせていただいた方を選ばせてもらいました。
みなさん、本当にありがとうございました。
また競プロの問題で質問させていただくと思うので、もしお時間があれば是非またご回答宜しくお願い致します。
Python
1# coding: UTF-8 2def find_comb(n,x): 3 count = 0 4 #探索 5 for i in range(1,n-1): 6 for j in range(i+1,n): 7 k = x - i - j #←がi < j < k <= nを満たせばその時点で総和がxとなる 8 if j < k <= n: 9 count += 1 10 print count 11while(1): 12 n,x = map(int, raw_input().split(" ")) 13 if n == 0 and x == 0: 14 break 15 find_comb(n,x)
投稿2018/01/23 13:09
総合スコア34
参考にしていただけたようで何よりです。
他の方々が扱っているテクニックも実戦でよくあらわれるものです
ですが、単純なものであればこのような形のものが有力かと思われます。
私自身も各回答者の回答を見て勉強となるところがありました。
元々数学家畑の人間だったので、学生時代を思い出しながら楽しくやらせていただきました。
ありがとうございます。
0
つい熱くなってしまい、失礼しました。
話の本筋に戻りますと、主様のコードは失礼ながら無駄が多く感じます。
やりたいことは何となく分かるのですが、少し工夫するだけでコードもきれいになりますし、可読性も向上します。
また、複雑なコードを人に見せるときは、随所にコメントをいれていただけると、なぜそうしたのかがわかりやすいです。
これが競技プログラミングという性質上、本来コメントは不要とは思いますが、質問の際にはそうしていただけると助かります。
投稿2018/01/23 09:21
総合スコア72
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/01/23 08:49
2018/01/23 08:49
2018/01/23 09:05 編集
2018/01/23 09:37
2018/01/23 10:12
2018/01/23 10:35
2018/01/23 12:35 編集
2018/01/23 12:54 編集
2018/01/23 12:51
2018/01/23 12:59
2018/01/23 12:59
2018/01/23 13:24