Atcoder ABC250 振り返り

A - Adjacent Squares【AC】

　場合分けしてO(1)で解くことも出来ますが，早解きでミス無く書くのは難しいので(1敗)H, W<=10であることを活かして全探索します．
　マスの数は最大でも100しかないので，全てのマスについて辺で隣接しているかチェックすれば良いです．チェックは問題文にある定義を使えば良いです．

H, W = map(int, input().split())
R, C = map(int, input().split())
ans = 0

for h in range(1, H+1):
    for w in range(1, W+1):
        if abs(h-R) + abs(w-C) == 1:
            ans += 1

print(ans)

B - Enlarged Checker Board【AC】

　アルゴリズムというよりは実装力が求められる問題でした．nタイル目のnの偶奇で色が決まります．あとは頑張って実装します．

N, A, B = map(int, input().split())
ans = ["" for _ in range(N*A)]

for i in range(N):
    for j in range(N):  
        if (i+j) % 2 == 0:
            tile = "."
        else:
            tile = "#"

        for ii in range(A):
            ans[ii+i*A] += tile*B

for a in ans:
    print(a)

C - Adjacent Swaps【AC】

　値を入れ替えるときに，リストのどこに値があるのかをindex()関数などで探すとそれだけでO(N)かかってしまうので，ここを短縮することを考えます．辞書で値を取得するのはO(1)で出来るため，辞書でこの操作ができないかを考えます．
　鍵にインデックス，値に数字を持つ辞書i2v_dicと，鍵に数字，値にインデックスを持つ辞書v2i_dicの2つを用意します．値がリストのどのインデックスにあるかを調べるためにv2i_dicを使い，実際に値を入れ替える動作をi2v_dicで行います．入れ替えた後，2つの辞書とも値を入れ替える必要があるため気をつけます．

N, Q = map(int, input().split())
i2v_dic = {i:i+1 for i in range(N)}
v2i_dic = {i:i-1 for i in range(1, N+1)}

for _ in range(Q):
    x = int(input())
    ind = v2i_dic[x]
    if ind != N-1:
        v2i_dic[x] = v2i_dic[i2v_dic[ind+1]]
        v2i_dic[i2v_dic[ind+1]] = ind
        i2v_dic[ind], i2v_dic[ind+1] = i2v_dic[ind+1], i2v_dic[ind]

    else:
        v2i_dic[x] = v2i_dic[i2v_dic[ind-1]]
        v2i_dic[i2v_dic[ind-1]] = ind
        i2v_dic[ind], i2v_dic[ind-1] = i2v_dic[ind-1], i2v_dic[ind]

ans = []
for i in range(N):
    ans.append(str(i2v_dic[i]))

print(" ".join(ans))

D - 250-like Number【AC】

　エラトステネスのふるいを使います．p*q^3<=10^18を満たすqは，pが最小値の2を取ったとしても必ずq < 10^6となる事が分かります．よって探索するp, qは10^6以下の素数である事が分かります．
　エラトステネスのふるいを使ってO(N loglogN)で素数を列挙します．これは10^6までなら間に合います．列挙された素数に対してp*q^3＜Nを満たすかをチェックしていけば良いです．
　エラトステネスのふるいは以前実装しました．
hirohirohirohiros.hatenablog.com
　しかし，これを使って提出するとTLEになってしまいます．コードに誤りがあるわけではありません．このコードの出力は数字iが素数ならi番目がTrue，素数でないならFalseが入ったリストです．この長さ10^6のリストを使って，リスト[i]がTrueなら……とやっていると時間が足りなくなります．
　よって，初めから素数のみが入ったリストを出力するようにコードを書き換える必要があります．といっても新しくprimesというリストを用意してやり，prime_listがTrueならprimesにappendするという処理を追記すれば良いです．これによりループする回数が減りACする事が出来ます．

def erato_sieve(x):
    primes = []
    prime_list = [True] * (x + 1)
    prime_list[0] = False
    prime_list[1] = False

    p = 2
    while p <= x:
        if not prime_list[p]:
            p += 1
            continue

        primes.append(p)
        i = p*2
        while i <= x:
            prime_list[i] = False
            i += p

        p += 1

    return primes

N = int(input())
prime_list = erato_sieve(10**6+1)
ans = 0
l = len(prime_list)

for i in range(l-1):
    for j in range(i+1, l):
        if prime_list[i] * prime_list[j]**3 > N:
            break
        ans+=1

print(ans)