taki["blog"] = 2022

社会人8年目(東京5年目)の日常

2020/3/1 ABC157

久しぶりです.タイポ,変数名ミスなどでよく分からないWAを出しまくりました.表には復習したやつもあります.

f:id:takilog:20200303231418p:plain

  • Aは計算するだけでした.
  • Bも計算するだけでしたが,変数名をタイポして死亡しました.
  • Cは条件が緩かったので全探索(1桁なら0〜9,2桁なら10〜99みたいな)だと思いました.実装もほとんどあっていたのですが,WAが出まくって死亡しました.原因は変数名タイポでした(死にたい).
  • Dは最初問題の意味がよく分からなかったのですが,要するに到達可能な頂点数から自分とブロックを除けば良いので,計算はできます.問題は普通に実装するとTLEということです.
    • 最初はPypy3が死亡かと思ってC++でも死亡したので諦めました.
    • グラフアルゴは発想は良かったのですが,ダイクストラではなくて連結成分が大事でした.連結成分にして,同じ連結成分であるときにブロックを考慮するみたいな解き方です.
    • AtCoderでよく出てくるUnion Findでもいけるみたいです.僕は使い方よく分からないです.
  • Eはとりあえず何も分からなかったですが,TLを見たらセグメント木だったらしいです.

終わりです.