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

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

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

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

Q&A

解決済

1回答

785閲覧

AtCoder, ABC204-D, 誤答添削をお願いします.

Algeot

総合スコア21

Python 3.x

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

0グッド

0クリップ

投稿2021/06/07 04:59

https://atcoder.jp/contests/abc204/tasks/abc204_d
上記サイトの問題に対して, 私の解答が以下となります.

Python

1n = int(input()) 2t = sorted(list(map(int, input().split())), reverse=True) 3ans = sum(t) 4for i in range(n-1): 5 a = [t[_] for _ in range(i+1)] 6 b = [] 7 for j in range(i+1, n): 8 if sum(a) < sum(b): 9 a.append(t[j]) 10 else: 11 b.append(t[j]) 12 m = max(sum(a), sum(b)) 13 print(a, b, m) 14 if m < ans: 15 ans = m 16print(ans)

サンプルデータへの正答率が9割程なのですが, 残りの誤答がどういった部分で生じているのかわかりません.
コードの反例となる入力データにはどのようなものがあるのでしょうか.

以下コードの解説:
時間のかかる順に料理n個を並べる.
iを1からnまで走らせて, i個を1つ目のオーブンに必ず入れる事例を想定する.
このとき残りの料理のためにjをi+1からnまで走らせて, 使用時間に余裕のあるオーブンの方にj番目の料理を入れるという操作を行ってオーブンの使い方を決める.
この事例のオーブンの使用時間をmとする.(すなわちmはiを変数としている.)
mの最小値を求めれば, これが最小の使用時間となる.

なお, コード下から4行目にprint(a, b, m)と余計なものがありますが, これは解答時には事前に消してあります.

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

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

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

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

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

guest

回答1

0

ベストアンサー

たとえば入力例1を少し変えて
入力
5
8 3 7 3 5

とすると、質問欄のコードでは下記が出力されます。でも、正答は[8, 5] [7, 3, 3] 13 のはずですね。
[8, 3, 3] [7, 5] 14
[8, 7] [5, 3, 3] 15
[8, 7, 5] [3, 3] 20
[8, 7, 5, 3] [3] 23
14

最後の方の数字が大きいとき、それまでを最適化するだけではダメなようです。

投稿2021/06/07 06:25

編集2021/06/07 06:28
jeanbiego

総合スコア3966

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

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

Algeot

2021/06/07 14:19

ありがとうございました. お陰様で納得いたしました. [8]と[7]をオーブンの状況とした後に, コードでは次に大きい5を入れようと考えたが, 実際にはそれより大きい3+3=6を入れるべきで, それを考慮できていないのが問題点のようです.
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問