hotpepsiの練習帳

TCO15 Algorithm Round 1A

02:05

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

Easy (250)

問題

• 2つの数値について、10進数表記にしたとき共通する数字の数を類似性とする
• L以上R以下の異なる2つの数の類似性の最大値を求める

方針

• 各数値について0-9の有無をbit0-9に対応させて持っておき、全探索で間に合う
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/tco_2015/Similars.cpp

Medium (500)

問題

• N個の場所とN個のトークンがある
• それぞれの場所には矢印がついていて、いずれかの場所を指している
• 初期配置として0個以上のトークンを異なる場所に置く
• 各ターンでは、各場所のトークンを、矢印で指示された先に移動する
• トークンが同じ場所に置かれるとゲームオーバー
• ゲームオーバーにならないトークンの置き方の総数を求める

方針

• 全てのトークンを置いてKターンシミュレーションしてみる
• 場所が重なるものがあったら同じグループと見なす
• 同じグループは、どれか一つだけ置くか、または、置かない
• なので総数は(各グループの個数+1)の積
• Kが大きいがmin(N,K)ターンで良い
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/tco_2015/Autogame.cpp

結果

oo- +1

153.34 + 309.42 + 50 = 512.76pt 163rd/1195 rating 1459 -> 1543 (+84)

毎度TCOご祝儀。

参加者が少なくて1pt以上の人は全員通過。

http://togetter.com/li/807322