lu100101の日記

勉強の記録

20210724

  • AtCoder
    • 競プロ典型 90問
    • ABC 211
      • Dがわかりそうで実装全然できず
        • 解けなきゃいけない問題だったっぽい……
      • 辺の重みが等しいときの最短経路問題はBFSでいいのか……
        • というかBFSの理解が浅い……

20210627

  • AtCoder
  • 今月はAtCoderに限らずすべての勉強においてさぼりすぎている。来月から頑張れるようにリハビリ……

20210606

20210530

  • AtCoder
    • 競プロ典型 90問
      • 012 Red Painting
        • 何も分からなかった
        • 連結判定はUnion-Find
          • Union-Find木はリンクと連結判定を高速で行えるデータ構造
        • Union-Findの実装を見ただけでAC取れる実装できたのはよかった
      • 013 Passing
      • 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やん解けなくてもいっか（）

20210523

  • AtCoder
    • 競プロ典型 90問
      • 009 Three Point Angle
        • N = 2000なので O(N^{3})はTLEするが O(N^{2} \log{N})なら間に合うことから、一つだけ二分探索という発想はできてもよかったはず。。。
        • 二分探索してくれる標準ライブラリbisectの存在を知った
      • 010 Score Sum Queries
        • さすがに簡単
      • 011 Gravy Jobs
        • 小問題 1しか通らないだろうなと思った、最初に思い付いた解法で小問題 2まで通った
        • 「 D_{i}の小さい順に仕事をする」、ということが分かったのならDPの発想があってもよかった