このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 082 - Counting Numbers（★3） ポイント 1度、各桁ごとに書かれる文字の個数を整理してみましょう。例えば、1桁の数字は1~9まであり黒板に書かれる文字の総数は下記の式で求めることができます。 ...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 076 - Cake Cut（★3） ポイント この問題は累積和を使って解くとスムーズです。本問題に限らず、連続する~個のといった言葉が出てきたら累積和を使えないか考えてみるといいでしょう。 まず、N個のピースそれ...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 075 - Magic For Balls（★3） ポイント 1回の魔法で各ボールは2つに分裂できるので、必要な操作の回数は元の整数xを因数分解した時の因数の数の対数、すなわちlog2(因数の数)の小数点以下切り上...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 069 - Colorful Blocks 2（★3） ポイント N = 1, 2, 3以上の場合に条件を満たすような塗り方が何種類あるか見てみましょう。 N = 1 の場合答え：K通り　K種類の色を使用して1つの...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 064 - Uplift（★3） ポイント 何となく皆さん予想がついているとは思いますが、地殻変動が起こるたびに全ての区画の不便さを再計算していたら余裕でTLEです。 ここで、地殻変動が起こる際、不便さがどのように...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 032 - AtCoder Ekiden（★3） ポイント 10人の選手の並べ方の総数は10! = 3628800通りです。総当りで調べても十分時間内に間に合うので、噂になっている2人が並ばない組み合わせを全探索し...

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 016 - Minimum Coins（★3） ポイント 各コインの使用枚数を全探索で求めていきたいところですが、9999枚分のfor loopを3重にする下記の様なコードではTLEとなってしまいます。 for a...