AtCoder Beginner Contest 178 E - Dist Max【Python】

https://atcoder.jp/contests/abc178/tasks/abc178_e

AtCoder ProblemsでDifficulty: 1054、Solve Probability: 18%でした。

解けませんでした。
下記の記事の解説がわかりやすかったです。

bqn2.hatenablog.com

愚直に2点の距離を求めようとすると2重ループになるため1重ループで済むように式変形をする。
絶対値をmaxで分解するとmax((xi + yi) + (-xj - yj), ...)のようにiとjごとに分けられる。
各要素(xi + yi), (-xj - yj)....が最大なら全体も最大となる。
各要素(xi + yi), (-xj - yj)....を(x + y), (-x - y)....として一重ループで要素ごとの最大値を求めて変形した式に代入。

N = int(input())
XY = []
for i in range(N):
    XY.append(list(map(int, input().split())))

# x + y
a = 0
# -x - y
b = 0
# -x + y
c = 0
# x - y
d = 0
 
for i in range(N):
    x, y = XY[i]

    a = max(a, x + y)
    b = max(b, -x - y)
    c = max(c, -x + y)
    d = max(d, x - y)
    
print(max(a + b, d + c, c + d, b + a))

AtCoder Beginner Contest 153 E - Crested Ibis vs Monster【Python】

https://atcoder.jp/contests/abc153/tasks/abc153_e

AtCoder ProblemsでDifficulty: 1015、Solve Probability: 19%でした。

ちょうどアルゴ式でDPについて勉強したところだったため問題文を見てDPで解けそうという検討がつきました。

algo-method.com

H, N = map(int, input().split())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
maxA = max(A)
dp = [[INF] * (H + 1 + maxA) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H + 1 + maxA):
        if j - A[i] >= 0:
            dp[i + 1][j] = min(dp[i][j - A[i]] + B[i], dp[i + 1][j])
            # 同じ魔法を何度も使う場合
            dp[i + 1][j] = min(dp[i + 1][j - A[i]] + B[i], dp[i + 1][j])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

print(min(dp[N][H:]))

AtCoder Beginner Contest 225 D - Play Train【Python】

https://atcoder.jp/contests/abc225/tasks/abc225_d

AtCoder ProblemsでDifficulty: 778、Solve Probability: 33%でした。

解けませんでした。
双方向リストも思いつかず、制約の「3xの形式のクエリで出力する電車の番号の個数の合計は106以下」についても、3xのクエリごとの番号の個数の合計が106以下の意味と捉えてしまっていました。
今後こういった制約の文については注意したいところです。

UNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225) - YouTube

N, Q = map(int, input().split())
front = [-1] * N
back = [-1] * N

for i in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 3:
        x = q[1]-1
        while front[x] != -1:
            x = front[x]
        ans = [x+1]
        while back[x] != -1:
            x = back[x]
            ans.append(x+1)
        print(len(ans), *ans)
    else:
        x, y = q[1]-1, q[2]-1
        if q[0] == 1:
            front[y] = x
            back[x] = y
        elif q[0] == 2:
            front[y] = -1
            back[x] = -1

AtCoder Beginner Contest 167 D - Teleporter【Python】

https://atcoder.jp/contests/abc167/tasks/abc167_d

AtCoder ProblemsでDifficulty: 754、Solve Probability: 35%でした。

最終的に経路はリピートされるため、辞書で町ごとに訪れた回数をカウントし、初めてカウントが2になった街があれば、その時点からその街のカウントが3になるまでの経路をリストで管理しループから抜けるようにしました。

from collections import defaultdict

N, K = map(int, input().split())
A = list(map(int, input().split()))

d = defaultdict(int)
c = 0
d[c] += 1
rep_flag = False
rep = []
n_before_rep = 1
for i in range(K):
    c = A[c] - 1
    d[c] += 1
    if d[c] == 3:
        print(rep[(K + 1 - n_before_rep) % len(rep) - 1] + 1)
        exit()
    if d[c] == 2:
        rep_flag = True
    if rep_flag:
        rep.append(c)
    else:
        n_before_rep += 1
print(c + 1)

AtCoder Beginner Contest 243 D - Moves on Binary Tree【Python】

https://atcoder.jp/contests/abc243/tasks/abc243_d

AtCoder ProblemsでDifficulty: 758でした。

解けませんでした。
解説

atcoder.jp

の解法2の2進数に変換した文字列で考えるというのは部分的に他の問題でもあった記憶があるため思いつきたかったところです。

解説の解法1

from collections import deque
N, X = map(int, input().split())
S = input()
d = deque()

for i in range(N):
    s = S[i]
    if len(d) == 0:
        d.append(s)
    else:
        dl = d[-1]
        if (dl == 'R' or dl == 'L') and s == 'U':
            d.pop()
        else:
            d.append(s)

for s in d:
    if s == 'U':
        X //= 2
    elif s == 'L':
        X *= 2
    else:
        X = X * 2 + 1
print(X)

解説の解法2

N, X = map(int, input().split())
S = input()

T = list(bin(X))
for i in range(N):
    s = S[i]
    if s == 'U':
        T.pop()
    elif s == 'L':
        T += '0'
    else:
        T += '1'
print(int(''.join(T), 2))

AtCoder Beginner Contest 241 C - Connect 6【Python】

https://atcoder.jp/contests/abc241/tasks/abc241_c

AtCoder ProblemsでDifficulty: 664でした。

コンテスト中に解けませんでした。6行6列のマス目を動かして全探索するという発想ができませんでした。

N = int(input())
S = []
for i in range(N):
    S.append(input())

for i in range(N-5):
    for j in range(N-5):
        for k in range(6):
            count = 0
            for l in range(6):
                if S[i+k][j+l] == '#':
                    count += 1
            if count >= 4:
                print('Yes')
                exit()
            
        for k in range(6):
            count = 0
            for l in range(6):
                if S[i+l][j+k] == '#':
                    count += 1
            if count >= 4:
                print('Yes')
                exit()
        count = 0
        for k in range(6):
            if S[i+k][j+k] == '#':
                count += 1
        if count >= 4:
            print('Yes')
            exit()
        count = 0
        for k in range(6):
            if S[i+k][j+5-k] == '#':
                count += 1
        if count >= 4:
            print('Yes')
            exit()
print('No')

AtCoder Beginner Contest 240 D - Strange Balls【Python】

https://atcoder.jp/contests/abc240/tasks/abc240_d

AtCoder ProblemsでDifficulty: 570、Solve Probability: 53%でした。

解けませんでした。コンテスト中に1時間10分ほど時間が残っており、スタックについても知っていたので解きたかった問題でした。

from collections import deque

d = deque()
ans = 0
for i in range(N):
    x = A[i]
    if len(d) == 0:
        d.append((x, 1))
        ans += 1
    else:
        a, b = d[-1]
        if a != x:
            d.append((x, 1))
            ans += 1
        else:
            if a != b+1:
                b += 1
                d[-1] = (a, b)
                ans += 1
            else:
                d.pop()
                ans -= b
    print(ans)