lu100101の日記

勉強の記録

20210522

AtCoder
- 競プロ典型 90問
  - 006 Smallest Subsequence
    - 解ける気がせん
    - 辞書順最小は前から貪欲法、らしい
    - 文字列→数値はord()、数値→文字列はchr()
    - 前計算なしの解法もあるっぽい（https://github.com/ryusuke920/kyopro_educational_90_python/blob/main/solve_python/006.py）
  - 007 CP Classes
  - ソートしてから二分探索するだけだったのに時間かかってしまった
  - 008 AtCounter
  - dpっぽいな～と思ったけど解けず、、、
  - 解けなきゃまずい
- ABC 202
  - 水パフォで緑に戻った
  - E Count Descendantsは普通にむずそう

20210519

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
      - 思いつくわけないし、解説読んでもよくわからないし、実装もなんか通らない

20210518

AtCoder
- 競プロ典型 90問
  - 004 Cross Sum
    - さすがに簡単
  - 005 Restricted Digits
    - 全然わからん
    - 小問題 1
      - 余りの情報を保持した桁DPをすればいいらしい（参考）
      - 計算量は $O(NBK)$
    - 小問題 2
      - 数学じゃん、行列累乗というらしい
      - 書けたは書けたが遅くてTLEした、たぶん行列計算が遅い

20210516

AtCoder
- ABC 201
  - D Game in Momotetsu World
    - こういう解法をミニマックス法というらしい（参考）
    - 上記実装でも通らなかった
      - REは再帰上限のせい
      - 上限あげると今度はTLE
      - PyPyは再帰が遅く、やめた方がいいらしい
    - 単純にforループでDPを逆向きに進めればいい
- ARC 118
  - A Tax Included Price
    - math.floor()とかint()ではなく//を使うべき
  - B Village of M People
    - ソートに使う値を愚直に小数にするのではなく整数のままにするだけでよかった
    - 解法が分かっていただけに悔しい
  - とにかく小数を扱うのを避ける！
- 競プロ典型 90問
  - 001 Yokan Party
    - 答えになりうる値を二分探索という競プロっぽいことができた
  - 002 Encyclopedia of Parentheses
    - itertools.productで全列挙
  - 003 Longest Circular Road
    - 最も長いパス（木の直径というらしい）を探せばよいことは分かったが実装が全然できない
    - 基本的なDFSだしそろそろ身につけたいところ
    - 木の直径を求めるには最短距離の最大値探索を2回やればよい

20210515

AtCoder
- ABC 201
  - C Secret Number
    - 最初、数学的に考えてしまったが、10000通り全探索でいけることに気づけた
    - 最初からその方針で行けてれば10分くらい早かったかも
    - 実装に多少手こずった
  - D Game in Momotetsu World
    - 最適化戦略も分からず、実装も分からないだろうと思い40分以上残して退散
    - 解説を読んで実装してみたがTLE祭り……

20210509

AtCoder
- 昨日さぼったのを一応解いておく
- ABC 200
  - C Ringo's Favorite Numbers 2
    - 簡単
  - D Happy Birthday! 2
    - 瞬殺ではなかったが、競プロっぽい問題を解けて嬉しい
- ARC118
  - 初めて一問も解けなかった
  - 両方ともコーナーケースにやられた

20210505

AtCoder
- 休んでる間のABCとARCの300, 400点問題埋め
  - ABC 199
    - C IPFL
      - listのset itemは $O(1)$ なのを忘れて無理じゃね？と思ってしまった……
      - 反転しているかどうかの情報を保持して $T_{i} = 1$ の時の処理を場合分けで記述する、って確かに当たり前だよなあ
    - D RGB Coloring 2
      - ムズイ、全然わからんかった
      - 参考