20210530 - lu100101の日記

AtCoder
- 競プロ典型 90問
  - 012 Red Painting
    - 何も分からなかった
    - 連結判定はUnion-Find
      - Union-Find木はリンクと連結判定を高速で行えるデータ構造
    - Union-Findの実装を見ただけでAC取れる実装できたのはよかった
  - 013 Passing
    - ダイクストラを2回やるだけ
  - 014 We Used to Sing a Song Together
    - ソートすればいんじゃねと思ったらそうだった
  - 015 Don't be too close
    - 愚直にDPしたらTLE、知ってた
    - 解説を読んだら一応実装できた
      - ステップ1
        
        調和級数になることは気づけなかった
        
        $N + \frac{N}{2} + \frac{N}{3} + ... + \frac{N}{N} = O(N\log{N})$ の証明は簡単
      - ステップ2
        
        差が $k$ 以上となるように $a$ 個のボールを選ぶ方法が ${}_{N- (k-1)(a-1)} C_{a}$ 通りであることが分からなかった
        
        組み合わせ ${}_n C_{r}$ を高速に求めるには逆元を用いる（参考）
  - 016 Minimum Coins
    - 全探索するだけ
- ABC 203
  - Dがさっぱり解けず、レート微減
    - 二分探索することはすぐに思いついたが、判定を高速でやる必要がわからず
    - 0/1にして和を取ることにすれば累積和が使えたのか……
      - 前処理して部分的に何かを求めるのを高速にしようと思ったが、思いつかなかった
    - 個々のパーツは分かる、知っているものだったが、組み合わせる必要がありゴールまでのルートが見えず手が出せなかったという感じ
    - 青diffやん解けなくてもいっか（）