ABC134 write up

B - Golden Apple

監視員は$2D+1$本の木を監視できる。
ちょうど監視範囲が被らないように監視員を配置すればよいので、ceil(N/2D+1)を計算すればよい。(ceil=切り上げ)

from math import ceil
 
n, d = map(int, input().split())

print(ceil(n/(2*d+1))

C - Exception Handling

$A_i$の中で最大の要素$A_n$と2番目に大きい要素$A_m$を求めておく。
n番目は$A_m$, それ以外では$A_n$を出力すればよい。

from sys import stdin

n = int(stdin.readline())
a = [int(stdin.readline()) for _ in range(n)]

b = a.copy()
m1 = max(b) # 最大の要素
b.remove(m1)
m2 = max(b) # 2番目に大きい要素

for i in range(n):
  if a[i] == m1:
    print(m2)
  else:
    print(m1)

D - Preparing Boxes

考え中

E - Sequence Decomposing

数列$A$の頭から順に$A_i$をどの色にするか決めていく。
$A_1, \dots, A_{i-1}$の配色について、各色について一番大きな数字のリスト$L$を持っておく。
この時、

• $\min L \ge A_i$ であれば、$A_i$には新しい色を割り振る
  • そもそも既存の色を割り振れないので新しい色を付ける
• $\min L < A_i$ であれば、$A_i$には$\max \{ l \in L ;, l < A_i \}$を実現する$l$に振られている色を割り振る
  • 既存の色で$A_i$に割り振れるのは$\{ l \in L ; , l < A_i \}$に割り振られている色であることに注意
  • $L$に含まれる数字が出来るだけ小さい方が新しい色を割り振らずに済むので、一番効率がいいものを考えると最大の数に割り振られている色をつけるのがよい

とすることで効率よく色を割り振ることができる。

from sys import stdin
from bisect import bisect_left
from collections import deque
 
n = int(input())
a = [int(stdin.readline()) for _ in range(n)]
 
l = deque()
 
for i in range(n):
  n = bisect_left(l, a[i])
  if n == 0:
    l.appendleft(a[i])
  else:
    l[n - 1] = a[i]
 
print(len(l))