AtCoder Beginners Contest 315 (ABC315) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。

A - tcdr

問題ページ

考察

ある文字列 $B$ の中になにか別の文字列 $A$ が含まれているかどうかの判定は、A in B で書けます。

# 具体例
A = "Code"
B = "AtCoder"
if A in B:
    print("ok")  # "AtCoder"の中に"Code"が入っているので、okが出力される。
else:
    print("ng")  # ngは出力されない

これをつかって入力で受け取った文字列 $S$ の文字を1つ1つ見ていって、"aeiou"のどれとも一致していなければ変数ansの末尾にその文字をつけ加えていくことでACできます。

コード

S = input()
ans = ""
for s in S:
    if s not in "aeiou":
        ans += s
print(ans)

別解

replaceメソッドをつかった解き方

str.replace(A, B) で文字列 $A$ を文字列 $B$ に変換できます。 "aeiou"それぞれについて、replaceメソッドをつかって空文字に変換することで、母音をすべて取り除くことができます。

S = input()
for t in "aeiou":
    S = S.replace(t, "")
print(S)

パターンマッチ構文をつかった解き方

言語アップデートが入って、Pythonでもパターンマッチ構文がつかえるようになりました。 if文で書くのと処理の内容は変わらないですが、他の言語ではよく標準的に装備されている構文で、見慣れてくるとちょっぴり可読性が上がるかも(私もまだ慣れてません...)。

S = input()
ans = ""
for s in S:
    match s:
        case "a" | "e" | "i" | "o" | "u":
            pass
        case _:
            ans += s
print(ans)

B - The Middle Day

問題ページ

考察

制約を見ると、 $1 \leq M \leq 100, 1 \leq D_i \leq 100$ とあるので、1年間は最大でも $10000$ 日までしかありません。
これくらいの数なら、テクニカルな解法をつかわなくても全列挙してしまっていいです。

たとえば1年間が9日だったら真ん中は5日目で、0-indexだと4日目になります。1年間が $N$ 日だったら0-indexで真ん中は $N//2$ 日目です( $//$ は小数点以下切り捨ての割り算)。
下のコードでは、全体の日にちの合計をsum関数をつかって求めています (知らなかったら、for文でリスト $D$ の要素の総和を求めてもokです)。

コード

M = int(input())
D = list(map(int, input().split()))
lst = []  # (月, 日) のタプルを格納する
for i in range(M):
    for j in range(D[i]):
        lst.append((i + 1, j + 1))
a, b = lst[sum(D) // 2]
print(a, b)

C - Flavors

問題ページ

考察

次の2次元リストを用意して、味ごとにおいしさをまとめます。

$G[F]$ : 味 $F$ のアイスクリームのおいしさ $S$ が格納されたリスト

満足度は次のように決められていました。

食べたアイスクリームのおいしさを $s,t$ (ただし、 $s \geq t$ )とする。

2つのカップの味が異なるなら、満足度は $s+t$ である。

そうでないなら、満足度は $s+t/2$ である。

2つのアイスクリームが同じ味のときを考えてみます。2つの味がどちらも $F$ のとき、 $G[F]$ を大きい順にソートして上位2つを選べば、味 $F$ について最大の満足度を求められます。

2つのアイスクリームが異なる味のときを考えてみます。空のリストtopを用意し、それぞれの味について最大のおいしさの値をリストtopに追加していきます。
topを降順にソートして上位2つの値の和を求めると、それが2つのアイスクリームが異なる味のときの満足度の最大値になっています。

コード

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N):
    f, s = map(int, input().split())
    G[f - 1].append(s)

for i in range(N):
    G[i].sort(reverse=True)

