AtCoder ABC 115

久しぶりにABC全完しました。それだけではなく、30分切りのタイムが出せたり、パフォーマンス1600(ABCの上限)を出してレートが1200を超えて水色になったりと、嬉しいことずくめのコンテストでした。以下CとD問題の提出コードです。

C問題 (Christmas Eve)

N, K = map(int, input().split())
H = [int(input()) for h in range(N)]
H.sort()
 
Ans = H[K-1] - H[0]
for i in range(1, N-K+1):
    Ans = min(Ans, H[i+K-1]-H[i])
print(Ans)

K本の木を選んだ時その高さの差を最小にしたいです。木の高さの情報さえあれば並び方は不要であることがわかるので、昇順ソートをして順番にi番目～i+K-1番目の木の高さの差を見ていけばよいです。"ここに10万行の入力例を貼るわけにはいかないのです"ってなんかかわいいですよね。

D問題 (Christmas)

N, X = map(int, input().split())
 
Num = [1] 
for i in range(N):
    Num.append(3 + 2*Num[-1])
 
def B(L, X): #レベルLのバーガーの下からX層にあるパティの数
    if L == 0: return 1
    elif X == 1: return 0
    else:
        if X <= 1 + Num[L-1]:
            return B(L-1, X-1)
        elif X == 2 + Num[L-1]:
            return B(L-1, Num[L-1]) + 1
        elif X <= 2 + 2*Num[L-1]:
            return B(L-1, Num[L-1]) + 1 + B(L-1, X - 2 - Num[L-1])
        elif X == 3 + 2 * Num[L-1]:
            return 2*B(L-1, Num[L-1]) + 1
 
print(B(N, X))

解説と同じことをやっているだけなので正直書くことがないのですが…レベルLのバーガーの下からX層にあるパティの数をB(L, X)とします。レベルLのバーガーは、B-(L-1)d- P-(L-1)u-B、という構造になっています。ただし下側のレベルL-1のバーガーを(L-1)d、上側を(L-1)uとしています。するとX層目がどの層に当たるか場合分けすると、B(L-1, i)を用いてB(L, X)を表すことができます(詳しくはコードをみて)。あとは再帰的に答えを求めていけば十分高速に求められます。