/ 最近 .rdf 追記 編集 設定 本棚

脳log[20211001]



2021年10月01日 (金) [AtCoder] 精進。ABC104-C「All Green」(水 diff)。配点の高い問題から解いていきたいけど完答ボーナスがちょっとした番狂わせを演出するのにどう対処するか。貪欲がダメなら DP すればいいじゃない。だから DFS で解いた>提出 #26249595。問題群を ボーナス込みの得点合計÷問題数 でソートして効率のいい方から総当たり(打ち切りあり。残りスコアの合計からと得点効率から計算する最小値更新の見込みから)。問題の解き方は問題群単位で全部解くか1問も解かないかスコアを満たせるだけ解くかの3パターンしかない。制約がたいへん控えめなので解法もバラエティに富んでいる印象>Ruby によるすべての提出。と思ったらほとんどがビット全探索で DFS が少々、といった感じ。DP はダメだったか。たしかに、全部解くか残スコア分だけ解くかの2択に対して p 回繰り返すループは、それが無理な制約ではないにしても無駄が多い。