atcoder.jp 具体例で考える 入力例 2の 5915 は、次のように計算されます。 桁の数は、切れ目を入れられる部分が 個あり、それぞれについて切れ目を入れる/入れないの どちらかになるため、[2^{N-1}] 通りの掛け算の和を求めることになります。 は大きな数に…

atcoder.jp 欲しい商品だけを購入する場合 商品を購入するとき、定価＋追加金額 が必要になります。 定価はどのように商品を購入しても変わりませんが、追加金額 は商品の購入順序によって変わります。 そこで、まず追加金額が最小になる買い方を考えます。…

atcoder.jp 累積和の考えを利用する 連続する区間に、同じ数字を加える操作をします。これを繰り返すときは、累積和の考え方 （「競技プログラミングの鉄則」2.2 一次元の累積和(2) ）が利用できます。 前の数字との差を表す配列を用意すると、 番目から連続…