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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Python

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

PyPy

PyPy(パイパイ)は、RPythonで記述されたPythonの実装のひとつです。CPythonとの互換性に重点を置いて開発されており、コードを必要に応じて機械語にコンパイルする「JITコンパイル機能」を備えています。

Q&A

解決済

1回答

440閲覧

AtCoder ABC159 E問題 高速化の方法(貪欲法)

shake9

総合スコア19

Python

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

PyPy

PyPy(パイパイ)は、RPythonで記述されたPythonの実装のひとつです。CPythonとの互換性に重点を置いて開発されており、コードを必要に応じて機械語にコンパイルする「JITコンパイル機能」を備えています。

0グッド

0クリップ

投稿2020/06/10 13:24

発生している問題・実現したいこと

AtCoder ABC159について、テストファイル19個のうち、8つがTLEとなりました。
プログラムを高速化し、ACするためにはどこを改善すれば良いでしょうか。

該当のソースコード

Python

1h,w,k = map(int,input().split()) 2s = [list(map(int,input().strip())) for i in range(h)] 3 4def gru_hol(HOL): # セットから切り方を作る 5 groups_a = [] 6 group_a = [0] 7 for i in range(h-1): 8 if(HOL[i] == 1): 9 groups_a.append(group_a) 10 group_a = [i+1] 11 else: 12 group_a.append(i+1) 13 groups_a.append(group_a) 14 return groups_a 15 16def nex_hol(HOL): #次のセットを作る 17 for j in range(h-1): 18 if(HOL[j] == 0): 19 HOL[j] = 1 20 for k in range(0,j): 21 HOL[k] = 0 22 break 23 return HOL 24 25def cutsum(grp,lscut,nxcut): #groupのlastcut~nextcutのホワイトチョコを数える 26 count = 0 27 for i in grp: 28 for j in range(lscut,nxcut): 29 count += s[i][j] 30 return count 31 32def cutcheck(grp_a,lscut_a): #切ってもダメかチェック 33 ct_a = 0 34 for i in grp_a: 35 ct_a += s[i][lscut_a] 36 if(ct_a > k): 37 return False 38 else: 39 return True 40 41min_cut = h + w - 2 #切り方の最小値 全部切ったらこの値 42hol = [0]*(h-1) #水平方向の切り方を2進数で表現 43for i in range(2**(h-1)): 44 fl_ag = 0 45 lastcut = 0 46 cuts = 0 #切る回数 47 groups = gru_hol(hol) #groupsを作る 48 for j in range(1,w): #鉛直方向のうちどこを切るか調べる 49 flag = 0 50 for group in groups: 51 if(cutsum(group,lastcut,j+1) > k): 52 if(cutcheck(group,lastcut) == False): 53 fl_ag = 1 #切ってもダメなので、groupsから作り直し 54 break 55 else: 56 flag = 1 57 if(fl_ag == 1): 58 break 59 if(flag == 1): 60 cuts += 1 61 lastcut = j 62 63 if(cutcheck(group,w-1) == True): 64 min_cut = min(min_cut,cuts+sum(hol)) 65 nex_hol(hol) 66 67print(min_cut)

試したこと

PyPyで提出すると8ファイル中4ファイルはACとなりましたが、残り4ファイルはTLEのままでした。

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

十分かどうかはともかく、cutsumが重すぎるので改善は必要でしょう。
特にlastcutが動かない場合(すべてのチョコレートが0の場合など)、cutsum(group,lastcut,j+1)は、0~jまでのマスを毎回すべて足し合わせることになります。

投稿2020/06/10 14:38

yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

shake9

2020/06/10 16:16

ありがとうございます。 左端からの合計を記録し、その差をとることでcutsumを計算するように変えました。 結果、PythonとPyPyどちらでもACとなりました。 的確なご指摘、ありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問