20210220 - lu100101の日記

AtCoder
- グラフの典型問題を解いてみる
- ABC 035 D トレジャーハント
  - 頂点1始点のダイクストラ×滞在先N頂点全探索で50点はとれた
  - これだと $O(NM\log N)$ でTLE
  - 帰り道は辺の向きがすべて逆のグラフに対して頂点1始点の最短路問題を解けば一回だけでよくなり $O(M\log N)$ で収まる
  - 非負の重み付きグラフの最短路問題はダイクストラ
  - Pythonではheapqを用いて $O(M\log N)$ （ループの中に入れてはいけない）
  - 帰り道を逆向きのグラフに対する単一始点最短路問題を解くことで求める解法は見たことあるし典型
- ABC 051 D Candidates of No Shortest Paths
  - 最短路の経路を復元するのができなかったが、復元しなくてもできなくてもできるらしい（以下）
  - 頂点iと頂点jを結ぶ辺が頂点sから頂点tへの最短経路に含まれるとき、次の式が成り立つ（逆も成り立つ）
    - dist( $s, i$ ) + edge( $i, j$ ) + dist( $j, t$ ) = dist( $s, t$ )
  - 全頂点からの最短路問題を解いてから上を全辺×2頂点 $s, t$ について全探索（ $O(MN^{2})$ ）
  - 下の式でも可（）
    - dist( $s, i$ ) + edge( $i, j$ ) = dist( $s, j$ )
- ABC 061 D Score Attack
  - 重みの符号を変えてベルマンフォードをするというAtCoder的な（？）発想もできて正解かと思いきやいくつかでWA
  - うち2つはINFの値が小さすぎた
    - 今回の問題では $-N\min c_{i}$ （=10¹²）より大きくとらなければならなかった
    - float('inf')を使えばよい
  - 残りの3つはinfを出力するときの条件考慮が足りなかった
    - 通常のベルマンフォードでは始点からたどり着ける負閉路をすべて検出するが、今回は終点が頂点 $N$ に決まっているため、頂点 $N$ にたどり着ける負閉路のみを検出しなければならない
  - 参考：AtCoder ABC 061 D - Score Attack (青色, 400 点) - けんちょんの競プロ精進記録
ABC 192
- 完全に上振れた。初のA-E5完で初の水色パフォ通り越して初の青パフォで緑になった
- B uNrEaDaBlE sTrInG：こういうの内包表記で書けるようにしたい
- C Kaprekar Number： $K=0$ の考慮漏れで1ペナ
- D Base n：公式解説と違う
  - 最上位の数と桁数からだいたいの当たりをつけて線形探索したけど、公式解説のように二分探索した方が速い
  - メインの処理をできない場合の考慮漏れで1ペナ、 $|X|=1$ の時の考慮漏れで2ペナ
- E Train：辺の重みに電車が来るまでの時間を足して（cost += -dist[v] + % k）ダイクストラで最短路問題を解くだけ
  - 今日グラフの典型問題を練習した甲斐あった
- そろそろコーナーケースの考慮を真面目にやらないとむやみにスコアを落としてしまう気がする
- いいパフォーマンスも出したし、資格試験ラッシュ終わるまで休止してもいいかもしれない
『アルゴリズムとデータ構造』
- Chap. 18 難問対策
- 読み終わったけど最後2章は全く分からなかった