AGC033 LRUD Game
概要
AGC033 B問題(600) LRUD Gameの解説をしたいと思います。
言語
問題
解法1 (嘘貪欲)
僕は、コンテスト中に嘘貪欲でACしてしまいました。 （自分の回答) https://atcoder.jp/contests/agc033/submissions/5262993
内容
先手が落とす方向を決めて、それを防ぐように後手の手を選ぶ。それをLRUDの４方向で試す
という方針で実装したけど、
先手「右に落とすよー」
後手「じゃー左に動かそ」
先手「やっぱ、左に落とすわー」
みたいなパターンだと、右に落とされてしまう。
(しかし、嘘貪欲だと、落とされない という答えを出す。
入力例
H,W,N=3,3,4
sr,sc=2,2
S-> DRLL
T-> RUDD
という入力で誤答してしまいます。(今回は、テストケースに入っていなかったため、ACになってしまいました。)
解法2
内容
youtubeの解説放送でもありましたが、手順を後ろから見ていく手法です。
横方向の移動と、縦方向の移動に分けて考えます。
生存可能な範囲を変数として持っていて、手に応じてその範囲を変化させていきます
後ろから手を見ていくので、最初の手まで見終わった時にスタート地点が生存可能な範囲に入っていれば、「落とされない」と答えを出すことができます。
(AC code with python)
atcoder.jp
終わりに
今後は証明のない嘘貪欲をしないように、気をつけます(反省)
