読者です 読者をやめる 読者になる 読者になる

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

hamayanhamayan's blog

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

競技プログラミング

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

  • 一次連立方程式を解く
  • ガウスの消去法, 反復法(誤差に注意)のどちらでも解ける
  • 反復法で10^4ループぐらいすれば十分な精度が得られそう?(初期値も適当で大丈夫そう。誤差10^-9以内でもACできた)
  • 漸化式を作った時にDP更新とは違ってループしているようなものは連立方程式を解くかも

問題

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

http://yukicoder.me/problems/129

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

http://yukicoder.me/problems/no/463

[多分] SRM504.4 Div1 Hard TheTickertsDivOne

https://community.topcoder.com/stat?c=problem_statement&pm=11098

[多分] SRM 512 Div1 Med SubFibonacci

https://community.topcoder.com/stat?c=problem_statement&pm=11288&rd=14537


以下、解説























解説

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なので通る

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