2022-02-26 アルゴリズムと数学 演習問題集 056 - Recurrence Formula 2 を解いた
アルゴリズムと数学 演習問題集 056 - Recurrence Formula 2 を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_av
試したらできた……。問題の流れからすると解法は行列の累乗を使うと推測できる。前の 2 項をどうやって残すのか。たぶん 3 行 3 列にするのだろう。 (1,1) を a_n にしたい。すると 1 行目は a_{n-1} + a_{n-2} + a_{n-3} になるよう 1 1 1 とする。残りの 2 つはそれぞれ a_{n-2} と a_{n-3} をそのまま残したい。試していたらたまたまできた。
\begin{pmatrix}
1 & 1 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
\end{pmatrix}
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29649073
ABC241 で -19 。 C 問題では全探索できることに気づいていなかったのと count >= 4 で判定したために壁を含めてカウントしてしまっていて WA 。 D は考察は間違っていなかったのだけど実装でひたすらバグらせて時間ギリギリだった。たぶんぼくのレート的には E まで解かないといけなかった。
https://atcoder.jp/users/bouzuya/history/share/abc241
『 JUNK HEAD 』を観た。
『 Versioning in an Event Sourced System 』を読み進めている。
今日のコミット。