2021-07-06から1日間の記事一覧
問題 atcoder.jp 解法 鉄の棒の長さLが例えば100のとき、分割できる地点は正整数となる地点だけなので、99箇所。 ここから11箇所の切断点を選ぶ。 つまり、99箇所から11箇所の切断点の選び方の組み合わせ数を計算すれば、答えになる。 組み合わせの公式nCrを…
![はてなブックマーク - AtCoder Beginner Contest 185 [ C - Duodecim Ferra ]をPythonで解く（300点、⬜️灰色diff）](https://b.hatena.ne.jp/entry/image/https://uchidama.hatenablog.com/entry/2021/07/06/235538)
問題 atcoder.jp 解法 数列Aの中のAiの倍数を配列fをつくって、あらかじめカウントしておく。 f[i]はIの約数の数が入る。 これができてしまえば、Aiの数値の約数はf[Ai]を参照すればわかる。 f[Ai]が1ならば、Aiの約数は自分自身しかないので、数列Aの中にAi…
![はてなブックマーク - AtCoder Beginner Contest 170 [ D - Not Divisible ] をPythonで解く（400点、🟩緑diff）](https://b.hatena.ne.jp/entry/image/https://uchidama.hatenablog.com/entry/2021/07/06/203519)
問題 atcoder.jp 解法 1 〜 Nまでの約数を配列に保存する方針。 1の倍数、2の倍数、3の倍数……と各配列に1づつ足していく。 この約数を求める計算量は Nを外にだして Σ部分は調和級数になるので、だいたいlogNになる。 ゆえに計算量はO(NlogN)とのこと。 約数…
![はてなブックマーク - AtCoder Beginner Contest 172 [ D - Sum of Divisors ]をPythonで解く（400点、🟩緑diff）](https://b.hatena.ne.jp/entry/image/https://uchidama.hatenablog.com/entry/2021/07/06/181000)
問題 atcoder.jp 解法 N人を運ぶのに、５つの交通機関の中で一番処理能力が低い交通機関をソートして求める。 ここがボトルネックになる。 このボトルネックになってる交通機関がN人を何分で処理できるかを計算。 他の４つの交通機関は、このボトルネックの…
![はてなブックマーク - AtCoder Beginner Contest 123 [ C - Five Transportations ]をPythonで解く（300点、🟫茶diff）](https://b.hatena.ne.jp/entry/image/https://uchidama.hatenablog.com/entry/2021/07/06/014836)
問題 atcoder.jp 解法 とにかく入力例とか問題の内容読むと「これ約数の問題っぽくない！？」と悟れという問題のよう。 最大公約数がモンスターのHPの最小値になるので、これを求めればよい。 3つ以上のパラメータの最大公約数の求め方が実装例(Python3.8系)…
![はてなブックマーク - AtCoder Beginner Contest 118 [ C - Monsters Battle Royale ]をPythonで解く。最大公約数(GCD, greatest common divisor)を求める問題（300点、🟫茶diff）](https://b.hatena.ne.jp/entry/image/https://uchidama.hatenablog.com/entry/2021/07/06/011523)
問題 atcoder.jp 実装 この問題は、普通にACしてるんだけど、実装メモとして。 たまにAtCoderで、リスト内の要素がソートした結果、前から何番目か？という情報が必要になってくることがあるけど、その実装パターンとして残しておく。 A内の要素を、Bにソー…
![はてなブックマーク - AtCoder Beginner Contest 208 [ C - Fair Candy Distribution ]をPythonで解く。数列の要素が前から何番目かを管理する、たまに必要な実装メモ（300点、⬜️灰色diff）](https://b.hatena.ne.jp/entry/image/https://uchidama.hatenablog.com/entry/2021/07/06/001442)
