ABC-376

A

$URL\:\to$ https://atcoder.jp/contests/abc376/tasks/abc376_a

#愚直

N,C = Integer().content
T = IntegerList().content
t = 0
ans = 0
for i in range(N):
  if i==0:
    ans += 1
    t = T[i]
    continue
  if T[i]-t<C:continue
  else: ans += 1
  t = T[i]
print(ans)

解法

始めにボタンを押すとき、それよりも前に飴はもらっていないので必ず $+1$ される。飴をもらうたびに、貰った時間を更新し、ボタンを押した時間と最後に貰った時間の差が $C$ 秒以上ならカウンタを更新することで題意を満たすことができる。

B

$URL\:\to$ https://atcoder.jp/contests/abc376/tasks/abc376_b

#だるい

N,Q = Integer().content
LH,RH = 1,2
cnt = 0
for i in range(Q):
  H,T = String().content
  T = int(T)
  if H=='R':
    if T==RH: continue
    if LH<RH:
      if T<LH:
        cnt += T + N - RH
      elif LH<T<RH:
        cnt += RH - T
      else:
        cnt += T-RH
    else:
      if LH<T:
        cnt += RH-(T-N)
      elif RH < T < LH:
        cnt += T - RH
      else:
        cnt += RH - T
    RH = T
  if H=='L':
    if T==LH: continue
    if LH<RH:
      if T<LH:
        cnt += LH - T
      elif LH<T<RH:
        cnt += T - LH
      else:
        cnt += LH-(T-N)
    else:
      if LH<T:
        cnt += T-LH
      elif RH < T < LH:
        cnt += LH-T
      else:
        cnt += T+N-LH
    LH = T
print(cnt)

解法

動かす前、動かした後、反対の手の位置関係でただただ場合分けすると題意を満たすことができる。

C

$URL\:\to$ https://atcoder.jp/contests/abc376/tasks/abc376_c

#二分探索

def upperBound(list, target):
  left, right = -1, len(list)
  while right - left > 1:
    middle = left + (right - left)//2
    if list[middle] <= target: left = middle
    else: right = middle

  return right

N = Integer().content
A = IntegerList().content
B = IntegerList().content
A.sort()
B.sort()

Boxes = []

for i in range(N-1):
  if B[i] < A[i]:
    print(-1)
    exit(0)

for i in B: Boxes.append(upperBound(A, i))
Boxes.sort()

for i in range(-1-1, -(N), -1):
  if Boxes[i]>=Boxes[i+1]: Boxes[i]=Boxes[i+1]-1

for i in range(N):
  if i==N-1 or Boxes[i]!=i+1:
    print(SA[i])
    exit(0)

解法

まず、題意を満たせない条件を考えてみる。 $A,\;B$ をソートし、 $i(1 \to N-1)$ まで回したときに $1$ 回でも $B_{i} \lt A_{i}$ が成り立つとどれだけ大きい箱を購入しても題意を満たせないのは明らかである。

以降は $A,\;B$ はソート済みであるとして話を進める。ある $B_{i}$ に対して、入れることができる最大の $A_{i}$ のインデックスを二分探索のupperBoundの方で求め、別のリスト(Boxesと名付ける)に保管しておき、すべての $B_{i}$ に対して求めることができたら、Boxesをソートする。 Boxesを後ろから見ていき、 $Boxes_{i-1} \ge Boxes_{i}$ が成立するとき、 $Boxes_{i-1}=Boxes_{i}-1$ とすることで必ず $1 \to N$ のうちのどれかが欠けているので、その欠けている数字を $T$ とすると、答えは $A_{T}$ となる。証明などは省かせてもらったが、実際にコードを試してもらうと、言っている意味が分かってもらえると思う。

D

$URL\:\to$ https://atcoder.jp/contests/abc376/tasks/abc376_d

#BFS

N,M = Integer().content
G = directedGraph(N,M,False,True).graph

V = [False]*N
Q = deque(G[0])
V[0] = True
while Q:
  v,no = Q.popleft()
  V[v] = True
  for i in G[v]:
    if i[0]==0:
      print(no+2)
      exit(0)
    if V[i[0]] == False:
      Q.append((i[0],no+1))
      V[i[0]] = True
print(-1)

解法

問題を解いてみて、感じたのは結構典型的なBFSの問題であるということである。キューに $(1,1)=(Node, Value)$ を入れてBFSを開始し、 $1$ に帰ってきたらそこで終了し、その時の $Value$ を出力、すべての $Node$ を探索しても $1$ に帰ってこなかったら $-1$ を出力すると題意を満たせることができる。

E

$URL\:\to$