Atcoder 灰diff埋め ABC148C~ABC214C 振り返り

ABCの灰diffが全て埋まりました！次はARCを埋めていきます．

ABC148 D - Brick Break【AC】

　ぱっと見難しい問題に見えます．しかし，1,2,3...の順番さえ守っていれば，どのレンガを壊しても答えは変わらない事に気付けば簡単になります．今残す数字をkと記憶しておき，kとレンガの数が一致してたらレンガを壊さずkを+1し，kとレンガの数が異なっていたらレンガを壊します．全てのレンガを見た後k=1，つまりレンガを1つも壊さなかったとき，満足する事が出来ないので-1を出す事に気をつけます．

N = int(input())
A = [int(i) for i in input().split()]
ans = 0
k = 1

for a in A:
    if a == k:
        k += 1
    else:
        ans += 1

if k == 1:
    print(-1)
else:
    print(ans)

ABC149 C - Next Prime【AC】

hirohirohirohiros.hatenablog.com
　以前実装したエラトステネスのふるいを使います．エラトステネスのふるいは0からNまでの数字について，素数判定をO(N loglog N)で行ってくれるアルゴリズムです．これを使えばN=10^6までの素数判定も十分間に合います（ACしたコードの実行時間は80msでした）．
　X以上の素数のなかで，最小の素数を求める問題なので，Xが素数が判定し素数でなければX+1するのをXが素数になるまで繰り返せばよいです．

def erato_sieve(x):
    """エラトステネスの篩

    0からxまでの素数を返す
    計算量: O(n loglog n)

    Args:
        x (int): 素数判定をしたい数の最大値

    Returns:
        list: i番目が素数ならTrue, そうでないならFalse
    """
    prime_list = [True]*(x+1)
    prime_list[0] = False
    prime_list[1] = False
    p = 2
    while p**2 <= x:
        if not prime_list[p]:
            p += 1
            continue
        
        i = p*2
        while i <= x:
            prime_list[i] = False
            i += p
        p += 1

    return prime_list

X = int(input())
prime = erato_sieve(10**6)
while not prime[X]:
    X += 1
print(X)

ABC214 C - Distribution【AC】

　まず思い付くのは，時間T[i]にiが宝石を受け取った後その宝石が他の人に受け取られる時間を記録していき，全てのiについて記録が終わったらその最小値を取るという手法です．しかしこの手法では，iについて他の人に受け取られる時間を記録する工程でO(N)，全てのiについて記録する工程でO(N)かかるので，合わせてO(N^2)の計算量が掛かってしまい間に合いません．
　そこで発想を逆転し，他の人に受け取られる時間を記録するのでなく，自分が他の人から宝石を受け取る時間について考えるようにします．すると，宝石は隣の人からしか受け取ることはないので，見るポイントは隣の人の時間しかないことが分かります．これでiについて記録する工程がO(1)となるので，全体の計算量はO(N)となり間に合います．
　なお，2*N回ループさせないと，T[0]とT[-1]についての探索が行われず正しい答えが求まらないので注意します．

N = int(input())
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]

for i in range(2*N):
    T[(i+1)%N] = min(T[(i+1)%N], T[i%N] + S[i%N])

for t in T:
    print(t)