20210519 - lu100101の日記

AtCoder
- 競プロ典型 90問
  - 005 Restricted Digits
    - 小問題 2
      - 昨日行列計算が遅いと書いたがそれだけじゃなかった
      - ①累乗する行列が間違っていた
        
        解説には「dp[i][j]] -> dp[i+1][k]の遷移が存在する場合に第 $j$ 行第 $k$ 列が1になる」とあるが、正確には「dp[i][j] -> dp[i+1][k]の遷移が存在する場合に第 $j$ 行第 $k$ 列を+1する」だった
        
        思考停止よくない
      - ②forループは遅い、行列計算するならnumpy
      - ③numpyはデフォでは初期化時の値にあった型が選ばれる
        
        計算していく中でその型が引き継がれていくから、累乗など小さい値から始まって大きい値になる計算だと簡単にoverflowしてしまう
        
        初期化時にdtype="object"で桁無限のPythonオブジェクト型を指定する
        
        $N \times N$ の行列同士の積の計算量は一般的には $O(N^{3})$
    - 小問題 3
      - 思いつくわけないし、解説読んでもよくわからないし、実装もなんか通らない