hotpepsiの練習帳

SRM 667

02:19

https://competitiveprogramming.info/topcoder/srm/round/16547/div/1

Div1 Easy (250) OrderOfOperations

問題

• N個の命令セットとM個のメモリセルがある
• ひとつの命令はいくつかのメモリにアクセスする
• 命令の実行時間は、アクセスされたことのないメモリの2乗である
• 各命令を1回ずつ全て実行するとき、実行時間の最小値を求める

方針

• 各メモリをビットで表す
• 全部のビットを立てるための最小コストを求める
• 最終的なビットマスクからDFSでコストを更新していく
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_667/OrderOfOperations.cpp

結果

o-- 113.86pt 189th/489 rating 1358 -> 1429 (+71)

ビットマスクは減る方向しかないので、使う順番とかどれを使ったのかは管理しなくていい。

探索してない人が意外と多く、チャレンジできたっぽい。

http://togetter.com/li/872475

SRM 666

01:12

https://competitiveprogramming.info/topcoder/srm/round/16515/div/1

Div1 Easy (222)

問題

• N個の頂点からなる木が与えられる
• 1ステップで辺を一つ移動できる
• ノード0からLステップで訪問できる異なる頂点の最大数を求める

方針

• (終了後)
• 一番遠い葉までの距離Dを求める
• 近いノードは往復してノード0に戻り、そのあと一番遠いノードに移動すればいい
• 残りのノード数は(N-D-1)個
• 近いところは(L-(N-D-1))÷2個訪問できる
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_666/WalkOverATree.cpp

結果

--- 0pt 186th/343 rating 1400 -> 1358 (-42)

全く思いつかなかった。良い問題。

http://togetter.com/li/865547

TCO15 Algorithm Round 2D

10:07

https://competitiveprogramming.info/topcoder/srm/round/16538/div/1

Easy (250) BalancedSubstrings

問題

• 長さNのてこがあり、0か1からなる文字列sとして与えられる
• 1の場所にはおもりがあるものとする
• 文字列sの部分文字列のうち、左右の重さがつりあうものの総数を求める

方針

• 中心の位置を決め打ちして全探索
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/tco_2015/BalancedSubstrings.cpp

結果

o-- 132.45pt 202nd/463 rating 1341 -> 1400 (+59)

tomerunさんが1位の回。

Round2、通過は無理だけど4回もあるので楽しめて良い。

http://togetter.com/li/863862

SRM 665

01:17

https://competitiveprogramming.info/topcoder/srm/round/16514/div/1

Div1 Easy (250) LuckySum

問題

• 4か7だけからなる数がラッキーナンバー
• ラッキーナンバー同士の和をラッキーサムとする
• 数値または?からなる文字列noteが与えられる
• ?は任意の数字、ただし先頭は0ではない
• noteの条件を満たす最小のラッキーサムを求める

方針

• (終了後)
• 上の桁と下の桁、7桁ずつに分割して考える
• 7桁までのラッキーナンバーを全列挙しておく
• 7桁以下ならテーブルひくだけ
• 下の桁で有効な和の組み合わせを全列挙する
• 上の桁で、有効な和の組み合わせを全列挙する
• その際、桁上がりの有無を両方試して、下の桁の有効なものと組み合わせる
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_665/LuckySum.cpp

結果

--- 0pt unrated

桁DPらしい。

テストケースの不備でdiv1はunrated。

http://togetter.com/li/859452

SRM 664

19:57

https://competitiveprogramming.info/topcoder/srm/round/16513/div/1

Div1 Easy (250) BearPlays

問題

• 何個かの石があり、2つの山にわける
• 数が少ないほうをX個、数が多いほうをY個とする
• Y個の山からX個の山にX個移動する操作をK回行う
• 少ないほうの山の数を求める

方針

• (終了後)
• 小さいほうを2倍していく
• 合計はA+Bで不変
• 2倍してMOD (A+B)取る操作を繰り返していることになる
• ので、modexpを計算する
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_664/BearPlays.cpp

結果

x-- 0pt 225th/473 rating 1362 -> 1343 (-19)

シンプルだけど難しい。撃墜祭り。

http://togetter.com/li/855325