A - Water Station
バグが怖いので全探索しました
- 水が存在するすべての地点をlistに収め、距離が最小となる点をmin関数で求めた
B - ABCDEFG
dictとabsを使いました
C - Snuke the Cookie Picker
クッキーが存在する最[東西南北]端を求めて、欠けてる地点を全探索
- 上下左右にクッキーが2つ以上ある空白地点はすなわち答え、らしい
-
- コンテスト後にTwitterで知った
-
- 天才〜
D - Sleep Log
二分探索だとバグらせそうで怖かった
クエリ先読みをして座標圧縮を使った
- 高橋くんの睡眠状態が切り替わる時間とクエリで与えられる時間の和集合をとる
- その後座標圧縮
- 高橋くんの睡眠時間の累積和を求めておく
- このような前処理によって、クエリで左右の端が与えられた時、累積和の差を求めることで早く答えが出せる
-
- 簡単に書いたが、コンテスト中は結構悩んでしまった
-
- 競プロ筋が足りない……
E - Art Gallery on Graph
優先度付きキューを使った変則的なDFS
- Pythonではheapqが使える
1つの頂点を複数の警備員が見張っている場合もあるので注意
- 重複がある可能性をわかった上でheapqに格納
- 最も眼力が強いやつだけを考え
- あとは無視
-
- この処理についてよく考えずに提出したせいでWA
F - Dungeon Explore
インタラクティブ問題ということでめちゃくちゃ悩んでしまう
結局コンテスト中に解けなかった
- DFSをやりましょう
-
- 通ってきた道を覚えておく必要があるので注意
総括
冷えは回避
- インタラクティブ問題が課題
-
- 昔のABCにはインタラクティブ問題なんてなかったのだが……
-
- あまり構えすぎず、見慣れたアルゴリズムで解決できないか考えること
解ける問題を早解きすることで、崖問題に対して考察時間が長くとれ、それも解ける可能性がある？
- 取らぬ狸の皮算用
余談
多重ループする時にitertools.productを使うと、外側の変数に応じて内側のループを変えられないから不便に思った
- なので関数を作った
-
- ジェネレータは便利
- 提出 #42132418で使われている
-
- しかしこの例はitertools.productでもよかった
-
-
- 考えてみるとこの関数でないといけない問題があまり思いつかない
-
-
-
- 実務では関数に切り出せばよいし……
-