AtCoder Regular Contest 060 review

Link

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.

 

 

Sponsored Links

Leave a Reply

Your email address will not be published.