Eまで。終了後F1は通った、と思ったらシステムテストで落ちた。
コンテスト後のツイート
D maxの最後のindexの位置がどこ以下が決まる。
— titia (@titia_til) December 29, 2025
E 貪欲。小さい箱から順に、その箱を使ったとき効率のよい（z-yが大きい）ものを詰める。
F1 必要なpower pに対して、cを使ったら(p-c)*2に更新（それが何個かは持つ）というDPで通った。TLEのつもりで書いたけど、よく考えたら計算量落ちてそうかも。
F2. Christmas Reindeer (hard version)
自力AC。見直したら難しくなかった。
各桁について、何個使うのがギリギリなのかが分かるので、ギリギリのときと、それ以上が確定したときに分けてDPしていく。ギリギリのときは何個使えば良いか？ が分かるので、それより大きい個数を使うときは確定。同じ個数を使うときはギリギリ。二項係数で計算する。
これも桁DPの一種といって良いかな。
コンテスト中、30分残っていたら解けて良かった気もするけど、問題把握に結構時間かかってしまったなぁ。
0 件のコメント:
コメントを投稿