n-knuu's logs

憧れ駆動。だいたい競プロ

Codeforces Round #308 Div.2 C - Vanya and Scales

問題

Codeforces Round #307(Div. 2) - C. Vanya and Scales
天秤があり、整数wとmが与えられる。重さm, w^0, w^1, w^2, ..., w^100のおもりを使って、天秤の両側を同じ重さにできるか。ただし、重さmのおもりは必ず使うものとする。

制約

2<=w<=10^9, 1<=m<=10^9

解法

重さw^0, w^1, w^2, ..., w^100のおもりは、w進数の10^0, 10^1, 10^2, ..., 10^100に相当する。
よって、重さw^0, w^1, w^2, ..., w^100のおもりでは、w進数の1と0を使った数しか表現できない。
ここで、mのw進数を考える。w^iの位をm_w[i]と置くと、天秤の両側を同じ重さにできるのは以下の2つのときである。

  1. 各iについて、w[i]が0もしくは1である
    • このときは、mを天秤の片側に置き、もう一方にm_w[i]が1であるような位について、w^iのおもりをおけばよい
  2. mのw進数に、w進数のw^0, w^1, w^2, ..., w^100をいくつか足して繰り上がりを発生させて、各iについて、m_w[i]を0もしくは1にできる
    • このときは、mを片方の天秤に置き、w^0の位から順番に、各iについて
      • m_w[i]が0ならなら何もしない
      • m_w[i]が1なら、mとは異なる側にw^iのおもりを置く
      • m_w[i]がw-1なら、mと同じ側にw^iを置いて繰り上がりを発生させる(つまりm_w[i+1]+=1とする)
      • m_w[i]がwなら、これはm^(i-1)の位からの繰り上がりによって、m^iの位にも繰り上がりが発生している(同様にm_w[i+1]+=1とする)
      • それ以外なら失敗

この制約では、mがwの和を超えることはない(10^9 < 2^100)なので、これでよい。

知見

n×(baseのexp乗) (ただし0 <= n < base)は、base進数のbase^expの位がnである、と言い換えられる。

コード

終わりに

図で説明すればよかった