はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける連立方程式問題まとめ

連立方程式を使った解法について

解説

yukicoder No.75 回数の期待値の問題

http://yukicoder.me/submissions/157990
dp[i] := 現在マスiにいるときに合計をKとするためにサイコロを投げる回数の期待値
dp[i] = 1 + (dp[i + 1] + dp[i + 2] + ... + dp[i + 6]) / 6 + 1
※dp[i] = dp[0] (K < i)
dp[0]が答え。以下のサイトが分かりやすい
garnacha.techblog.jp

yukicoder No.463 魔法使いのすごろく

http://yukicoder.me/submissions/157992
まずyukicoder No.75と同様に期待値を計算する。
後半はそれを使ってDPする。kmjpさんのブログが詳しい。
http://kmjp.hatenablog.jp/entry/2016/12/15/0900

Indeedなう E. Page Rank

http://indeednow-finala-open.contest.atcoder.jp/submissions/1163550
連立方程式を解けって問題なので反復法で漸化式を更新しながら解く。
ループがO(10^10)になるが更新が疎+簡単なDPなので通る

HR Frog in Maze

ただの反復法ではダメで、行列累乗を使った反復法なら通る。
想定解はガウスの消去法

yukicoder No.195 フィボナッチ数列の理解(2)
[多分] SRM504.4 Div1 Hard TheTickertsDivOne

解説
https://topcoder.g.hatena.ne.jp/jackpersel/20110523/1306160504

[多分] SRM 590 Div1 Med XorCards

解説
http://kmjp.hatenablog.jp/entry/2013/09/11/1000