SRM参加記録など雑記です。社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。Statementコーディングフェーズうーん・・・まずはサンプル確認sample0によるとdeleteを使っているようだがどういう場面でdeleteが必要になるのだろう少なくともsample0はdeleteなしでも同じ答えになる。{0}→{2}→{2,2,2}→{3,2,2}→{3,2,3}同じようにやればどんな場面でもdeleteなしでできそうだ。returnの数はどうやっても数列のサイズ-1にしかならないので最初に加算する。spaceのコストは、例えば、a<=b<=c<=dで{a,c,b,d}を作るとき、以下の順で作ればc+(d-b)のスコアで作成できる{a}→{a,a}→{a,b}→{a,b,b}→{a,c,b}→{a,c,b,b}→{a,c,b,d}もっと複雑なパターンでも同じように作成できる例えば{1,2,4,3,2,5}などでは以下のようにやれば良い{1}→{1,1}→{1,2}→{1,2,2,2}→{1,2,3,2}→{1,2,3,3,2}→{1,2,4,3,2}→{1,2,4,3,2,2}→{1,2,4,3,2,5}deleteを使っても結局このようなGreedyな方法より良いスコアは出せそうにない。(試せば分かるが、どうやってもdeleteのスコアとspaceのスコアが相殺される)少なくとも、sampleは全部これで答えが合う。・・・これは簡単すぎていかにも罠っぽいな。計算量も余裕すぎるし。550でこの解はありえん。提出その後も残り45分ずっと反例を考えるが見つからず・・チャレンジフェーズみんな全然違うDP解(涙目)8回もチャレンジを受けるが生き残るシステムテストPassed信じられん。OpenTipsDiv1SRM455SRM456SRM457SRM466SRM467SRM468SRM469SRM470SRM471SRM473SRM474SRM475SRM476SRM477SRM478SRM479SRM480SRM481SRM482SRM483SRM484SRM485SRM486SRM487SRM488SRM489SRM490SRM491SRM492SRM493SRM494SRM495SRM496SRM497SRM498SRM499SRM500SRM502SRM503SRM505SRM504.5SRM506SRM507SRM508SRM510SRM511SRM512SRM513SRM514SRM515SRM516SRM517SRM518SRM519SRM520SRM521SRM522SRM523SRM524SRM525SRM526SRM527SRM526.5SRM528SRM529SRM530SRM531SRM532SRM533SRM534SRM535SRM536SRM537SRM538SRM540SRM541SRM543カウンター357907リンク集SigmarのProfile。