このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 075 - Magic For Balls（★3） ポイント 1回の魔法で各ボールは2つに分裂できるので、必要な操作の回数は元の整数xを因数分解した時の因数の数の対数、すなわちlog2(因数の数)の小数点以下切り上...
競プロ典型90問
競プロ典型90問の記事一覧
このシリーズでは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...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 052 - Dice Product（★3） ポイント 各サイコロの目の合計の総積が解答となります。 素直に合計を掛け算していくとオーバーフローとなるので割りながらかけて、最後にもう一回割ります。 コード def ...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 050 - Stair Jump（★3） ポイント 動的計画法で解きます。 L 段目までは1歩ずつあがるしかないので1通り L 段目以降は今の段目-L段目からL段飛び越してくる方法と、i-1段目から1つ上がる方法が...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 048 - I will not drop out（★3） ポイント 貪欲法で点数の高い順に取っていきます。 コード def main(): import sys sys.setrecursionlimit(10 ...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 046 - I Love 46（★3） ポイント Ai + Bj + Ckが46で割り切れるとき Ai ÷ 46 の余り + Bi ÷ 46 の余り + Ci ÷ 46の余りも46で割り切れます。 この問題はここに...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 044 - Shift and Swapping（★3） ポイント Ti = 2 のクエリが曲者です。このクエリのたび素直にリストの並び替えを行うとTLEとなってしまいます。 そこで、これまでTi = 2 が何回来...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 038 - Large LCM（★3） ポイント AとBの最小公倍数は以下の式で求めることができます。 A x B ÷ (AとBの最大公約数) AとBの最大公約数を求めるにはmathライブラリのgcdを使用します。...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 020 - Log Inequality（★3） ポイント 問題文の通りに比較しようとすると、以下のようなコードを思いつくかもしれません。 import math if math.log2(a) < b * ...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 014 - We Used to Sing a Song Together（★3） ポイント 小学生の家と学校の位置をそれぞれ昇順ソートして、左からi人目の小学生を左からi番目の学校に通わせていくことで最適解を得る...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 007 - CP Classes（★3） ポイント クラスを昇順ソートして、二分探索で生徒が入るべきクラスを探ります。 コード def main(): import sys from bisect import b...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 002 - Encyclopedia of Parentheses（★3） ポイント 長さがNとなる「(」と「)」の組み合わせを全て試し、正しいカッコ列かどうかを検証します。 Pythonで組み合わせを生成するには...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 078 - Easy Graph Problem（★2） ポイント はじめに各頂点の隣接頂点のグラフを作成し、その後条件に当てはまる頂点を探索していきます。 コード def main(): import sys s...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 067 - Base 8 to 9（★2） ポイント 問題文の通りに作業するだけです。 8進数から一気に9進数にするのが少々めんどいので、8進数→10進数、10進数→9進数に操作を分けています。 コード def m...
このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。 問題 061 - Deck（★2） ポイント この問題はリストで山札を管理し、クエリの順番通りに要素を追加、出力するだけでACできます。 コード def main(): import sys sys.setrecursi...
