naoya_t@topcoder

SRM420 Div1 Hard: ChangeOMatic

過去問, 練習 | 18:13 |

1000点問題の練習。（問題文はこちら。要TopCoderアカウント）

• すぐにコーディングを始める方式をやめて、先にノートに考えをまとめる方式に移行中。
• 問題文のTestCase 4で、想定される37ではなく34が出てしまう
  • 120 → 100 + 12 + 8 の後、100の分割が悪かった。
  • 12*7 + 8*2 = 100 が出せてない。
• priority queueを使って最小枚数かつ辞書順最大の組合せを得られるルーチンは書けた。しかしこれは大きな数の入力に非常に弱い（数十万程度でも遅い）ので、問題文のTestCase程度にしか対応できない。
• 少ないコイン枚数の（かつ辞書順で一番大きい）組合せを、大きな数（10^15まで）の入力に対し「高速に」得るロジックを（数学的にきちんと）考え直さないといけない。← いまここ