ABC376参加記録 by Python

リアルタイムに解けた問題

A - Candy Button

問題文

不思議なボタンがあります。このボタンを押すと飴を1つもらえますが、前回飴をもらってからの経過時間が$C$秒未満である場合はもらえません。

高橋くんはこのボタンを$N$回押してみることにしました。$i$回目にボタンを押すのは今から$T_{i}$秒後です。

高橋くんは何個の飴をもらうことができますか？

制約

• $1 \leq N \leq 100$
• $1 \leq C \leq 1000$
• $0 \leq T_{i} \leq T_{2} \leq ‥ \leq T_{N} \leq 1000$
• 入力は全て整数

アルゴリズム

Tに対してループを回し、next_get_time以上の数値であれば飴がもらえる。飴をもらうごとに次にもらえる時間を記録。

ソースコード

N, C = map(int, input().split())

T = list(map(int, input().split()))

next_get_time = 0

get_candy = 0

for i in range(len(T)):
  if T[i] >= next_get_time:
      get_candy += 1
      next_get_time = T[i] + C

print(get_candy)

B - Hands on Ring(Easy)

問題文

注：この問題はF問題とほぼ同じ設定です。本文中で太字で示されている部分および制約のみが異なります。

あなたはアルリングを両手で握っています。このリングは$N(N \geq3)$個のパーツ$1,2,...,N$によって構成されており、パーツ$i$とパーツ$i+1(1 \leq i \leq N-1)$、およびパーツ１とパーツNがそれぞれ隣接しています。

最初、左手はパーツ１を、右手はパーツ２を握っています。あなたは、1回の操作で以下のことを行えます。

• 片方の手を、今握っているパーツに隣接するいずれかのパーツに移動する。ただし、移動先にもう一方の手がない場合に限る。

以下の図（この記事では省略）は、初期状態およびそこから行える操作と行えない操作の例を示したもので、リングの各パーツに書き込まれた数はそのパーツの番号を、Lと書かれた丸は左手を、Rと書かれた丸は右手を示しています。

あなたは今から与えられる$Q$個の指示に順番に従う必要があります。$i(1 \leq i \leq Q)$個目の指示は文字$H_{i}$および整数$T_{i}$によって表され、その意味は以下の通りです：

• 操作を何回か（０回でもよい）行うことで、$H_{i}$がLならば左手、Rならば右手が、パーツ$T_{i}$を握っている状態にする。このとき、$H_{i}$によって指定された手ではない方の手を動かしてはならない。

なお、達成可能な指示しか与えられないことが保証されます。
（詳細があるがこの記事では省略）

すべての指示に従うために必要な操作回数の合計の最小値を求めてください。

制約

• $3 \leq N \leq 100$
• $1 \leq Q \leq 100$
• $H_{i}$はLまたはR
• $1 \leq T_{i} \leq N$
• $N,Q,T_{i}$は整数
• 達成可能な指示しか与えられない（詳細は問題ページを参照）

アルゴリズム

愚直に試行回数を求める。具体的には試行回数ではなく、手の移動距離を求める。動かしたい位置と手の現在地のそれぞれの数値の大小を比較。その結果に応じて、ringリストに対するスライシングを変え、スライシングした配列のなかに、もう一方の手が含まれているかで、動かしたい位置に時計回りで行くのか、反時計回りで行くのかを決め、その移動距離を累積していく。

ソースコード

N, Q = map(int, input().split())

ring = []
for i in range(N):
  if i == 0:
    ring.append('L')
  elif i == 1:
    ring.append('R')
  else:
    ring.append('.')
    
left_hand_pos = 0
right_hand_pos = 1

move = 0 
  
