Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12685 - Binary Tree (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12685

問題概要

無限に大きい $2$ 分木を考える.
各ノードは,左の子供ノード,右の子供ノード,上に親ノードを持っている.
ただし,ルートの親のノードはルートとみなす.
命令の列 $S$ と $T$ が与えられる.
命令はL, R, Uの3種類で,それぞれ,今いるノードから左,右,上のノードに移動することを意味する.
最初はルートにいて,命令列 $S$ を全部こなす.
その後,命令列 $T$ をこなすのだが,命令列 $T$ に関しては,各命令をこなすか,その命令をスキップするかを選ぶことができる.
全ての操作が終わった時に,最後にいること可能性のあるノードの数を mod $ 21092013$ で求める問題.
$S, T$ の命令の数はそれぞれ $10^5$ 以下

解法

まず,$S$ を眺めていって,Uでなければその命令を追加,Uなら最後に追加した命令を削除,として,
$S$ が終わった地点でのいる場所を,ルートからL, Rのみの列を用いて表しておく.
また,命令列 $T$ の各命令に対して,その後に出てくる一番最初の命令L, R, Uの場所を後ろからなぞって計算しておく.
$T$ のある場所以降で,LとRのみを用いて移動できるノードの数をDPで計算する.この時,上で計算した各命令が出てくる最初の場所を使えば $O(|T|)$ で計算できる.
まず,現在位置から,$1$ 歩左に行ってから,および,右に行ってから,その先に移動パターンをDP表から答えに足す.
後は,上に何回か移動した後,逆方向に進んでから,その先の移動パターンを足していく.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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