きままにものづくり

日々の気付いたことなんかを書いてます。

SRM604Div1Easy

問題

無限の平面を考える。k=0から始まり、四方向のどれかに3^k必ず毎回移動するロボットが存在する。このロボットは(x, y)に到達することが可能か求めよ。

解法

到達可能な場合を考える。この時、(x,y)は以下となる。
 x = c_0*bit_0*3^0 + c_1*bit_1*3^1 + ... + c_n*bit_n*3^n
 y = c_0*\bar{bit_0}*3^0 + c_1*\bar{bit_1}*3^1 + ... + c_n*\bar{bit_n}*3^n
 c_kは+,-の符号を、bit_kは0,1を示す。
指数が0の部分を除けば3を共通項として持っているので、必ず割り切れるようになる。指数が0になっている項は、符号が-の場合は余りは2に、+の場合は1となる。この性質を利用し、xとyがゼロになるかを確認する。xとyのどちらかの余りは0になるはずなので、そうならない場合は到達不可能なケースとなる。

計算量

 log_3(max(x,y))

コード

広告を非表示にする