第三回アルゴリズム実技検定 (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 - ダイナミック・スコアリング
考え方
クエリごとに,ナイーブに で各人の得点を計算していては,制限時間に間に合いそうにありません.そこで,配列(Python ではリスト)などを用いて,以下を記録することにします.これらを用いると,スコアを計算するクエリに, で答えられるようになり,間に合います.
- その人がどの問題を解いたか (
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 - 等比数列
考え方
公比が ならば,制約上 を出力すれば事足ります.さもなければ,初期値を として, を 回逐次掛けていきます.途中で値が を超えればその旨を出力して終了し,そうではなく,最後まで到達すれば得られた値を出力します.
解答コード
#!/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 - 回文行列
考え方
行列 の 行目と 行目 *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 - グリッド金移動
考え方
各マスをグラフの頂点に見立てれば,この問題は二頂点対最短経路問題に帰着でき,幅優先探索が使えます.実装上は,グリッドを陽にもつのではなく,頂点をマス目の座標を表すタプル に関連付ければ手間が省けます.
解答コード
#!/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()
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 問題以降
問題文は読みましたが,何も手掛かりが浮かびませんでした.可能であれば,後日取り組んでみます.