for i in range(Q):
  H, T = input().split()
  T = int(T) - 1
  if H == 'R':
    if T > right_hand_pos:
      if 'L' not in ring[right_hand_pos:T]:
        move += abs(T - right_hand_pos)
        ring[T] = 'R'
        ring[right_hand_pos] = '.'
        right_hand_pos = T
      else:
        move += abs(N - (T - right_hand_pos))
        ring[T] = 'R'
        ring[right_hand_pos] = '.'
        right_hand_pos = T
    elif T < right_hand_pos:
      if 'L' not in ring[T:right_hand_pos]:
        move += abs(right_hand_pos - T)
        ring[T] = 'R'
        ring[right_hand_pos] = '.'
        right_hand_pos = T
      else:
        move += abs(N - (right_hand_pos - T))
        ring[T] = 'R'
        ring[right_hand_pos] = '.'
        right_hand_pos = T
  else:
    if T > left_hand_pos:
      if 'R' not in ring[left_hand_pos:T]:
        move += abs(T - left_hand_pos)
        ring[T] = 'L'
        ring[left_hand_pos] = '.'
        left_hand_pos = T
      else:
        move += abs(N - (T - left_hand_pos))
        ring[T] = 'L'
        ring[left_hand_pos] = '.'
        left_hand_pos = T
    elif T < left_hand_pos:
      if 'R' not in ring[T:left_hand_pos]:
        move += abs(left_hand_pos - T)
        ring[T] = 'L'
        ring[left_hand_pos] = '.'
        left_hand_pos = T
      else:
        move += abs(N - (left_hand_pos - T))
        ring[T] = 'L'
        ring[left_hand_pos] = '.'
        left_hand_pos = T
        
print(move)

C - Prepare Another Box

問題文

$1$から$N$までの番号が付けられた$N$個のおもちゃと、$1$から$N-1$までの番号が付けられた$N-1$個の箱があります。おもちゃ$i(1 \leq i \leq N)$の大きさは$A_i$、箱$i(i \leq i \leq N-1)$の大きさは$B_{i}$です。

すべてのおもちゃを別々の箱にしまいたいと考えている高橋君は、今から以下の操作を順に行うことにしました。

1.任意の正整数$x$を選んで、大きさ$x$の箱を1つ購入する。
2.$N$個のおもちゃそれぞれを、（元々あった箱と新しく購入した箱を合わせた）$N$個の箱のいずれかに入れる。ただし、各おもちゃはそのおもちゃの大きさ以上の大きさを持つ箱にしか入れることはできず、また1つの箱に2つ以上のおもちゃを入れることもできない。

高橋君は、操作１で十分な大きさの箱を購入することで操作２が実行できるようにしたいですが、大きな箱ほど値段が高いため、可能な限り小さな箱を購入したいです。

高橋君が操作２を実行できるような$x$の値が存在するか判定し、存在するならばその最小値を求めてください。

制約

• $2 \leq N \leq 2 * 10^{5}$
• $1 \leq A_{i},B_{i} \leq 10^{9}$
• 入力は全て整数

アルゴリズム

グリーディ法を採用・
おもちゃのリストAと箱のリストBを降順にソートする。
ループを用いて、最も大きいおもちゃから順に最適な箱に収納していく。おもちゃが入れられないときは、おもちゃと同じサイズの箱を変数additional_box_sizaに格納。以降、すべてのおもちゃをしまえた場合は、additional_box_sizeを返し、しまえなかった場合は失敗を表す-1を返す。

ソースコード

N = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))

def find_minimum_additional_box(toys, boxes):
    N = len(toys)
    toys.sort(reverse=True)  
    boxes.sort(reverse=True)  
    
    additional_box_size = 0
    box_index = 0
    assigned_toys = 0
    
    for toy in toys:
        if box_index < len(boxes) and toy <= boxes[box_index]:
            box_index += 1
            assigned_toys += 1
        elif additional_box_size == 0:
            additional_box_size = toy
            assigned_toys += 1
        else:
            return -1  
    
    if assigned_toys < N:
        return -1 
    
    return additional_box_size
    
print(find_minimum_additional_box(A, B))