Divide by Zero 2017 and Codeforces Round #399 (Div. 1 + Div. 2, combined)

参加しました、結果は２完
http://codeforces.com/contest/768

A.o
B.o
C.x

Bがいつもより難しかった気がします
公式解説
Editorial Divide by Zero and Codeforces Round #399 (Div. 1+2, combined) - Codeforces

停滞気味なのでコードとちょっとしたコメントだけ
最近コンテストが多くて追いつかないです

A. Oath of the Night's Watch

配列に含まれる最大値の数と最小値の数を数えて、それを全体から引けば答えになる
ただし、最大値と最小値が一致するときのみ場合分けが必要（答えは０になる）

def solve():
    n = int(input())
    As = [int(i) for i in input().split()]
    As.sort()
    ans = 0

    if As[0] == As[-1]:
        print(0)
        return None

    ans += As.count(As[0])
    ans += As.count(As[-1])
    ans = n - ans

    print(ans)

if __name__ == '__main__':
    solve()

最大値と最小値を求めるだけならソートする必要は無かったんですが制約が緩いのでソートしました
O(nlogn)かかりますが組み込みのソートだからか実際はそんなに時間がかかるという印象がないです

B. Code For 1

最終的な配列の長さは2^(nのビット長さ) - 1になります
どうやってやったかというと、最終的な配列の添え字を元にそこが0か1かを判定する、っていうのをr - l回ループを回して足していきました
計算量は恐らくO((r - l)*logn)になります
二分木を書いてやると分かりやすかったです、ビット演算を使いました

実際に書いたコード

def solve():
    n, l, r = map(int, input().split())
    bit_len = len(bin(n)[2:])
    cnt = 0

    for i in range(l, r + 1):
        off = bit_len - 1
        for j in range(bit_len - 1):
            if i & (1 << j):
                break
            else:
                off -= 1
        cnt += (n >> off) & 1

    print(cnt)

if __name__ == '__main__':
    solve()

こうやって見ると割と短いというかシンプルですね……、コンテスト中は頭がこんがらがりそうでした
ただもうちょっとスマートなやり方というか、もっと計算量の少ないやり方はあるだろうなって思ってました
最終的な配列が1or0を逐一判断してカウントするっていうのは何か原始的ですよね
解説のコメントにO(logn)で出来るよ！って言ってすごいシンプルに説明してくれていた方がいたのでその方法でやってみました
直接[l, r]の和を求めるんじゃなくて、[1,l - 1]の和と[1, r]の和を求めて引くってやり方ですね、累積和法でよく見ます
そして左端からどこどこまでの和を求める関数は再帰を使って綺麗に書いてます、いいですね
関数を呼ぶごとにO(logn)しかかからない、かつ関数を呼ぶのは２回でいいのでO(logn)です、凄いですね

def solve():
    n, l, r = map(int, input().split())
    ans = f(n, r) - f(n, l - 1)

    print(ans)

def f(n, i):
    if i == 0:
        return 0

    bitlen = len(bin(n)) - 2
    mx = 2**bitlen

    if i == mx//2:
        return n//2 + n%2
    elif i < mx//2:
        return f(n//2, i)
    else:
        return n//2 + n%2 + f(n//2, i - mx//2)

if __name__ == '__main__':
    solve()

C. Jon Snow and his Favourite Number

よく分からなかったので適当に小さいケースで試したら何か偶奇の場合分けでいけるんじゃ？と思って提出したらpretestは通ったので
通るのかなーって思ったらやっぱり通らなかった、ですよね

前解説見てもよく分からなかったんですが今読んだら何となく分かってきました
暇を見つけてコーディングしたいと思います……ただこれO(1024 * k)でk <= 10^5だから結構ギリギリですね
少なくともpythonでは通ら無さそうです、pypyなら通るかな？
と思ったけど無理ぽいです、Atcoderのカスタムテストなら2 * 10^8回のループでも2s切るぐらいでかなり速いですが、codeforcesのpypyでは10^8回のループは4s超えますね……
となるとコーディングするならC++とかでやらないといけないですね……うーん

pythonで通してる人いるかなって思って見てみたら確かに通してますが、何か周期性を利用してますね
k % 64とかmin(k, 8 + k % 4)とか……良く分からないですけれど