0.はじめに
落ちていくレートに歯止めを掛けたい今日この頃。
A~Cは簡単に解けて迎えたD問題。
最初の解法だとTLEだったので工夫してなんとか
ACまで持っていきましたが3分ほどオーバーし
あえなく3問まで。
レートは-21の711と、某コンビニエンスストアのようになりました。
21時過ぎに家に来た兄への対応が無ければ
間に合ったのにな・・・と思いました。
1. A - Is it rated?
今はレート外となってしまった懐かしいARCを題材にした問題。
XとRの値をもとに場合分けして判定結果を出力して終了。
https://atcoder.jp/contests/abc405/submissions/65643230
2.B - Not All
問題がややこしく感じましたが、まぁ、B問題。
制約も緩いので処理時間等気にせず分かりやすく実装しました。
【実装】
１）まずは、リストA内の数字毎の出現回数をリストLに集計。
２）リストLを1からMまで見ていき、出現回数０の
数値があれば、0を出力して終了。
３）リストＡを後ろから見ていき、リストＡの値に基づき
リストＬの出現回数をチェック
→出現回数が１なら、チェック回数を出力して終了
→1でなかったら（2以上）チェック回数を1マイナスする
https://atcoder.jp/contests/abc405/submissions/65649577
3.C - Sum of Product
制約から、普通にi×j回処理したらTLEなのは明白。
【考え方】
リストの数がA,B,C,Dの4つの場合
ＡＢ＋ＡＣ＋ＡＤ+ＢＣ＋ＢＤ＋ＣＤ
＝Ａ（Ｂ＋Ｃ＋Ｄ）+Ｂ（Ｃ＋Ｄ）+Ｃ（Ｄ）
となるので、リストＡの後ろからの累積和リストＢを作り
Ｂ＝[Ａ＋Ｂ＋Ｃ＋Ｄ,Ｂ＋Ｃ＋Ｄ,Ｃ＋Ｄ,Ｄ]
リストＡを先頭からＮ－１個目まで見ていき(index=i)
A[i]×B[i+1]を集計すれば、解が求まる。
後で解説を見て、別にリスト化しないでも、合計から、掛ける数を
引いていけばよかったことが分かりました。
https://atcoder.jp/contests/abc405/submissions/65660774
4.D - Escape Route
3分遅れでACとなった悔しい問題。
【考え方】
・各非常口から到達できるマスを幅優先で探索
・各非常口からの探索時にどの非常口から来たかの方向と
非常口からの移動距離を保存
・各非常口からの探索時にすでに他非常口からの到達が
出来てるマスであった場合、移動距離が少なければ上書きし
大きければそのルートの探索を終了する
上記で進めましたが、TLE
まぁ、上記方法だと、効率悪いのはわかっていたので
探索のチェックをキューで管理し、各非常口から
近いマスを埋めていく方式にかえてACとなりました。
https://atcoder.jp/contests/abc405/submissions/65694004
以上