# AtCoder Regular Contest 060 review

## C: Tak and Cards – 高橋君とカード

• Dynamic programming

I could come up only full search using bit operation during the contest.

But it can be solved by DP. Below is full score (Section 3.3 of editorial) implementation.

## D: Digit Sum – 桁和

I came up different approach from editorial.

Let $$a_i$$ be $$i$$-th digit with base $$b$$. Then,

$$n = \sum_i b^i a_i$$

$$s = f(b, n) = \sum_i a_i$$

applies. If we subtract these equation, we obtain

$$n – s = \sum_i (b^i – 1) a_i$$

Both side should be integer, and right hand side can be divided by $$(b-1)$$. So $$b-1$$ is a divisor of $$n-s$$. To find out divisor of $$n-s$$, it is enough to scan from 1 to $$\sqrt{n-s}$$. The computational complexity is thus $$O (\sqrt{n-s})$$

## E: Tak and Hotels – 高橋君とホテル

During the contest, I was writing primitive solution. Its computational complexity is $$O (NQ)$$ and thus it can answer only small size problem 〜 $$10^3 * 10 ^3 = 10^6$$.

To solve big size solution, you beed a pre-calculation to prepare table r[k][i], explained in editorial.

Sample implementation is below.