ABC 273 E — Notebook
考察
保存後に列を変更しても、保存した時点の列へ戻れるようにしたい。変更されるのは末尾だけなので、各要素に「一つ前の末尾」を記録して残しておけば、列全体をコピーせずに過去の状態を表せる。
クエリ数を とする。列を普通の配列で持ち、SAVEやLOADのたびに全要素をコピーすると、長い列の保存・復元が繰り返される場合に時間・空間とも最悪で になる。クエリ数は最大 なので、列の長さによらず処理する方法を考える。
ADDとDELETEは、末尾への追加・削除を行うスタックの操作である。例えば列 の末尾4に「一つ前は3」と記録しておけば、DELETEは3へ戻るだけでよい。ただし、削除した4の記録を消したり、後のADDで上書きしたりすると、保存していた へ戻れなくなる。そこでADDのたびに新しい節点を作り、作成済みの節点は変更しない。このように過去の版を残すデータ構造を、永続データ構造という。
列を末尾の節点番号で表す
空列を表す番兵の節点番号を root = 0 とする。節点 v には、追加した値 value[v] と、その直前の末尾の節点番号 parent[v] を持たせる。現在の末尾は current、ページ p に保存した末尾は連想配列の saved[p] で管理する。初期状態は次のとおりである。
value[root] = -1。空列の出力を表す。parent[root] = root。空列から親へ戻っても空列に留まる。current = root。savedは空で、未登録のページはrootを保存していると解釈する。
根 root から current への道にある値を、番兵を除いて根側から順に並べたものが現在の列になる。末尾の節点番号一つで、その列全体が定まる。ページに保存するのもこの番号であり、全版で共通の根 root 自体は変わらない。
四操作と答えの取り出し方
クエリを入力順に、次のように処理する。
ADD x: 未使用の節点番号vを取り、value[v] = x、parent[v] = currentとしてからcurrent = vにする。DELETE:current = parent[current]とする。節点自体は消さない。SAVE y:saved[y] = currentと代入する。同じページへの以前の保存は、この番号で上書きする。LOAD z: ページzが登録済みならcurrent = saved[z]、未登録ならcurrent = rootとする。
どの操作でも、直後の答えは value[current] である。SAVEやLOADの後も一つずつ記録し、全 個を空白区切りで出力する。
保存後の追加は別の枝になる
次の独自の小例では、節点番号をADDのたびに1、2、3と割り当てる。SAVEしたページ1の番号は、その後のADDやLOADでは変わらない。
| 操作 | current | 現在の列 |
|---|---|---|
ADD 3 | 1 | |
SAVE 1 | 1 | |
ADD 4 | 2 | |
LOAD 1 | 1 | |
ADD 5 | 3 | |
LOAD 1 | 1 |
最後までにできた木は次の形である。矢印は親から子への関係を表し、実装では逆向きの parent だけを持てばよい。
0: 番兵
└→ 1: 値3(ページ1の保存先)
├→ 2: 値4
└→ 3: 値5
列 と は、接頭辞 を表す節点1を共有している。ADD 5 は新しい節点3を作るだけで、節点1や2の値・親を変更しない。従って、再び LOAD 1 すれば列は に戻る。もし列 も別ページへ保存してあれば、節点2も残っているのでそちらへも戻れる。
典型の発動条件
永続stackとstructural sharing
末尾への追加・削除を行う列で、過去の版へ何度も戻り、そこからさらに更新したいときに使える。各要素に直前の末尾への参照を持たせ、既存節点へ書き込まずに新しい節点を追加することで、版どうしの共通部分を共有する。内部の任意位置も書き換える別問題では、この末尾だけの表現で十分かを改めて確認する。
疎なkey状態の連想配列
キーの範囲が大きく、実際に必要なキーがクエリ数以下なら連想配列を考える。この問題では ページすべてを確保せず、SAVEされたページだけに末尾の節点番号を対応させればよい。
問題固有の要素
未保存のページには空列が記録されているので、未登録のLOAD先は番兵と解釈する。また、空列をSAVEするときも root をそのまま保存でき、特別な印は要らない。
要求される出力が各操作直後の末尾だけであることにも注目する。列の表現には親をたどる道を使うが、答えを出すために道を実際にたどる必要はない。
正当性
「番兵を除く根から current への道の値列が現在の列に一致し、登録済みページの saved は最後にSAVEした列の末尾を指す」という不変条件を保つ。初めは current が root で、すべてのページも空列なので成立する。
ADDでは現在の末尾の子として値 x の新節点を作るため、道の末尾に x だけが加わる。DELETEでは親へ戻るので末尾の一要素だけが除かれる。空列でも parent[root] = root により、そのまま空列に留まる。value[root] = -1 だけでは親への移動先は定まらず、この親の定義が必要である。
SAVEは現在の列を表す番号を指定ページへ代入するので、同じページへの上書きも含めて保存内容が一致する。既存節点の値と親は変更しないため、保存済みの道は後のADDやDELETEで変わらない。LOADではその番号へ移ることで保存時の列になり、未保存なら root へ移ることで初期の空列になる。root を保存したページをLOADする場合も同じである。
従って四操作の後も不変条件が保たれる。空列以外では current の値が末尾であり、空列では value[root] が なので、毎回 value[current] を出力すれば正しい。
実装上の注意
- 節点番号は列の長さと区別する。DELETEやLOADで短い列へ戻っても、次のADDには未使用番号を割り当てる。節点を再利用して上書きすると保存済みの列が壊れる。
- ADDは高々 回なので、番兵を含めて 個分の
valueとparentの配列を用意できる。子の一覧は不要である。 - 空DELETEを分岐なしで扱うには、番兵の値だけでなく
parent[0] = 0も初期化する。 - 出力は全操作後の一個だけではなく、各操作直後の計 個である。バッファにまとめるなどして大量の出力に対応する。
復習の核
- 保存後も任意の過去状態から更新したいなら、保存する参照と、その先の共有部分を変えない方法を考える。
- 末尾だけを操作する列は、各要素に直前の末尾を持たせると、版全体を末尾の節点番号一つで表せる。
- 番兵は値だけでなく、境界で操作した後も正しい状態に留まるよう、参照先まで定義する。
計算量と制約
時間
番兵の初期化は 、ADDで使う配列をまとめて確保・初期化しても である。ADDとDELETE、各操作後の答えの取り出しは一回 。SAVEとLOADをハッシュマップで管理すると一回期待 なので、入力と 個の出力を含めて全体で期待 時間となる。ページの連想配列に平衡二分探索木を使うなら一回 、全体で最悪 時間である。
空間
番兵とADDで作る節点が高々 個、保存するページが高々 個で、空間計算量は 。全 個の出力をバッファに保持しても同じである。
制約との対応
クエリ数は 、追加値とページ番号は 。列をコピーする二乗の処理や全ページ分の配列を避け、クエリ数に比例する節点・ページ情報で処理できる。追加値は正なので番兵の と区別できる。
出典
- 公式問題(2026-07-24T23:59:30+09:00確認) — source-abc273-e-problem-fed53a2a982096aeb89f298579a1e809a95058a06ddf4fe75177d79e756a083a
- 個別公式解説(2026-07-24T23:59:30+09:00確認) — source-abc273-editorial-5023-f05e948a7eca80904f9ead71fc40f2c30993d9c1d91142ec2d2b7b341bb61399
分類・前提・執筆情報
掲載状態: 収録済み
最終確認:
学習上の位置付け
主題の単元: 永続data structure・structural sharing
- 主題
- 永続data structure・structural sharing: 変更pathだけを複製して未変更部分を共有し、各versionのrootから過去状態へアクセスする。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
- 追加で学ぶ技能
- 既習技能
執筆: abc-explanation-author1.1.1 / revision 4
学習の位置
体系上の位置: 永続data structure・structural sharing
- 変更pathだけを複製して未変更部分を共有し、各versionのrootから過去状態へアクセスする。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
学習記録
状況更新: 更新記録なし
復習設定更新: 更新記録なし
端末内の保存状態を確認しています。
要復習一覧 / 学習記録のバックアップ / 解説に戻る