割り算を実装したのは久しぶり。 問題 yukicoder.me 考察 整数部分は普通にA / Bで計算し、小数点以下は筆算と同じ方法で計算する。 その際に「B * x <= Rを満たす最大の整数x」みたいなのを求めたくなるけど、これは数学を使うとO(1)で求められる。 具体的…

問題 Convex-Hull Trickの入門に最適な問題。 DPの更新式を変形することでmin({ A[1]*x + B[1], ..., A[i]*x + B[i] })の形を得て、これはConvex-Hull Trickでの高速化を望める。

問題 初めて行列演算が腑に落ちた気がする。 行列演算を使うことで、ベクトルの各成分の入れ替えたり、ついでに成分の値を倍にしたりできる。この問題だと、位置を64要素を持つベクトルと見て、移動を64x64行列の演算と見なせる。 今回の問題の自然な解き方…

問題 蟻本の復習みたいな感じ。 まずはじめに思いつくDPは以下のようなもの。 DP定義 dp[i][j][k] = 真偽値 i : 解いた問題の数 j : 雪男くんの解いた問題の合計秒数 k : 雪女さんの解いた問題の合計秒数 初期値 dp[0][0][0] = true dp[i][j][k] = false (i …

次の問題を解いた。 yukicoder No.783 - 門松計画 問題 この問題の解説を見ることで、個数制限なしナップサックDPを使えるようになった。個数制限なしナップサックDPについて少し勘違いしていて、次の順序でDPをするものだと思っていた。 荷物1を可能な限り…

yukicoder No.798 - コレクション 問題 自力で解けなかった。悲しい。 Ai + Bi * dという式を見た途端、頭の中がConvex-Hull Trickで支配された。そのせいか、「Biの降順で選ぶのが最適」という簡単な事実にすら気付かなかった。解説をチラ見してこの事実を…

問題 解けなかった。悔しい。 想定解法は、累積和といもす法という2つの基本的なアルゴリズムを組み合わせるというもの。しかし、これがわからなかった。通した今でもよくわかっていない。 図を書いて理解した。 dp[i][j]を配るという発想ではなく、範囲に着…

Convex-Hull Trickについては理解したけど、DPの遷移式をどのように変形するかがわからない。そこで、問題にあるタグ「Monge」で検索すると、何だかそれらしい情報がヒットする。しかし、これについても結局よくわからなかった。 Mongeを知っていく過程でこ…

yukicoder.me 考察 この問題は、「合計が\(X\)以下となる\(0\)以上の整数\(D-1\)個の組はいくつあるか」という問題に言い換えられます。そしてこの問題はベル数やスターリング数を求めるときのように、漸化式を立てることで数え上げることができます。 実装 …

yukicoder.me 概要 以下の条件を満たす数列\((A_1, \ldots, A_N)\)は何通りあるでしょうか。\(10 ^ 9 + 7\)で割った余りを求めてください。 \(A_1 + \ldots + A_N = S\) 任意の\(i(1 \le i \le N - 1)\)に対して\(A_i + K \le A_{i + 1}\) 制約：\(2 \le N \…