ans = 0
# 同じ味のアイスクリームの満足度
for i in range(N):
    if len(G[i]) >= 2:
        ans = max(ans, G[i][0] + G[i][1] // 2)

# 異なる味のアイスクリームの満足度
top = []
for i in range(N):
    if len(G[i]) >= 1:
        top.append(G[i][0])
top.sort(reverse=True)
ans = max(ans, sum(top[:2]))

print(ans)

D - Magical Cookies

問題ページ

考察

この行にある'a'の個数はいくつで、'b'の個数はいくつで、...と、すべての行に対してすべてのアルファベットがいくつあるのかを知りたいです。アルファベットのまま進めてもいいですが整数値の方が分かりやすいので、ord関数というUnicode値を返す関数をつかって、先にアルファベットすべてを数値に変換しておきます。

$row[i][num]$ : $i$ 行目にある数字 $num$ の個数
$rowColorCnt[i]$ : $i$ 行目にある数字の種類数
$nowH$ : 削除されていない行の数
$deletedRow[i]$ : $i$ 行目が操作1によって削除されていればTrue、そうでなければFalse

の変数を用意します。列に対しても同様に変数を用意します。

あとは問題文の通りに実際にシミュレーションしていくのみです。最終的な答えは、$(操作1で削除されなかった行の数) \times (操作2で削除されなかった列の数) = now_H \times now_W$ になります。

(この問題はコードの中身を言語化する方がかえって分かりにくくなると思うので、下のコードを参考にしてください。)

コード

H, W = map(int, input().split())
Grid = [list(input()) for _ in range(H)]

# アルファベットを整数に変換
for i in range(H):
    for j in range(W):
        Grid[i][j] = ord(Grid[i][j]) - ord('a')

# row[i][num]: i行目にある数字numの個数
row = [[0] * 26 for _ in range(H)]
col = [[0] * 26 for _ in range(W)]
# row_color_cnt[i]: i行目にある数字の種類数
row_color_cnt = [0] * H
col_color_cnt = [0] * W

for i in range(H):
    for j in range(W):
        num = Grid[i][j]
        if row[i][num] == 0:
            row_color_cnt[i] += 1
        if col[j][num] == 0:
            col_color_cnt[j] += 1
        row[i][num] += 1
        col[j][num] += 1

# now_H: 削除されていない行の数
now_H, now_W = H, W
# deleted_row[i]: i行目が操作1によって削除されていればTrue
deleted_row = [False] * H
deleted_col = [False] * W

while now_H >= 2 or now_W >= 2:
    now_delete_row = []  # 操作1で削除する予定の行番号を格納するリスト
    for i in range(H):
        if deleted_row[i]:
            continue
        if row_color_cnt[i] == 1 and now_W >= 2:
            deleted_row[i] = True
            now_delete_row.append(i)
    now_delete_col = []
    for j in range(W):
        if deleted_col[j]:
            continue
        if col_color_cnt[j] == 1 and now_H >= 2:
            deleted_col[j] = True
            now_delete_col.append(j)
    now_H -= len(now_delete_row)
    now_W -= len(now_delete_col)

    if len(now_delete_row) == len(now_delete_col) == 0:
        break

    for i in now_delete_row:
        for j in range(W):
            if not deleted_col[j]:
                num = Grid[i][j]
                if num == -1:
                    continue
                col[j][num] -= 1
                Grid[i][j] = -1
                if col[j][num] == 0:
                    col_color_cnt[j] -= 1

    for j in now_delete_col:
        for i in range(H):
            if not deleted_row[i]:
                num = Grid[i][j]
                if num == -1:
                    continue
                row[i][num] -= 1
                Grid[i][j] = -1
                if row[i][num] == 0:
                    row_color_cnt[i] -= 1

print(now_H * now_W)

E - Prerequisites

問題ページ

考察

サンプル1で考えてみます。サンプル1はこのような入力でした。

6
3 2 3 4
2 3 5
0
1 5
0
0

次の順番で本を読むことになります(他の順番もあります)。

本1を読みたいです。そのために本2,3,4を読まないといけません。・・・(A)
(A)より、本2を読みたいです。そのために本3,5を読まないといけません。・・・(B)
(B)より、本3を読みたいです。本3は事前に読まないといけない本はないので、本3を読みます。
(B)より、本5を読みたいです。本5は事前に読まないといけない本はないので、本5を読みます。
(B)より、本2を読むのに必要な本3,5を読み終えたので、本2を読みます。
(A)より、本4を読みたいです。本4を読むのに必要な本は本5のみでこれは読み終えているので、本4を読みます。
(A)より、本1を読むのに必要な本2,3,4を読み終えたので、本1を読みます。

この手順を再帰関数を用いてそのまま実装します(深さ優先探索DFSの帰りがけ順ともよばれます)。
再帰関数なので、下のコードの最初5行の記述を忘れないようにしておきましょう。

コード

import sys
import pypyjit

sys.setrecursionlimit(10 ** 7)
pypyjit.set_param('max_unroll_recursion=-1')

N = int(input())
G = []
for i in range(N):
    c, *p = map(lambda x: int(x) - 1, input().split())
    G.append(p)

read = [False] * N  # read[i]:本iを読んだことがあればTrue
ans_lst = []


def dfs(v):
    if not read[v]:
        for nv in G[v]:
            if read[nv]:
                continue
            dfs(nv)
            read[nv] = True
            ans_lst.append(nv + 1)


dfs(0)
print(*ans_lst)

別解

トポロジカルソートをつかった解法

「すべての本を読める」という前提が問題文にあるので、たとえば「本1を読むために本3を読まないといけなくて、本3を読むために本1が必要で、ループしちゃうせいで本1が読めませんでした」みたいなことは起こりません。グラフで言うと、サイクルが存在しないことになります。
このようなグラフ上で、「 $i<j$ のとき、2頂点 $A_i, A_j$ について必ず $A_j$ → $A_i$ の辺が存在しない」を満たすようなリスト $A$ をつくるのは「トポロジカルソート」でした。

「本 $i$ を読むのに本 $j$ を読まないといけない」を有向辺 $j$ → $i$ だと見ることにして、この有向グラフをトポロジカルソートします。・・・(A)
読まないといけない本は、「本 $i$ を読むのに本 $j$ を読まないといけない」を有向辺 $i$ → $j$ だと見たときの有向グラフ上で、本1をスタート地点にした幅優先探索BFSをすることで、すべてリストアップできます。・・・(B)

(A)でトポロジカルソートした順に本を1つずつ見ていって、もしそれが読まないといけない本(これは(B)からわかる)だったら読むことにすればいいです。

トポロジカルソートは、強連結成分分解SCCをすることでできます。SCCは言語アップデートで新しく入ったac-library-pythonに入っているので、ありがたくインポートしてつかわせてもらいましょう。

from collections import deque
from atcoder.scc import SCCGraph

N = int(input())
G = []
scc_g = SCCGraph(N)
for i in range(N):
    c, *p = map(lambda x: int(x) - 1, input().split())
    G.append(p)
    for j in p:
        scc_g.add_edge(j, i)
scc = scc_g.scc()

seen = [False] * N
seen[0] = True
que = deque()
que.append(0)
while que:
    v = que.popleft()
    for nv in G[v]:
        if seen[nv]:
            continue
        seen[nv] = True
        que.append(nv)

ans_lst = []
for group in scc:
    v=group.pop()
    if seen[v] and v != 0:
        ans_lst.append(v + 1)
print(*ans_lst)

F - Shortcuts

問題ページ

考察

まず愚直なTLEしてしまう解法として、頂点番号とスルーした回数を引数にした2次元DPがあります。

$dp[i][j]$ : 頂点 $i$ にいて、いままで $j$ 回だけチェックポイントをスルーした状態になるまでの最短距離

このDPは、そもそもマスの数が $N^2 \leq (10^4)^2=10^8$ 個もあって、しかも $dp[i][j]$ を求めるときに $dp[i-1][j], dp[i-2][j-1], \cdots ,dp[i-j-1][0]$ の計 $j+1$ 個を参照しないといけなくて、全体としての計算量は $O(N^3)$ です。

ここで、答えがめちゃくちゃに大きくなるような最悪のケースはどれくらいになるのかを考えてみます(「なにかの値が実は最悪でも×××以下で、それに気づくのが1つのポイントでした～」の問題はそこそこ出題されます)。

チェックポイントが全部で $10^4$個あって、偶数番目のチェックポイントが $(0,0)$ で、奇数番目のチェックポイントが $(10^4, 10^4)$ のときを考えてみます。

まず全部のチェックポイントをちゃんと通過するときを考えます、ペナルティは $0$ です。総移動距離は、移動1回あたり $10^4 \times \sqrt{2}$ なので、全体で $(10^4 \times \sqrt{2}) \times 10^4 = 10^8 \times \sqrt{2}$ です。めちゃくちゃ移動しないといけない嫌がらせみたいなチェックポイントの配置にされても、答えはこの $10^8 \times \sqrt{2}$ を超えないことが分かりました。

次に、全部のチェックポイントをスルーしてみます(本当は最後のチェックポイントに行かないといけないですが、概算したいだけなのでざっくりしたお話です)。総移動距離は $0$ で、ペナルティが $2^{10000}$ です。$2^{10} \fallingdotseq 10^3$ なので、 $2^{10000} \fallingdotseq 10^{3000}$ です。

...やばいです。さっき全部のチェックポイントを通過してみたときのスコア $10^8 \times \sqrt{2}$ と桁が違いすぎます。「あんまりスルーしない方がいいんじゃない？」になります。

どれくらいまでスルーしていいんでしょうか。厳密な計算はおいといて、たとえば$30$ 回スルーしたときのペナルティは $2^{30} \fallingdotseq 10^9$ です。スコアが $10^8 \times \sqrt{2}$ を超えることはないはずなので、 $30$ 回もスルーしてはいけないみたいです。

実はこれでほとんど問題は解けています。最初に書いた2次元DPで、チェックポイントをスルーしていい回数を最大で $30$ 回にしてあげます。スルーできる回数の上限を $c (c=30)$ として、計算量が $O(N^3)$ から $O(Nc^2)$ に落ちています。

あとはこの2次元DPの表を埋めて、最後のチェックポイントについてスルーした回数ごとにペナルティもプラスして最小値を求めればACです。

コード

INF = 1 << 40

N = int(input())
c = 30  # スルーできる回数の上限
checkpoint = [tuple(map(int, input().split())) for _ in range(N)]


# チェックポイントi,j間の距離
def dist(i, j):
    xi, yi = checkpoint[i]
    xj, yj = checkpoint[j]
    dx = xi - xj
    dy = yi - yj
    return (dx * dx + dy * dy) ** 0.5


# penalty[i]: チェックポイントをi回スルーしたときのペナルティ
penalty = [0, 1]
for _ in range(c):
    penalty.append(penalty[-1] << 1)

# dp[i][j]: 最終地点i、スルーした回数jの最短距離
dp = [[INF] * c for _ in range(N)]
dp[0][0] = 0

for i in range(1, N):
    for j in range(c):
        d = i - 1 - j
        for i2 in range(i - 1, -1, -1):
            j2 = i2 - d
            if j2 < 0:
                break
            dp[i][j] = min(dp[i][j], dp[i2][j2] + dist(i, i2))

ans = INF
for j in range(c):
    ans = min(ans, dp[N - 1][j] + penalty[j])
print(ans)