AGC049-C Robots

問題リンク

普通に難しかったんだけど黄 diff 前半… AGC 苦手すぎる

解法

ロボットを $0$ に到達させない方法は大きく分けて二つある。

• つぶす（他のロボットに踏ませて壊す）
• 縮める（ボールを書き換えて $1$ までしか到達しなくする）

まず、このままつぶされずに進めば $0$ に到達してしまうロボットと、そうでないロボットに分ける。

到達してしまう任意のロボットは、1個適当なボールを書き換えることでつぶすことができる。 また、到達してしまうロボットのうちひとつを縮めて到達しないようにすると、そのロボットより前からスタートする任意のロボットをつぶせる。

この2つを利用して、$0$ まで到達してしまうロボットを後ろから見て、そのロボットを縮めるか否かを選択すれば良い。

提出リンク

感想

頭がこんがらがる、非常に苦手なタイプ