問題 030 - K Factors（★5） ポイント 2以上N以下の整数の素因数の種類を全て求め、最後にK 種類以上の素因数を持つものの個数を求めます。 方法としては2からNまで全探索していき、素数を見つける度にその素数で割り切れるN以下の全ての整数の素因数の種類数を+1します。 以上を踏まえ、実装したコードがこちら...

問題 051 - Typical Shop（★5） ポイント 競プロに親しみがある方だとこの問題を見たときにナップサック問題と似ている→動的計画法で解ける！と思われるかもしれません。 ただ、残念ながらこの問題を動的計画法で解くことはできないのです・・・。理由は値段の合計Pと、各商品の値段Aiの上限が大きい（10の18乗...

問題 085 - Multiplication 085（★4） ポイント a,b,cの候補を全探索していきますが、実直に全てのパターンを試すとTLEとなってしまいます。 そこで、問題文から得られるaは√k以下、bはa以上という制約を利用して全探索の範囲を絞ることで時間内に探索を終えることができます。 以上を踏まえ、実装...