AtCoder Beginner Contest 115 C,D
解説放送は無く、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接続するわけではない。
ところでパティとハンバーグの違いって、パン粉とかのツナギを使ってないのを特にパティって言うらしい。
