7K12 blog

猫でも分かるアルゴリズム解説

2020-06-10から1日間の記事一覧

ABC153 E - Crested Ibis vs Monster

https://atcoder.jp/contests/abc153/submissions/14123891 個数無制限ナップサックDPは一次元で処理できる(ただし、繰り返しは二重ループ) 配るDPで制約オーバーするときは貰うDPでも制約オーバーで実装する infはオーバーフローしない程度の値(例えばと…

ABC152 E - Flatten

https://atcoder.jp/contests/abc152/submissions/12833879 全ての積が同じ値になる⇔全てBiで割り切れる⇔lcm(Ai) lcmがインフレするときは素因数分解を利用する 大きいAiと小さいBiの積にする必要があると分かるが、更に詰めていくと「全ての積が同じ値(な…

ABC151 E - Max-Min Sums

https://atcoder.jp/contests/abc151/submissions/12468410 Σ(X- Y) ⇔ ΣX - ΣY max(x)とmin(x)の決め打ち 素直に実装すると一生処理が終わらないので、線形処理できるように工夫する。max(x)とmin(x)を決め打ちすればf(x)の値が変わらないことに着目しつつ、…

ABC148 E - Double Factorial

https://atcoder.jp/contests/abc148/submissions/14100952 初めてコンテスト本番で解けたE問題。 積の数字の個数→素因数分解の考え方は大事(今回は素因数分解しない) 2の因数は大量にあるので、5の因数の個数だけ調べれば良い 数弱だと数式の意味は分かり…