AtCoder 東京海上日動 プログラミングコンテスト2020

AB2完の緑パフォでした。そして今回のコンテストでようやくレート緑になることができました！

個人的にレート緑は最初の目標として掲げていたので、ようやくですが入緑できてほっとしています。これからも少しずつ伸ばしていきたい。

A - Nickname

問題のリンク

概要

• 省略

コード

S = input()
print(S[:3])

B - Tag

問題のリンク

概要

• 二次元軸での鬼ごっこ問題。鬼役の座標と速度。逃げる役の座標と速度が与えれるので、制限時間以内に追いつけるかどうかを判定。

制約

省略

考察

省略

コード

A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

diff = abs(A-B)

if (V-W)*T >= diff:
    print('YES')
else:
    print('NO')

C - Lamps

問題のリンク

概要

• 省略

制約

• 
• 
• 

考察

　今回解けなかった問題。解説で学んだいもす法を振り返りながら実装して行こうと思います。

いもす法の考え

　スライドにしてみましたが、これが一番分かりやすいと思います。左図はのように一定の区間をドンドン足し合わせていく操作については、右図のようにその始点と終点+1のポイントに着目することで、大幅に計算量を減らせます。（始点と終点の間全てに+1をしてしまっては計算量が膨大になってしまうことはイメージできると思います。）よってこの方法を使うと、スライドの操作自体は見ての通り、になるので、これを回だけ繰り返すとすると、で問題を解くことが可能です。 　ただここで問題が一つあり、最悪ケースの場合（）でだとAtCoderでは通りません。ただこれも解説で触れていたのですが、今回の問題設定の場合、の操作で収束してしまうことが分かるので、はが回以上の場合、問答無用で答えは[N] * Nの配列になってしまいます。

コード

import numpy as np
from numba import jit
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)

# 高速化
@jit
def imo(a, n):
    imos = np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        imos[max(0, i-a[i])] += 1
        imos[min(n, i+a[i])+1] -= 1

    # 累積和はnumpyの方が高速
    immo = np.zeros(n+1, dtype=np.int64)
    immo = np.cumsum(imos)

    return immo[:n]


for _ in range(min(K, 41)):
    A = imo(A, N)

print(*A)