AtCoder Beginner Contest 115 C,D

AtCoder Beginner Contest 115

解説放送は無く、pdfのみ。

C - Christmas Eve

問題

$N$ 本の木があり、 $i$ 番目の木は高さ $h_i$
$K$ 本を選んで電飾を施すが、出来るだけ近い高さの木を選びたい
選んだ $K$ 本の内、最も高い木と最も低い木の差が最小となるように選ぶと、その差はいくつか

解法

選ぶ木の中で最も低い木を固定すると、残りはそれより高い木の中で低い方から $K-1$ 本を選ぶのがよい。

よって、ソートして $i$ 番目と $i-K-1$ 番目の木の差を、1つ1つ調べればよい。

        
              n, k = map(int, input().split())
hhh = [int(input()) for _ in range(n)]
hhh.sort()
ans = float('inf')
for i in range(n - k + 1):
    ans = min(ans, hhh[i + k - 1] - hhh[i])
print(ans)

        
          関数型っぽく
          
              from itertools import starmap
from operator import sub
 
n, k = map(int, input().split())
hhh = sorted(map(int, (input() for _ in range(n))))
print(min(starmap(sub, zip(hhh[k - 1:], hhh))))

D - Christmas

問題

肉とパン（のみ）でハンバーガーを作ろう
レベル $L$ バーガーは、以下のようにして決まる
- レベル0バーガーは、肉1枚
- レベル $L$ バーガーは、「パン、レベル $L-1$ バーガー、肉、レベル $L-1$ バーガー、パン」を下から積み上げたもの
レベル $N$ バーガーの下から $X$ 層には、肉が何枚含まれるか？
$1 \le N \le 50$
$1 \le X \le (レベルNバーガーの層の総数)$

例

P:肉, B:パン
レベル0バーガー  P
レベル1バーガー  B P P P B
レベル2バーガー  B BPPPB P BPPPB B
レベル3バーガー  B BBPPPBPBPPPBB P BBPPPBPBPPPBB B
...

解法

レベル50バーガーは $4.5 \times 10^{15}$ 層にもなるので、実際に1枚1枚確かめるのは無理。

ただ、バーガーの高さと、含まれる肉の総数は簡単に計算できる。

$\begin{eqnarray} レベルLバーガーの高さ &=& レベル(L-1)バーガーの高さ \times 2 + 3 \\ レベルLバーガーの肉数 &=& レベル(L-1)バーガーの肉数 \times 2 + 1 \end{eqnarray}$

なので、レベル $L$ バーガーを半分に割った時、 $X$ 層というのが下半分で終わるのか、上半分まで届くのかも分かる。二分探索（二分集計？）で答えを求める。

下半分で終わるなら、レベル $L-1$ バーガーの下から $X-1$ 層を調べればよい。（レベル $L$ バーガーで追加したパン1枚分を除いている）

(L Burger)
---Buns---
..........
..........
L-1 Burger
..........           
..........
--Patty---      →  
..........          ---Buns---
..........  -       L-2 Burger  -
L-1 Burger  |       --Patty---  |
..........  |X      L-2 Burger  | X-1
..........  |       ---Buns---  -
---Buns---  -

上半分まで届くなら、下に挟んだレベル $L-1$ バーガーが丸ごと含まれるのと、真ん中に挟んだ1枚分と、さらに上に挟んだレベル $L-1$ バーガーの中で何層かの合計となる。何層かというと、 $X-(レベルL-1バーガーの高さ)-2$ となる。

これを再帰的に求めることで、答えとなる。

レベル $L$ バーガーの上から $L$ 枚と下から $L$ 枚はパンなので、再帰的に求める中で $X$ がその範囲に入ったら答えが確定する。上から $L$ 枚なら $L$ バーガーの肉は全て含まれ、下から $L$ 枚なら全く含まれない。

        
              n, x = map(int, input().split())
 
heights = [1]
putties = [1]
for _ in range(50):
    heights.append(heights[-1] * 2 + 3)
    putties.append(putties[-1] * 2 + 1)
 
def burger(l, y):
    if l == 0:
        return y
    if y <= l:
        return 0
    hl = heights[l]
    if y >= hl - l:
        return putties[l]
 
    if hl // 2 + 1 <= y:
        return putties[l - 1] + 1 + burger(l - 1, y - (hl // 2 + 1))
 
    return burger(l - 1, y - 1)
 
print(burger(n, x))

Pattyの綴りの間違いは気にしてはいけない。SSH接続するわけではない。

ところでパティとハンバーグの違いって、パン粉とかのツナギを使ってないのを特にパティって言うらしい。