はむ吉(のんびり)の練習ノート

プログラミングとことばに関する話題を中心に,思いついたこと,試してみたこと,学んだことを,覚え書きを兼ねてまとめます.その際に役立った,技術書,参考書,辞書,機器などの紹介も行います.

第三回アルゴリズム実技検定 (PAST) @ AtCoder 参加記:簡単な解説とコード (Python) つき(A-I と K 問題)

私は,AtCoder でオンライン開催された,第三回アルゴリズム実技検定(略称:PAST)にリアルタイム参加しました.問題に関する言及が解禁されたため,受験時の取り組みを,解けた問題(A-I と K)の略解と,提出したコード (Python) とともに振り返ります.

はじめに

アルゴリズム実技検定は,AtCoder により開催されている検定です.第三回となる今回は,感染症の流行といった昨今の情勢を考慮して,無料で開催されました.そこで,私も受けてみることにしました*1.検定の方式には,5/23(土)の 13:00-18:00 の 5 時間に受けるもの(リアルタイム受験)と,5/23(土)18:00 から 6/6(土)12:59 のうちの好きな時刻を選び,そこから 5 時間を用いて受けるもの(通常受験)がありました(問題は同じです).私は,せっかくなのでリアルタイム受験を行いました.6/6(土)18:00 を過ぎ,問題に関する言及が解禁されたため,この記事を書くことにしました.

結果の概要

A-O の 15 問のうち,A-I および K の計 10 問に完答し,中級(70 点)という判定を得ました(認定証).私の AtCoder レーティングは水色に属するため,第二回検定の結果に基づく,AtCoder レーティングと判定の関係を見る限りでは,妥当だったと思います.初級以上が確定した時点で,気力がなくなってきて,あきらめかけていましたが,もうひと踏ん張りしたところ,なんとか中級を得ることができました.どちらかというと,普段の AtCoder コンテストよりも,実装力を問う問題が多かったのも,有利に働いたのかもしれません.

各問題ごとの取り組み

解けた問題を中心に,各問題についての考え方や解答コードを記します.なお,AtCoder 社による正式な解説もあるので,適宜参照してください.

A - ケース・センシティブ

考え方

両文字列が単純に比較して完全に一致すれば same を,そうではないが,すべて小文字(または大文字)にそろえて完全に一致すれば case-insensitve を,いずれにも該当しなければ different を答えればよいでしょう.実装には,Python の文字列メソッドを使うと楽です.

解答コード
#!/usr/bin/env python3


def judge(s, t):
    if s == t:
        return "same"
    elif s.lower() == t.lower():
        return "case-insensitive"
    else:
        return "different"


def main():
    s = input()
    t = input()
    res = judge(s, t)
    print(res)


if __name__ == '__main__':
    main()

B - ダイナミック・スコアリング

考え方

クエリごとに,ナイーブに O(N) で各人の得点を計算していては,制限時間に間に合いそうにありません.そこで,配列(Python ではリスト)などを用いて,以下を記録することにします.これらを用いると,スコアを計算するクエリに,O(M) で答えられるようになり,間に合います.

  • その人がどの問題を解いたか (is_solved)
  • その問題の現在の点数 (cur_score):問題を解いた人が現れ次第,その分減算する
解答コード
#!/usr/bin/env python3


def process_queries(n, m, queries):
    is_solved = [[False for _ in range(m)] for _ in range(n)]
    cur_score = [n for _ in range(m)]
    for q_type, q_args in queries:
        if q_type == 0:
            i = q_args[0]
            score = sum(b * s for b, s in zip(is_solved[i], cur_score))
            yield score
        else:
            i, j = q_args
            is_solved[i][j] = True
            cur_score[j] -= 1


def main():
    n, m, q = (int(z) for z in input().split())
    queries = []
    for _ in range(q):
        q_type, *q_args = (int(z) - 1 for z in input().split())
        queries.append((q_type, q_args))
    print(*process_queries(n, m, queries), sep="\n")


if __name__ == '__main__':
    main()

C - 等比数列

考え方

