SRM 546 Div I - agwの日記

Single Round Match 546 Round 1

http://community.topcoder.com/stat?c=round_overview&rd=14738

練習。Div I Easyに挑戦した。

	Problem	Status	Points
250	KleofasTail	WA	N/A
500	FavouriteDigits	WA	N/A
1000	FleaCircus	Unopened

KleofasTail

http://community.topcoder.com/stat?c=problem_statement&pm=12049&rd=14738

3時間。練習。

例えば27のKleofas Tailとは以下のような数値となる

サンプル4に0を含む例がある
- 0は無限に続く
  - 0は偶数であるので、0の次の値は0/2だ

とりあえず書き出してみよう
- サンプル0はKleofas Tailに3を含む数値を探す問題だ
- ならば、3から遡ってみよう
- 数値iが奇数ならば、その親は2iだ
- 数値iが偶数ならば、その親は2iかi+1だ
書き出す書き出す...

全く規則性が分からない
数値ではなく式のまま書いてはどうだろうか
書き出す書き出す...

見えてきた
- xの係数が1である式はxのみ
- xの係数が2である式は2x、2x+1
- xの係数が4である式は4x、4x+1、4x+2、4x+3
- xの係数が4である式は8x、8x+1、8x+2、8x+3、8x+4、8x+5、8x+6、8x+7
  - 8x+7は図にないが、8x+6のみから派生することはすぐ確認できる
xの係数を2ⁱとすれば、範囲を以下のように表すことができる

上の例は奇数の数値から親を探索した例だ
- 偶数の場合はもっと幅の広い木となるはず
  - 初めに2つに分かれるからだ
  - 書いてみよう
書き出す書き出す...

- xの係数が1である式はx、x+1
- xの係数が2である式は2x、2x+1、2x+2、2x+3
- xの係数が4である式は4x、4x+1、4x+2、4x+3
- xの係数が4である式は8x、8x+1、8x+2、8x+3、8x+4、8x+5、8x+6、8x+7
xの係数を2ⁱとすれば、範囲を以下のように表すことができる

規則性は把握した
実装しよう
- xの係数を1、2、4、...と繰り上げ、各係数での範囲と[A, B]の重複している範囲を数え上げる

ここで一回実装し、システムテストを通した
- ここでの実装は最後の実装を2回続けて書いたようなものなので、掲載しない

他のコーダーはどう実装しているのだろう?
- SRM546 Div1 Easy(250) KleofasTail - 赤コーダーになりたいを読む
!
- すごい! すごい!
しかし実装を見てもよく分からない
真似をして2進数表記で考え直してみることにする

初めに取り上げた27を考える
- 27を2進数にすると、11011
- 27のKleofas Tailは以下のように求めることができる
  - 27のKleofas Tailには3が含まれるはずだ
  - 3になったら止めよう

52なども考えてみよう
- 3から遡って親を探索したときに書き出した数値の一つ
- 52のKleofas Tailには3が含まれるはずだ

強調すると3が導き出される様が見やすい

つまり、以下の数値はKleofas Tailに3が含まれる値であると言える

この条件を満たす数の範囲はやはり以下の式で求めることができる(式は再掲)

Kが奇数の場合も考える
偶数の場合は少し違ったのであった
- Kを6(110)として書き出してみる

実際は111(7)も考慮に入れなければならないので、以下の図のほうがより明らかに感じる

これを元に考えなければならない数値を考える

この条件を満たす数の範囲はやはり以下の式で求めることができる(式は再掲)

実装するときに考えた
- 「末尾に0が続いた場合、例えば100(4)の場合はどうすればよいのだろう...?」
この場合もやはり末尾の0だけを以下のように扱う
- 再下段は「1**」などとはならないことに注意

これを元に再実装を行った(システムテスト済)

class KleofasTail {
public:
  long long countGoodSequences(long long K, long long A, long long B) {
    if (K == 0)
      return B - A + 1;

    long long s = 0;

    for (int i = 0, j = 1 - K % 2; ; i ++, j ++) {
      long long l =  K << i;
      long long u = (K << i) + (1LL << j) - 1;

      if (B < l)
	break;

      if (std::max(l, A) <= std::min(u, B))
	s += std::min(u, B) - std::max(l, A) + 1;
    }
    return s;
  };