解けなかった問題集

解説を読んでもよくわからず、解けなかった問題を載せていき、気が向いた時にもしかしたら解き直すかもしれない問題たちの墓場。

増えていったり減ったり更新されなかったりするもよう。

1, 5, 10, 50...みたいになってるコインから指定の額以上になる組み合わせをなるべく多く作る問題。

目的の金額Cとしたとき, C以上の価格のコインは1枚で解決（自明）

Cに対してCより安いコインを採用した時、

C' = C - coin[i]

となる。（自明）

これをCがなるべく小さくなるようにした後、今残っている最小金額のコインで残りの金額を調整するらしい。（非自明）

どうやって実装するんだ…

解説を見た感じ難しいらしい。

けど典型らしい。そのうち解こう。

幾何っぽい。こわい。

解説を見ていない。そのうち解こう。

バーチャルコンテストで扱った。

多分もしかするときっとそのうち解く。

回文＋期待値

ぷぇ