公比が R = 1 ならば,制約上 A を出力すれば事足ります.さもなければ,初期値を A として, R N - 1 回逐次掛けていきます.途中で値が  10^9 を超えればその旨を出力して終了し,そうではなく,最後まで到達すれば得られた値を出力します.

解答コード
#!/usr/bin/env python3


L = 10 ** 9


def compute(a, r, n):
    if r == 1:
        return a
    else:
        cur_val = a
        for i in range(n - 1):
            cur_val *= r
            if cur_val > L:
                return None
        return cur_val


def main():
    a, r, n = (int(z) for z in input().split())
    res = compute(a, r, n)
    if res is None:
        print("large")
    else:
        print(res)


if __name__ == '__main__':
    main()

D - 電光掲示

考え方

親切にも,入出力例 1 で各桁の表示方法が与えられているので,これを用いて桁の読み取りを実装すればよいでしょう.特に工夫をせず,左から順に読めばよいのです.

解答コード
#!/usr/bin/env python3


import sys


HEIGHT = 5
DIGIT_WIDTH = 4
SPACING_WIDTH = 1
ALL_DIGITS = """.###..#..###.###.#.#.###.###.###.###.###.
.#.#.##....#...#.#.#.#...#.....#.#.#.#.#.
.#.#..#..###.###.###.###.###...#.###.###.
.#.#..#..#.....#...#...#.#.#...#.#.#...#.
.###.###.###.###...#.###.###...#.###.###."""


def generate_sample_digits(data=ALL_DIGITS, digit_width=DIGIT_WIDTH, spacing_width=SPACING_WIDTH):
    rows = data.split("\n")
    num_columns = len(rows[0])
    digits = []
    for start_idx in range(0, num_columns - spacing_width, digit_width):
        digit = [row[start_idx:start_idx + digit_width] for row in rows]
        digits.append(digit)
    return digits


def print_digit(digit, file=sys.stderr):
    # for debug
    print("\n".join(digit), file=sys.stderr)


def read_str(rows, digit_width=DIGIT_WIDTH, spacing_width=SPACING_WIDTH):
    digits = generate_sample_digits()
    res = ""
    num_columns = len(rows[0])
    for start_idx in range(0, num_columns - spacing_width, digit_width):
        input_digit = [row[start_idx:start_idx + digit_width] for row in rows]
        # print_digit(input_digit)
        for i, sample_digit in enumerate(digits):
            if input_digit == sample_digit:
                res += str(i)
                break
    return res


def main():
    n = int(input())
    rows = [input() for _ in range(HEIGHT)]
    res = read_str(rows)
    print(res)


if __name__ == '__main__':
    main()

E - スプリンクラー

考え方

所与の無向グラフを,隣接リストで表せば,容易に実装できます.「スプリンクラー」では,ある頂点に隣接する(すなわち,距離 1)頂点を塗り替えるだけであり,その頂点が属する連結成分の頂点をすべて塗り替えるわけではないので,注意してください.

解答コード
#!/usr/bin/env python3


def parse_queries(adj_list, init_cols, queries):
    cols = init_cols[:]
    for q_type, q_args in queries:
        if q_type == 1:
            x = q_args[0]
            print(cols[x])
            for v in adj_list[x]:
                cols[v] = cols[x]
        else:
            x, y = q_args
            print(cols[x])
            cols[x] = y


def main():
    n, m, q = (int(z) for z in input().split())
    adj_list = [set() for _ in range(n)]
    for _ in range(m):
        u, v = (int(z) - 1 for z in input().split())
        adj_list[u].add(v)
        adj_list[v].add(u)
    init_cols = [int(c) for c in input().split()]
    queries = []
    for _ in range(q):
        q_type, *q_args = (int(x) for x in input().split())
        if q_type == 1:
            x = q_args[0] - 1
            queries.append((q_type, (x, )))
        else:
            x = q_args[0] - 1
            y = q_args[1]
            queries.append((q_type, (x, y)))
    parse_queries(adj_list, init_cols, queries)


if __name__ == '__main__':
    main()

F - 回文行列

考え方

行列 a i 行目と  N - i - 1 行目 *2 に同じ文字があるか調べ,もし存在すればこれを回文の構成要素として採用し,存在しなければそれを指摘して終了します.この判定は,Python の集合を用いると容易です.

