geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

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が遅いなと思うことがあり、座標圧縮で対応しました。しかし、その分、実装が複雑になってしまい手間取りました。

また、壁の記録には自作の平衡二分探索木(スプレー木)を使用しました(値の重複を許す、多重集合で実装しています)。ここでは詳細は書きませんが、「x以下/未満の最大値を取得する」という操作をサポートします。
動作は保証できませんが、自由に使用して問題ありません。
Submission #35688615 - Panasonic Programming Contest 2022(AtCoder Beginner Contest 273)

E - Notebook

木っぽい感じだと思ったのですが、ポインタを使うような問題をあまり見たことがなかったので、ポインタを使用しない実装方法で解きました。

公式解説の補足を見て、永続スタックについて知りましたが、記載する実装方法はポインタを使用していないだけで、内容は永続スタックと同じでした。

永続スタックの参考↓
あなたの庭に永続データ構造を飾りませんか? - noshi91のメモ

では、実装方法を書きます。

まず、使用する配列や変数です。
- 配列V:クエリで追加した値を追加順に保存する
- 変数cur:各クエリ処理において、Aの末尾の値が保存されているVのインデックスを保存する
- 配列BKBK_iにはV_iが追加される直前のcurが保存されるような配列
- ハッシュマップM:ページをkeyとしてcurを保存する

V_0 = -1,\ BK_0 = 0と初期化しておきます。これはAが空であることを示す番兵となります。
後述するcurを戻す処理をどれだけ行ってもV_0に留まり続けることが可能です。

各クエリの処理です。

  • ADD x
    Vの末尾にxを追加します。xの直前にAの末尾であった値のVのインデックスはcurなので、BKの末尾にcurを追加します。新たなcurVの末尾のインデックスとなるよう更新します。

  • DELETE
    現在のAの末尾の値V_{cur}を削除する代わりに、1つ前に末尾だった値に戻ればよいです。すなわち、cur\leftarrow BK_{cur}と更新します。

  • SAVE y
    ハッシュマップにyをkeyとして現在のcurを保存します。すなわち、M_y \leftarrow curとします。

  • LOAD z
    ハッシュマップに保存した位置となるようにcurを更新します。すなわち、cur\leftarrow M_zとします。なお、保存されていない場合は、cur\leftarrow 0としておけば良いです。

これで各クエリはO(1)で処理できます。

Submission #35754741 - Panasonic Programming Contest 2022(AtCoder Beginner Contest 273)

↓永続スタックの解答
Submission #35797075 - Panasonic Programming Contest 2022(AtCoder Beginner Contest 273)