競プロ典型90問 【競プロ典型90問】「082 - Counting Numbers(★3)」解法 2022年3月31日 このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 082 - Counting Numbers(★3) ポイント 1度、各桁ごとに書かれる文字の個数を整理してみましょう。例えば、1桁の数字は1~9まであり黒板に書かれる文字の総数は下記の式で求めることができます。 ... TheLogicalBear
競プロ典型90問 【競プロ典型90問】「076 - Cake Cut(★3)」解法 2022年3月29日 このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 076 - Cake Cut(★3) ポイント この問題は累積和を使って解くとスムーズです。本問題に限らず、連続する~個のといった言葉が出てきたら累積和を使えないか考えてみるといいでしょう。 まず、N個のピースそれ... TheLogicalBear
競プロ典型90問 【競プロ典型90問】「075 - Magic For Balls(★3)」解法 2022年3月27日 このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 075 - Magic For Balls(★3) ポイント 1回の魔法で各ボールは2つに分裂できるので、必要な操作の回数は元の整数xを因数分解した時の因数の数の対数、すなわちlog2(因数の数)の小数点以下切り上... TheLogicalBear
競プロ典型90問 【競プロ典型90問】「069 - Colorful Blocks 2(★3)」解法 2022年3月25日 このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 069 - Colorful Blocks 2(★3) ポイント N = 1, 2, 3以上の場合に条件を満たすような塗り方が何種類あるか見てみましょう。 N = 1 の場合答え:K通り K種類の色を使用して1つの... TheLogicalBear
競プロ典型90問 【競プロ典型90問】「064 - Uplift(★3)」解法 2022年3月23日 このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 064 - Uplift(★3) ポイント 何となく皆さん予想がついているとは思いますが、地殻変動が起こるたびに全ての区画の不便さを再計算していたら余裕でTLEです。 ここで、地殻変動が起こる際、不便さがどのように... TheLogicalBear
競プロ典型90問 【競プロ典型90問】「032 - AtCoder Ekiden(★3)」解法 2022年3月21日 このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 032 - AtCoder Ekiden(★3) ポイント 10人の選手の並べ方の総数は10! = 3628800通りです。総当りで調べても十分時間内に間に合うので、噂になっている2人が並ばない組み合わせを全探索し... TheLogicalBear
競プロ典型90問 【競プロ典型90問】「016 - Minimum Coins(★3)」解法 2022年3月16日 このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 016 - Minimum Coins(★3) ポイント 各コインの使用枚数を全探索で求めていきたいところですが、9999枚分のfor loopを3重にする下記の様なコードではTLEとなってしまいます。 for a... TheLogicalBear