phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

Google Code Jam 2019 Round 1B B. Draupnir

問題

「X-day ring」というものがあり、これは、X日ごとに分裂し、2倍の個数になるリングである。
最初は、1-day ringから6-day ringまでの6種類のリングがそれぞれ何個か(0個以上100個以下)ある。

今、1日目から500日目までのいずれかの日でのリングの合計数を2回だけ問い合わせることができる。
ただし、数が大きくなりすぎるため、2^63で割ったあまりが返ってくる。

最初の日(0日目)にあったリングのそれぞれの個数が何個だったかを答えよ。

制約

  • 1 <= T <= 50
  • 問い合わせ回数W = 2

解法

何日か経つと、リングの個数がかなり大きくなることがわかる。
また、2の累乗の倍数のいずれかになるため、0日目のi-day ringの個数がRiとすると、「(2^x) * Ri」のような形で書くことができる。

ここで、数が大きくなりすぎた場合、2^63で割ったあまりが返ってくることから、2^xの部分が2^63以上になったら2^63の倍数となるため、Riに関する要素が合計数に含まれなくなる。

また、0日目のリングの個数は100個以下であることがわかっているので、7bit以下で表現でき、「(2^x) * Ri」のxの部分がうまく7以上はなれるような日が見つけられれば、ビット部分からRiを求めることができる。

なので、「1-dayから3-dayが2^64の倍数となるような個数、かつ、4-dayから6-day ringが7bit以上離れるような日」で4,5,6-day ringの個数を求め、「1-dayから3-dayが7bit以上離れるような日の合計値から4-dayから6-day ringの個数を引いたもの」から1,2,3-day ringの個数を求めれば、0日目にあったリングの個数をすべて求められる。