Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2465-0a9811e8
この記事にトラックバックする(FC2ブログユーザー)

Timus 1992 - CVS (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1992

問題概要

クエリが与えられるのでそれをこなす問題.
最初クローン $1$ のみがいて,クローンを作った順に $2,3,\ldots$ と番号を付ける.
クエリは以下の $5$ 種類がある.
 learn $c_i$ $p_i$ : クローン $c_i$ が授業 $p_i$ を学ぶ
 rollback $c_i$ : クローン $c_i$ が最後に受けた授業を忘れる
 relearn $c_i$ : クローン $c_i$ が最後に行ったrollbackを忘れる
 clone $c_i$ : クローン $c_i$ と全く同じ状況を持つクローンを新しく作る
 check $c_i$ : クローン $c_i$ が最後に受けた授業を出力する(受けてなければbasicと出力する)
授業を新しく受けた場合,rollbackしてたログは全て削除されrelearnできなくなる.
クエリの数は $5 \times 10^5$ 以下.

解法

クエリ先読みできるので,クエリをクローンの種類 $c_i$ 別に分けておく.
クローンが新しく作られない場合は,スタックとrollbackを何回行われたかを覚えておけば良い.
また,クエリを逆に遡ることは簡単なので,新しくクローンが作られたときは,そのクローンに対するクエリを処理して,逆にさかのぼって戻ってきて,もともとのクローンの処理に戻るといった感じのDFSをすれば良い.
永続データ構造っぽくやっても良い.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2465-0a9811e8
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。