AtCoder Regular Contest 129 A - Smaller XOR 解けなかった方いますか？　僕はエスパーしました。

皆さんこんばんは。

ARC129お疲れ様でした！！

なんとか２完出来て耐えました。。

f:id:ryusuke_920:20211121230411p:plain — ARC129のコンテスト結果

所でA問題を皆さんどのようにして解きましたか？
僕はエスパーしました。

ということで
今回はエスパー記事第３弾です！！！！

↓今までのエスパー記事はこちら↓
ryusuke920.hatenablog.jp

それではまずは問題から見ていきましょう。

A - Smaller XOR

1. 問題の概要
2. 問題の制約・入力例
- 2-1. 問題の制約・入力例
2-2. 入力例
3. エスパー方法
4. ACコード
5. 最後に

1. 問題の概要

整数N, L, R が与えられます。
以下の条件を満たす整数 x の個数を数える問題

$\displaystyle L \leqq x \leqq R$
$\displaystyle (x \oplus N) < N$

2. 問題の制約・入力例

2-1. 問題の制約・入力例

$\displaystyle 1 \leqq N \leqq 10^{18}$
$\displaystyle 1 \leqq N \leqq 10^{18}$
$\displaystyle 入力される値は全て整数である$

2-2. 入力例

入力例1

$\displaystyle 2 \quad 1 \quad 2$

出力例1

$\displaystyle 1$

入力例2

$\displaystyle 10 \quad 2 \quad 19$

出力例2

$\displaystyle 10$

入力例3

$\displaystyle 1000000000000000000 \quad 1 \quad 1000000000000000000$

出力例3

$\displaystyle 847078495393153025$

3. エスパー方法

まずは実験です。
解けなかった方、ちゃんと実験しましたか？
実験はエスパーを行う上で本当に大切です。

今回の勝因は完全に実験です。

入力例1, 3は両極端なので今回は２を使って説明します。
すると、以下のような結果になります。

f:id:ryusuke_920:20211121230545j:plain — 入力例２の実行結果

もう見えましたよね？

これ、 $\displaystyle 2^{i}$ ずつ条件を満たすものと満たさないものがあります。

なので、 R の２進数の長さ分 for文を回して条件を満たしていれば、 $\displaystyle (min(R, 2^{i + 1}) - 1) - 2^{i} + 1$ をカウントするだけです。

4. ACコード

n, l, r = map(int,input().split())
 
def f(x):
    ans = 0
    for i in range(len(int(bin(x)[2:]))):
        if 2 ** i ^ n < n:
            ans += min(2 ** (i + 1) - 1, r) - 2 ** i + 1
    return ans
 
print(f(r) - f(l - 1))

5. 最後に

ここまでエスパー出来てるのになぜ２ペナしてる？と思う方いるかも知れません。
それは...

1 ~ R までの個数で求めていてずっと気づきませんでした！！！！！！！！！！！！！！！！！

1 ~ R で考えてもこの入力例が全て通ってしまうのは罠ですね...

最後までありがとうございました！