解答コード
#!/usr/bin/env python3


def generate_palindrome(n, matrix):
    cand_sets = [set(line) for line in matrix]
    left_str = ""
    for i in range(n // 2):
        for c in cand_sets[i]:
            if c in cand_sets[n - 1 - i]:
                left_str += c
                break
        else:
            return None
    if n % 2 == 0:
        res = left_str + left_str[::-1]
    else:
        res = left_str + cand_sets[n // 2].pop() + left_str[::-1]
    return res


def main():
    n = int(input())
    matrix = [input() for _ in range(n)]
    res = generate_palindrome(n, matrix)
    if res is None:
        print(-1)
    else:
        print(res)


if __name__ == '__main__':
    main()

G - グリッド金移動

考え方

各マスをグラフの頂点に見立てれば,この問題は二頂点対最短経路問題に帰着でき,幅優先探索が使えます.実装上は,グリッドを陽にもつのではなく,頂点をマス目の座標を表すタプル  (x, y) に関連付ければ手間が省けます.

解答コード
#!/usr/bin/env pypy3


import collections
import itertools


DELTAS = ((1, 1), (0, 1), (-1, 1), (1, 0), (-1, 0), (0, -1))
INF = 10 ** 9
COUNT_LIMIT = 10 ** 6


def minimize_dist(obstacles, goal, start=(0, 0), deltas=DELTAS):
    dist = collections.defaultdict(lambda: INF)
    dist[start] = 0
    q = collections.deque()
    q.appendleft(start)
    num_counts = 0
    while q and num_counts < COUNT_LIMIT:
        num_counts += 1
        x0, y0 = q.pop()
        if (x0, y0) == goal:
            return dist[goal]
        for dx, dy in deltas:
            x, y = x0 + dx, y0 + dy
            if (x, y) in obstacles:
                continue
            elif dist[(x, y)] >= INF:
                dist[(x, y)] = dist[(x0, y0)] + 1
                q.appendleft((x, y))
    return None



def main():
    n, x, y = (int(z) for z in input().split())
    obstacles = set(tuple(int(z) for z in input().split()) for _ in range(n))
    min_dist = minimize_dist(obstacles, (x, y))
    if min_dist is None:
        print(-1)
    else:
        print(min_dist)


if __name__ == '__main__':
    main()

H - ハードル走

考え方

ゴールに到達する場合には,地面についた状態で到達する場合と,ジャンプ中に到達する場合の二つがあります.これらをまぜこぜに考えるのは難しいので,まずは地面についた状態で到達する場合を考えると,それまでにかかる時間の最小値は,以下のコードに示されているように,動的計画法で求められます.あとは,この計算過程を用いて,ジャンプ中にゴールする場合を考慮します.

解答コード
#!/usr/bin/env python3


INF = 10 ** 9


def minimize(n, el, xs, ts):
    dp = [INF for _ in range(el + 2)]
    dp[0] = 0
    for i in range(1, el + 1):
        if i - 1 >= 0:
            dp[i] = min(dp[i], dp[i - 1] + ts[0] + ts[2] * int(i in xs))
        if i - 2 >= 0:
            dp[i] = min(dp[i], dp[i - 2] + ts[0] + ts[1] + ts[2] * int(i in xs))
        if i - 4 >= 0:
            dp[i] = min(dp[i], dp[i - 4] + ts[0] + 3 * ts[1] + ts[2] * int(i in xs))
    res = dp[el]
    if el - 1 >= 0:
        res = min(res, dp[el - 1] + ts[0] // 2 + ts[1] // 2)
    if el - 2 >= 0:
        res = min(res, dp[el - 2] + ts[0] // 2 + 3 * ts[1] // 2)
    if el - 3 >= 0:
        res = min(res, dp[el - 3] + ts[0] // 2 + 5 * ts[1] // 2)
    return res


def main():
    n, el = (int(z) for z in input().split())
    xs = {int(x) for x in input().split()}
    ts = [int(t) for t in input().split()]
    res = minimize(n, el, xs, ts)
    print(res)


if __name__ == '__main__':
    main()

I - 行列操作

考え方

転置や,行または列の入れ替えをナイーブに実装していては,制限時間に間に合いそうにないので,手を抜く方法を考えます.転置については,「現在転置されているか」という情報だけを,真偽値としてもっておきます.もし転置されていれば,行,列の交換はそれぞれ列,行の交換に読み替え,要素の読み取りの際には行番号と列番号を入れ替えたものに読み替えれば十分です.なお,私は Queries in a Matrix - GeeksforGeeks を参考にして実装しました*3

解答コード
#!/usr/bin/env python3


def process_queries(n, queries):
    rows = list(range(n))
    cols = list(range(n))
    transposed = False
    for q_type, q_args in queries:
        if not transposed and q_type == 0 or transposed and q_type == 1:
            a, b = q_args
            rows[a], rows[b] = rows[b], rows[a]
        elif not transposed and q_type == 1 or transposed and q_type == 0:
            a, b = q_args
            cols[a], cols[b] = cols[b], cols[a]
        elif q_type == 2:
            if transposed:
                transposed = False
            else:
                transposed = True
        else:
            a, b = q_args
            if not transposed:
                yield rows[a] * n + cols[b]
            else:
                yield rows[b] * n + cols[a]



def main():
    n = int(input())
    q = int(input())
    queries = []
    for _ in range(q):
        q_type, *q_args = (int(z) - 1 for z in input().split())
        queries.append((q_type, q_args))
    print(*process_queries(n, queries), sep="\n")


if __name__ == '__main__':
    main()

J - 回転寿司

解けていません.問題の趣旨はつかめたものの,解法は浮かびませんでした.

K - コンテナの移動

考え方

どの机にどのコンテナがどの順で並んでいるかをナイーブに実装していては,制限時間に間に合いそうにありません.そこで,以下のコードのように,「あるコンテナの真下にあるコンテナ」「ある机に積み重なっているコンテナのうち,一番上にあるコンテナ」を管理すれば,高速にクエリを処理できます.クエリをすべて処理した後は,これらの配列をたどっていくことで,最終結果が得られます.

解答コード
#!/usr/bin/env python3


def process_queries(n, queries):
    # ここでは添え字を 0 始まりとする
    # コンテナ i の真下にあるコンテナ
    adj_down = [None for _ in range(n)]
    # 机 i のてっぺんにあるコンテナ
    top = list(range(n))
    for f, t, x in queries:
        # 一行で書くことで,一時的な変数を使わずに一度に swap できる
        top[f], top[t], adj_down[x] = adj_down[x], top[f], top[t]
    # コンテナ i がどこにあるか
    cont2desk = [None for _ in range(n)]
    for desk_id, top_cont in enumerate(top):
        cur_cont = top_cont
        while cur_cont is not None:
            cont2desk[cur_cont] = desk_id
            cur_cont = adj_down[cur_cont]
    return cont2desk


def main():
    n, q = (int(z) for z in input().split())
    # 添え字を 0 始まりとする
    queries = [tuple(int(z) - 1 for z in input().split()) for _ in range(q)]
    res = process_queries(n, queries)
    # 添え字を 1 始まりに直しながら出力する
    print(*(r + 1 for r in res), sep="\n")


if __name__ == '__main__':
    main()

L 問題以降

問題文は読みましたが,何も手掛かりが浮かびませんでした.可能であれば,後日取り組んでみます.

おわりに

私がアルゴリズム実技検定に参加したのは,今回が初めてでした.アルゴリズムを考えたり運用したりする力に加えて,実装をやりとげる力も問われているのが,普段の AtCoder 公式コンテストとの違いだと思いました.検定の趣旨や対象からして当然なのでしょうが,実務を重視しているようです.また,5 時間のコンテストは,長丁場でした.体力や気力も,実力のうちとはこのことなのかもしれません.次回以降も,可能であれば参加したいと思います.

*1:こう書くと,ちょっと現金かもしれません.

*2:この行数は 0 始まりです.以下のコードでも,添え字を 0 始まりとしています.

*3:この検定では,受験中の Web 検索が認められています.