atcoder.jp 解法 香辛料の消費量は、整数以外も選択できるがどこかで調整すればすべて整数にすることができるので、最初から整数で考えてよい。 ナップザックDP感があるので、普通にDPするしようとすると、 dp[i][w] ← i番目までの料理を作った時、香辛料をw…

atcoder.jp 制約を見て半分全列挙とかいうやつじゃないか、と気づいた。 勉強したことなかったので記事にします。 半分全列挙について 簡単にいうとbit全探索もしくは何重かfor文全探索を、二分探索などで高速化しようという考え方のこと。 下の記事の解説が…

atcoder.jp 解法 エラトステネスの篩で素数かどうか判定する代わりに、素因数の種類を数えればOK。 N ≦ 107 でも間に合うんですね。 実装 K=1のときは場合分けした方が実装が楽だと思った。 void solve(long long N, long long K) { if (K == 1) { c(N-1) re…

atcoder.jp LIS問題という有名問題を少し変えた問題です。 LIS問題について 最長増加部分列(LIS)問題は、昇順(または降順)となるような部分列は最長でいくつ作れるか？という問題です。 O(N2)のDPが最初に思いつきましたが、これでは間に合いません。 有名問…

問題リンク 解法 問題文を読んだだけでは、観覧車がどのような動きをしているのかわかりにくいが、図を書いてみると、中心を(0, 0, L/2)とした半径2/Lの円周上を動いていることがわかる。 まず、与えられた時間の時の現在地の座標が知りたい。 中心を(0, 0, …

問題リンク 解法 a,b,cのなかにKが持っていない素因数を持っている数が含まれることはないので、a,b,cは必ずKの約数だとわかる。 後は約数の中から条件を満たす組を全探索できれば良いが、最大5000個以上の約数を持つ可能性があるのでN3では間に合わない。 (…

問題リンク 解法 解説スライドで紹介されていた解法とは違う方法で解いた。(解法2に少し似ているかも) 既にoxが含まれている区間を、右左どちらに広げても必ずoxが含まれることがわかる。 線形時間で問題を解きたいので、lかrを固定したい。今回はlを固定し…

問題リンク 解法 体重・身長の取る範囲が小さいということがとても気になる。 これをどうにか使えないかと考えてみると、二次元平面上に(身長, 体重)のようにプロットして、何らかの方法で条件を満たすそれぞれの範囲内にいくつ点が存在するかを高速に計算で…

問題へのリンク 解法 最短経路を求めたりする問題ではないので、BFSではなくDFSがしたい気分になる。 制約がとても緩いので、全探索が有効そう。 スタート地点は最大でも16通りしかないので、すべてのスタート地点から探索を開始してみることにする。 DFSの…

問題へのリンク 解法 区間の和を求めるということでまずしゃくとり法が思いついた。 全体の総和をsumとして、x = sum/10 とすると、区間の総和がx以上になるまで右端を動かし続け、x以上になった時点で区間の総和がsumと等しいかを確認すれば良い。 また、su…