AtCoder Beginner Contest 273 参加記録
2022/10/20 Eに永続スタックによる解答を追記
コンテストページ:Panasonic Programming Contest 2022(AtCoder Beginner Contest 273) - AtCoder
コンテスト中AC:A〜D
Eもコンテスト後に自力で解けました。
D - LRUD Instructions
壁を行と列にわけて保存し、移動方向に合わせて直近の壁を二分探索する、という手法は典型と言えると思います。
今回は、行及び列が非常に多いので、単純に行または列の番号をインデックスとした二次元配列に壁を保存していくことができません。
公式解説では、mapが遅いなと思うことがあり、座標圧縮で対応しました。しかし、その分、実装が複雑になってしまい手間取りました。
また、壁の記録には自作の平衡二分探索木(スプレー木)を使用しました(値の重複を許す、多重集合で実装しています)。ここでは詳細は書きませんが、「以下/未満の最大値を取得する」という操作をサポートします。
動作は保証できませんが、自由に使用して問題ありません。
Submission #35688615 - Panasonic Programming Contest 2022(AtCoder Beginner Contest 273)
E - Notebook
木っぽい感じだと思ったのですが、ポインタを使うような問題をあまり見たことがなかったので、ポインタを使用しない実装方法で解きました。
公式解説の補足を見て、永続スタックについて知りましたが、記載する実装方法はポインタを使用していないだけで、内容は永続スタックと同じでした。
永続スタックの参考↓
あなたの庭に永続データ構造を飾りませんか? - noshi91のメモ
では、実装方法を書きます。
まず、使用する配列や変数です。
- 配列:クエリで追加した値を追加順に保存する
- 変数:各クエリ処理において、の末尾の値が保存されているのインデックスを保存する
- 配列:にはが追加される直前のが保存されるような配列
- ハッシュマップ:ページをkeyとしてを保存する
と初期化しておきます。これはが空であることを示す番兵となります。
後述するを戻す処理をどれだけ行ってもに留まり続けることが可能です。
各クエリの処理です。
ADD x
の末尾にを追加します。の直前にの末尾であった値ののインデックスはなので、の末尾にを追加します。新たなはの末尾のインデックスとなるよう更新します。DELETE
現在のの末尾の値を削除する代わりに、1つ前に末尾だった値に戻ればよいです。すなわち、と更新します。SAVE y
ハッシュマップにをkeyとして現在のを保存します。すなわち、とします。LOAD z
ハッシュマップに保存した位置となるようにを更新します。すなわち、とします。なお、保存されていない場合は、としておけば良いです。
これで各クエリはで処理できます。
Submission #35754741 - Panasonic Programming Contest 2022(AtCoder Beginner Contest 273)
↓永続スタックの解答
Submission #35797075 - Panasonic Programming Contest 2022(AtCoder Beginner Contest 273)