キーエンス プログラミング コンテスト 2020

B - Robot Arms

atcoder.jp

解法

ロボットを位置で昇順ソートして１体ずつ見ていき、腕がぶつかるロボットがいたら消していく。 ぶつかった２体の内、右腕がより右側に伸びているロボットを消す。

走査した時点でもっとも右に伸びている右手の座標を保持しながら走査すれば計算量はO(N)になる。

ロボットA：○ーーー●ーーー○
ロボットB：　　　　○ーー●ーー○
この時はBを消す

ロボットA：○ーーー●ーーー○
ロボットB：　　　○ー●ー○
この時はAを消す

実装

n=int(input())
ls=[list(map(int,input().split())) for i in range(n)]
ls.sort()
 
first_robot=ls.pop(0)
max_right=first_robot[0]+first_robot[1]
 
for robot in ls:
    left=robot[0]-robot[1]
    right=robot[0]+robot[1]
    if left<max_right: #ぶつかった時
        n-=1
        if right<max_right: #新しいロボットの方が右にはみ出ていないパターン
            max_right=right
    else:
        max_right=right
print(n)

C - Subarray Sum

atcoder.jp

解法

l==r、つまり数列から1個だけ取り出してそれを合計とすることが許されているので、以下のように数列を組めばそれが解になる

例1) N,K,S = 5, 3, 10
=> [10, 10, 10, X, X]
(l,r)=(0,0),(1,1),(2,2) の計3つの組み合わせが条件を満たす。Xは適当な数

例2) N,K,S = 10, 7, 999
=> [999, 999, 999, 999, 999, 999, 999, X, X, X]
(l,r)=(0,0),(1,1),(2,2),(3,3),(4,4),(5,5),(6,6) の計7つの組み合わせが条件を満たす。Xは適当な数

ここで適当な数Xは、それを含む組み合わせの合計がSにならないようにしなくてはいけない。 （例えば例1でX=5とすると(l,r)=(3,4)も条件を満たしてしまい、組み合わせの数が4つになってしまう） Xは、Sが10⁹ではないときには10⁹にしておき、Sが10⁹の時だけは10⁹ -1にしておけばよい。

実装

n,k,s=map(int,input().split())
if s==10**9:
  x=10**9-1
else:
  x=10**9
 
ls_a=[s]*k
ls_b=[x]*(n-k)
print(" ".join(list(map(str,ls_a+ls_b))))

レート変化

レートを100あげるのに半年かかりました