hotpepsiの練習帳

SRM 534 Div2

16:05

Easy (250) EllysDirectoryListing

問題

• ディレクトリのファイルのリストがある。
• リストの最後がカレントディレクトリとルートディレクトリでないとき、最初に見つかったディレクトリを末尾と交換する。
• それでもリストの最後がカレントディレクトリとルートディレクトリでないとき、最初に見つかったディレクトリを末尾のひとつ前と交換する。

方針

• シミュレーション
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_534/EllysDirectoryListing.cpp

Medium (500) EllysCheckers

問題

• N個のマスからなる盤面がある。
• マスは空または駒が置かれている。
• 駒の右が空いていれば駒を一つ右に移動できる。
• 駒の右とその右が駒でその右が空いていれば、駒を三つ移動できる。
• 盤面の一番右の駒は直ちに取り除かれる。
• 二人のプレーヤーで交互に移動操作をする。
• 動かせなかったら負けとするとき、最初のプレーヤーが勝つかどうかを求める。

方針

• メモ化
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_534/EllysCheckers.cpp

Hard (1000) EllysFiveFriends

問題

• Ellyたちは5人でゲームをする。
• 円陣を組み、それぞれ数値を持つ。
• 1ターンでは隣同士の任意の2人の数値をピックアップする。
• 両方の数値が奇数であれば「りんごアクション」で両方の数値から1を引くことができる。
• 両方の数値が1以上であれば「オレンジアクション」で両方の数値を1/2できる。
• 全員の数値がゼロになると勝利となる。
• 何通りの勝利パターン数があるかを求める。

方針

• メモ化再帰
• メモ化領域のサイズと、処理時間がけっこうきつい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_534/EllysFiveFriends.cpp

結果

225.30 + 310.77 + 50-25 = 561.07 87th rating 1152 -> 1196

限りなくブルーに近い緑

easyは、ディレクトリを消してから末尾に足しているのを撃墜した。TopCoderは解が決まっていて末尾の順序が違っても落ちるので、そこは狙っていた。

末尾がディレクトリの場合には先頭から2回ループする必要があるのだが、それをやってない人がいて、気づけなかった。まだまだチャレンジ精神が足りない。

mediumは2回連続メモ化再帰で解いたが、今回は偶数奇数判定すればよかった。まあ300点は取れたのでよしとする。