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接続するわけではない。

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

programming_algorithm/contest_history/atcoder/2018/1208_abc115.txt · 最終更新: 2018/12/09 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0