SRM参加記録など雑記です。社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。Statement解答方針なぜか1-starクリアの数で二分探索なんじゃないかと思ってしまったいやいや、そもそも上限1000で二分探索なんか普通いらんし・・・というか何で二分探索なんだ。どの面を1-starに選ぶか決められないとそんな手法取れないし逆にそれが決められるなら二分探索いらない気がするもう一度落ち着いて考えるある状態で2-starに行ける面があるなら、常に取ってしまっていいある状態で1-starしか行けないとき、どの面を選ぶかが問題になる1-starの必要star数を満たしていないものは当然除外する1-starの必要star数を満たすものの中で、2-starの必要star数が小さいものを残しておいたほうが、総合的に1-starクリア数を減らせるんじゃないかこれで行けば、Greedyでいいことになる問題文中のサンプルの進め方と異なるが、本当に正しいか。(1-starの必要star数,2-starの必要star数)という表現で具体的な例を考える(0,1)と(0,3)があったとする(0,1)からクリアすると、(0,1),(0,1),(0,3),(0,3)の順で合計4回クリアする必要がある(0,3)からクリアすると、(0,3),(0,1),(0,3)の順で合計3回クリアでいけるどちらの1-starを取っても、2-starの必要star数は変わらないし、もらえるstar数も変わらないだったら、なるべく早い時点で2-starが取れる可能性のある方を残しておいたほうが得に決まっているやはり正しそうだなサンプルはたまたまどちらから進めても同じ結果になる例なだけっぽいとりあえずできたが無駄に時間がかかった。OpenTipsDiv1SRM455SRM456SRM457SRM466SRM467SRM468SRM469SRM470SRM471SRM473SRM474SRM475SRM476SRM477SRM478SRM479SRM480SRM481SRM482SRM483SRM484SRM485SRM486SRM487SRM488SRM489SRM490SRM491SRM492SRM493SRM494SRM495SRM496SRM497SRM498SRM499SRM500SRM502SRM503SRM505SRM504.5SRM506SRM507SRM508SRM510SRM511SRM512SRM513SRM514SRM515SRM516SRM517SRM518SRM519SRM520SRM521SRM522SRM523SRM524SRM525SRM526SRM527SRM526.5SRM528SRM529SRM530SRM531SRM532SRM533SRM534SRM535SRM536SRM537SRM538SRM540SRM541SRM543カウンター358024リンク集SigmarのProfile。