連立方程式を使った解法について
- とりあえず、けんちょんさんの最強記事を読もう
- 一次連立方程式を解く
- ガウスの消去法（掃き出し法,O(N^3)）, 反復法（誤差に注意）のどちらでも解ける
- 反復法でやるときは行列累乗を使って2^20くらい回すといいかも
- 漸化式を作った時にDP更新とは違ってループしているようなものは連立方程式を解くかも
- 素晴らしい資料
- ライツアウト系に特化した問題集
- ガウスの消去法の良い教科書
- ガウスの除去法はK重対角行列であれば、O(N^2K)に削減できる 問題1 問題2（非想定解）
- mod2上でのカウスの消去法もよく出題される
問題
反復法
ガウスの消去法
- CF425 Vasya and Shifts 解説
- AOJ Find the Outlier 解説1 解説2 解説3
- yukicoder No.195 フィボナッチ数列の理解(2) 解説
- AOJ Strange Couple 解説1 解説2
わからない
- yukicoder No.195 フィボナッチ数列の理解(2) [難]
- SRM504.4 Div1 Hard TheTickertsDivOne [多分]
- SRM 590 Div1 Med XorCards [多分]
- SRM 512 Div1 Med SubFibonacci [多分]
以下、解説
解説
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
