AtCoder Beginner Contest 185の感想

ABC185に参加した。

AtCoder Beginner Contest 185 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – ABC Preparation

一番少ない問題数に合わせる。

a = list(map(int, input().split()))
ans = min(a)
print(ans)

B – Smartphone Addiction

愚直に実装する。

最初のカフェに着くまで、次のカフェに行くまで、最後のカフェから帰宅するまでにバッテリーが切れるかどうか判定する。

n, m, t = map(int, input().split())

now = 0
battery = n
ans = True
for _ in range(m):
    a, b = map(int, input().split())
    use = a - now
    battery -= use

    if battery <= 0:
        ans = False
        break

    charge = b - a
    battery = min(n, battery + charge)
    now = b

use = t - now
battery -= use
if battery <= 0:
    ans = False

print('Yes') if ans else print('No')

C – Duodecim Ferra

12分割するということは、11本の区切りを入れる場所を選択するということになる。

長さLの棒にはL-1箇所の仕切りを入れる候補があるので、ここから11本選ぶ組み合わせ数を求める。

from scipy.special import comb

l = int(input())

ans = comb(l - 1, 11, exact=True)
print(ans)

D – Stamp

連続する区間が最小になるようにはんこの幅kを決めればOK。

Aをソートしてから青と青の間隔(diff)を求め、最小値を絞り込んでいく。

左端(マス0)と右端(マスn+1)が青く塗られているものとして考えると楽になる。

コーナーケースをifで回避しながら愚直に実装していく。

import math

n, m = map(int, input().split())
a = list(map(int, input().split()))

if m == 0:
    print(1)
    exit()

if 1 not in a:
    a.append(0)
if n not in a:
    a.append(n + 1)

a.sort()

diff = [0] * (len(a) - 1)
for i in range((len(a) - 1)):
    diff[i] = a[i + 1] - a[i] - 1

k = set(diff)
if k == {0}:
    print(0)
    exit()

if 0 in k:
    k.remove(0)
if len(k) == 0:
    print(0)
    exit()

k = min(k)

ans = sum([math.ceil(i / k) for i in diff])
print(ans)

D問題のコーナーケースでてこずってしまい、緑が遠のいてしまった。


コメント

タイトルとURLをコピーしました