hotpepsiの練習帳

SRM 604

math | 23:39

Div1 Easy (250) PowerOfThree

問題

• 4方向の移動を受け付けるロボットがいる
• ターンkに距離3^k移動できる
• 与えられた座標に移動可能かどうかを求める

方針

• 各桁が-1か+1の3進数みたいな感じ。平衡三進法というらしい。
• xとyを平衡三進法で表したとき、各桁がxとyどちらかだけに属すること
• x方向とy方向の移動をそれぞれビット化
• xとyが排他で、下位から全てのビットが連続していること
• Failed System Test
• 書き直し
• 一番下の桁から見ていく
• xとyを3で割った余りを調べる
• 片方だけ余りがあるならOK、そうでなければ不能
• 余りを加えて3で割っていく(余りが2のときは繰り下がりがあるので、そのぶんを加える)
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_604/PowerOfThree.cpp

結果

x-- 0pt 513rd/843 rating 1247 -> 1228 (-19)

余りの処理を間違って死。

Cの場合余りが数の正負に影響されるので、absで正にしておいたほうが楽。

http://togetter.com/li/614555