AtCoder が提供しているABC（AtCoder Beginner Contest）273 のE問題をC++とPythonで解いてみました。ABC273は、2022年10月15日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Notebook（Difficulty : 1624）
問題はリンク先をご覧ください。
数列をグラフ（木）に載せます。末尾の要素をノートで管理します。AtCoder Problems による Difficulty は、1624 でした。
解答案
数列をそのままノート（記憶場所）に格納しては、時間的に間に合いません（メモリも足りません）。問題を解くために以下のことが求められています。
- 末尾に要素を追加できる。
- 末尾の要素を削除する。その結果として、数列の末尾はひとつ前の要素になる。
- クエリ後に末尾の要素を出力する必要がある。つまり、ノートには数列全体を格納する必要はなく、末尾の情報だけを格納すればよい。
木構造のグラフを用います。木には以下の要素を格納します。
typedef struct {
int value;
int parent;
} NODE;value はその頂点が対応する要素の値を、parent は親頂点の場所を表します。親の頂点から子をたどる操作はなく、追加のみで子の要素が増えて移動するため、子の情報は持ちません。
C++ プログラム例（ABC273E）
頂点（型NODE）を配列として確保しておき、親ノードから、子ノードを追加していきます。
- 根として、値-1、自分自身を指すノードを設定します（20行目）。
- ADD：子ノードを追加します。現在のノード（末尾）を更新します。
- DELETE：末尾から親に移動します。子は削除しないで、使い捨てにします。
- SAVE：現在の末尾ノードの場所を記録します。ノートにはmapコンテナを使います。
- LOAD：書かれているノードの場所を戻します。ノートに記録がない場合は、mapコンテナの既定値0となります。これは根を指し、数列がないことに対応できています（－1を出力します）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef struct {
int value;
int parent;
} NODE;
int main()
{
cin.tie(nullptr);
ios::sync_with_stdio(false);
int q;
cin >> q;
vector<NODE> a(q + 1);
int now = 0;
int max_index = 0;
a[0] = {-1, now};
map<int, int> note;
for (int i = 0; i < q; ++i) {
string s;
cin >> s;
if (s == "ADD") {
int x;
cin >> x;
++max_index;
a[max_index] = {x, now};
now = max_index;
} else if (s == "DELETE") {
now = a[now].parent;
} else if (s == "SAVE") {
int y;
cin >> y;
note[y] = now;
} else if (s == "LOAD") {
int z;
cin >> z;
now = note[z];
}
cout << a[now].value << " \n"[i == q - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC273E）
Python 版では、map に相当する機能として defaultdict を使いました。基本的な考え方は、C++ と同じです。以下が Python プログラムです。
"""AtCoder Beginner Contest 273 E"""
from collections import defaultdict
q = int(input())
a = [(0, 0)] * (q + 1)
now = 0
max_index = 0
a[0] = (-1, now)
note = defaultdict(int)
result = []
for i in range(q):
query = input().split()
s = query[0]
if s == "ADD":
x = int(query[1])
max_index += 1
a[max_index] = (x, now)
now = max_index
elif s == "DELETE":
now = a[now][1]
elif s == "SAVE":
y = int(query[1])
note[y] = now
elif s == "LOAD":
z = int(query[1])
now = note[z]
result.append(a[now][0])
print(*result)こちらも「AC」と判定されました。
最後に
少し昔の問題ですが、木に必要な情報を載せて処理するという手順が学べました。次回、ABC353E問題（紹介記事）でこの考え方を再利用するため、この記事で紹介しました。
引き続き ABC の問題を紹介していきます。
