第三回 アルゴリズム実技検定

　A ~ O の全15問中、Gまで7問完答で初級でした。普段のAtCoderと違って実務よりの問題が多いとは聞いてましたが、確かに現実にありそうなシーンを意識して作問してる雰囲気は感じました。今回のAtCoderアルゴリズム実技検定はコロナウイルス影響で無料受験可能だったので、これを機に初めて受けてみたのですが、やはりもっと基本的なとこから鍛えていかなければならないなと改めて実感。

G問題までの解法

　自分の解法。もっと効率的な方法はあると思う。

種類	概要
A	str.lower() メソッドで
B	与えられたクエリを一つ一つ実直に
C	そのままfor文。ただしの時はすぐAを出力。じゃないとの時に無限ループになる。
D	めちゃくちゃ大変。if文の列挙。解答例は割と上手くやっていた（それでもややこしい）
E	無効グラフの問題。制約的にそのまま実直にクエリを実行
F	最初問題文の意味が分からずかなり時間取られる。上手い方法が思いつかずqueを使って実直に実装
G	幅優先探索

H - ハードル走

問題のリンク

概要

• 3つの行動から一つ選んで実行できる。（詳細は問題リンクから）
• からスタートして、までいく時の最短時間を求める。
• ただし間に個のハードルがある。

制約

• 
• 
• 
• 
• は偶数

考察

　問題の感じからDP。もしくは貪欲法あたりだろうなと考えてました。どうやらDPで行くらしいです。考えた方は以下の通り。

• dp[0, inf, inf, inf, ... ]で初期化。
• min(dp[i+1], dp[i]+行動1でかかる時間)で更新。もし座標にハードルがあった場合T3を後者に追加
• min(dp[i+2], dp[i]+行動2でかかる時間)で更新。もし座標にハードルがあった場合T3を後者に追加
• min(dp[i+4], dp[i]+行動3でかかる時間)で更新。もし座標にハードルがあった場合T3を後者に追加

　基本は上記の様にして動的計画法()してく感じ。ただゴール近くに差し迫った場合、ジャンプ中に飛び越している可能性もあるので、最後に微調整が必要。

コード

N, L = map(int, input().split())
X = [False] * (L+10)
hard = list(map(int, input().split()))

for x in hard:
    X[x] = True

T1, T2, T3 = map(int, input().split())

dp = [float('inf')]*(L+10)
dp[0] = 0

for i in range(L+1):
    cost = T3 if X[i] else 0
    dp[i+1] = min(dp[i+1], dp[i] + T1 + cost)
    dp[i+2] = min(dp[i+2], dp[i] + T1 + T2 + cost)
    dp[i+4] = min(dp[i+4], dp[i] + T1 + T2*3 + cost)
    if i+1 == L:
        dp[i+1] = min(dp[i+1], dp[i] + T1//2 + T2//2 + cost)
    elif i+2 == L:
        dp[i+2] = min(dp[i+2], dp[i] + T1//2 + 3*T2//2 + cost)
    elif i+3 == L:
        dp[i+3] = min(dp[i+3], dp[i] + T1//2 + 5*T2//2 + cost)
 
print(dp[L])

I - 行列操作

問題のリンク

考察

　普通に実装すると時間計算量以前に空間計算量的にもヤバくてメモリエラー起こしてました。解法みた所、実はそれに近い形で頭の中では解き方をイメージしてたものの、実装ミスで解けなかった感じです。

コード

N = int(input())
rows = [i for i in range(N)]
columns = [i for i in range(N)]
transposed = False

Q = int(input())
for _ in range(Q):
    q = list(map(int,input().split()))

    if q[0] == 3:
        transposed = not transposed
    else:
        A, B = q[1]-1, q[2]-1
        if q[0] == 1:
            if transposed:
                columns[A], columns[B] = columns[B], columns[A]
            else:
                rows[A], rows[B] = rows[B], rows[A]
        elif q[0] == 2:
            if transposed:
                rows[A], rows[B] = rows[B], rows[A]
            else:
                columns[A], columns[B] = columns[B], columns[A]
        elif q[0] == 4:
            if transposed:
                A, B = B, A
            r,c = rows[A], columns[B]

            print(N*r+c)