2022-08-19 ABC237 の A, B, C, D, E を解いた
ABC237 : AtCoder Beginner Contest 237 の A, B, C, D, E を解いた。
- A - Not Overflow
https://atcoder.jp/contests/abc237/tasks/abc237_a
- 提出: https://atcoder.jp/contests/abc237/submissions/34142186
(-(2_i64.pow(31))..2_i64.pow(31)).contains(&n)
- B - Matrix Transposition
https://atcoder.jp/contests/abc237/tasks/abc237_b
- 提出: https://atcoder.jp/contests/abc237/submissions/34142236
- 二重ループで転置行列をつくって二重ループで出力するだけ
- C - kasaka
https://atcoder.jp/contests/abc237/tasks/abc237_c
- 提出: https://atcoder.jp/contests/abc237/submissions/34142346
- prefix の
'a'は増やせるので suffix の'a'はたくさんあっても無視できる - prefix の
'a'のほうが suffix の'a'より多いと No - prefix の
'a'が suffix の'a'と重なっている (すべて'a') と Yes - それ以外は prefix suffix の
'a'を捨てて回文判定すれば良い
- D - LR insertion
https://atcoder.jp/contests/abc237/tasks/abc237_d
- 提出: https://atcoder.jp/contests/abc237/submissions/34142418
- 逆順に走査する
- 次の要素 (
i - 1) の追加先をLRの逆にすれば良い VecDequeを使えば先頭・末尾への追加を効率よくできる- D の位置にしては簡単な問題
- E - Skiing
https://atcoder.jp/contests/abc237/tasks/abc237_e
- 提出: https://atcoder.jp/contests/abc237/submissions/34143167
- 本番では嘘解法で通していた
- その解法と同じ解法だと After_contest のケースで TLE になった
- 本番のものに対しての difficulty は 1208 だけど、 After_contest のケースを含めた本来の難易度だと水色の真ん中かそれ以上の難易度があると思う (体感)
- 公式の解説よりもユーザー解説のほうがわかりやすかった https://atcoder.jp/contests/abc237/editorial/3346
- 高さの差の絶対値でダイクストラ法で頂点 1 から各頂点への最短距離を求めておく
- 最短経路 d は上りの合計と下りの合計の和で、頂点 1 と各頂点の高さの差は上りの合計と下りの合計の差で、求めたい楽しさは下りの合計から上りの合計の倍を引いたものであることを式変形して求める
- 直感的に無駄に下ったり上ったりすると上りのマイナス分が大きくなるので上下の距離 (高さの差の絶対値) が小さいほうが良いという説明もわかりやすかった
今日のコミット。