データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上
下
前
次
1-
新
55
: 2021/10/24(日)22:55
ID:340Kt+5N(1)
AA×
>>54
[
240
|320|
480
|
600
|
100%
|
JPG
|
べ
|
ﾚｽ栞
|
ﾚｽ消
]
55: [sage] 2021/10/24(日) 22:55:10.72 ID:340Kt+5N >>54 k日間で得られるポイントの合計の最大値を P(k) と表し、k日目に解禁されるタスクが2つあってそれぞれのポイントを p, q (p < q) とする。 貪欲法でないやり方で求めた最適解P(k)*があるとする。--- (1) 貪欲法でないある方針に基づいてpポイントのタスクを選択したとする。 このとき、貪欲法に基づいてqポイントのタスクを選択したとすると、P(k) = P(k)* + q - p となる更に良い解が得られ、(1) の「貪欲法でなくても最適解」の前提条件に矛盾する。 毎回思うけどこの atcoder てあんまり良くないね。 日本語の問題文があるから重宝されてるのかもしれないけど、入力のサイズが小さすぎてブルートフォースでも瞬時に解けたり、解説ないからもっと良い解があるのかわからないし、leetcode あたりのが勉強になると思う。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/55
日間で得られるポイントの合計の最大値を と表し日目に解禁されるタスクがつあってそれぞれのポイントを とする 欲法でないやり方で求めた最適解があるとする 欲法でないある方針に基づいてポイントのタスクを選択したとする このとき欲法に基づいてポイントのタスクを選択したとすると となる更に良い解が得られ の欲法でなくても最適解の前提条件に矛盾する 毎回思うけどこの てあんまり良くないね 日本語の問題文があるから重宝されてるのかもしれないけど入力のサイズが小さすぎてブルートフォースでも瞬時に解けたり解説ないからもっと良い解があるのかわからないし あたりのが勉強になると思う
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 50 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
ぬこの手
ぬこTOP
0.025s