このシリーズでは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...
