SAVE と LOAD の処理を高速にする方法を考えていたら、「これって Git みたいなものを作れ ってことか」と思い至った。
だったら 本物の Git を使っても解けるのでは？ と思い、やってみた。残念ながら例題以外は全て TLE になってしまったので、正しく解けているかは不明。
コード
公式解説の内容を Git の機能に置き換えていく。
- 根付き木 → コミットグラフ
- 頂点 → コミット
- 根 → initial commit
- 「コマ」 →
HEAD - ノートの各ページ → タグ（またはブランチ名）
あとは HEAD をひたすら動かせばいい。値はコミットメッセージに保存することにして、ファイルのバージョン管理を省く。
#!/bin/bash
set -eu
# 適当な作業用ディレクトリを作り移動しておく
cd $(mktemp -d)
{
# Git を初期化する
git init
git config --local user.name "atcoder"
git config --local user.email "atcoder@example.com"
# 根付き木の根を initial commit で表現する
git commit --allow-empty -m "-1"
git tag "root"
} > /dev/null
read n
for (( i = 0; i < $n ; i++ )); do
read op x
case ${op} in
ADD )
# 配列に push → コミットメッセージの形で数値を記録する
git commit --allow-empty -m "${x}"
;;
DELETE )
# 配列を pop → 直前のコミットを指し直す
git reset --hard HEAD~ || true
;;
SAVE )
# 配列を保存 → 現在のコミットにタグを付ける
git tag -d "page-${x}" || true
git tag "page-${x}"
;;
LOAD )
# 配列を復元 → タグを利用してコミットを指し直す
git reset --hard "page-${x}" || git reset --hard "root"
;;
esac
# 配列末尾を出力 → 現在指しているコミットから数値を取り出す
git show --no-patch --format=format:" %s" >> answer.txt
done > /dev/null 2>&1
# 解答を出力する（念のため末尾に改行を追加）
echo >> answer.txt
cat answer.txt
# （おまけ）コミットグラフを stderr に出す
# git reflog | awk '{ print $1 }' | xargs git log --graph --pretty='%h%d %s%n' | cat >&2
グラフ
スクリプト最終行をコメントアウト解除すると、完成した根付き木が見られる。入力例2だと以下のようになる。（コミットのハッシュ値は毎回変わる）
* fe6c1ec 4
|
| * 2e5f6a8 8
|/
|
* bcde297 7
|
* 1bc8440 (HEAD -> master, tag: page-5) 1
|
| * a709950 2
|/
|
* 5228b7c 5
|
* 43aa206 4
|
| * b7040b0 10
|/
|
| * 4033e27 3
|/
|
* 49347c6 4
|
* 830b062 (tag: root) -1
少し面白いことが 49347c6 で起きている。1番目と8番目のクエリは共に「 root を基点にして 4 を追加する」処理で、ふつうならコミットは別になる。しかし本スクリプトで実行すると秒単位での時刻も含めて完全に同じコミットになるため Git は区別していない。（ sleep を挟んだりすればコミットが分かれることを確認できる）
Ruby に翻訳
Git の語句を変数名などに使った。こちらは問題なく AC になる。
https://atcoder.jp/contests/abc273/submissions/35707481
answer = []
Commit = Struct.new(:message, :parent)
head = root = Commit.new(-1, nil)
tags = {}
n = gets.to_i
n.times do
op, x = gets.split
case op.to_sym
when :ADD
head = Commit.new(x.to_i, head)
when :DELETE
head = head.parent if head != root
when :SAVE
tags[x] = head
when :LOAD
head = tags[x] || root
end
answer << head.message
end
puts answer.join(" ")