pythonでAtCoder -ABC009-

対象

• AtCoder初心者（緑よりもランクが下の人、ABCのCD問題が解けない人）
• pythonがそれなりにかける人
• 数学やプログラミングに対する深い理解を持っていない人
  • Ex) DP, 深さ優先探索, メモ化再帰の実装ができない

動機

AtCoderは全ての問題に対して解説が存在しますが
ざっくり説明を読んでわかった気になっても独力で実装ができないといった経験が多くありました。
参考のために他人の提出を見ても解説と綺麗にリンクした解答が簡単には見つからず
理解を実装に落とすことに苦労しました。

そこで、公式の解答とある程度リンクした実装を見ながら
アルゴリズムや数学的な理解とソースコードを紐付けたいと思ったことが本記事を寄稿した動機です。

いるかわかりませんが同様の苦労をしている人のためにも何らかの参考になればと思い
私の回答とそれに対する簡単なコメントを付与したコードを記載します。

実行環境

• python3

実装

AB → 何も見ずに実装
CD → 解説を見て実装

A

A.py

import math
print(math.ceil(int(input()) / 2))

B

B.py

N = int(input())
A = list(set([int(input()) for _ in range(N)]))
A.sort()
print(A[-2])

C

C.py

from collections import Counter

N, K = map(int, input().split(' '))
S = input()
R = sorted(S)
T = ''
diff = 0

for i in range(N):
    # 各文字の出現回数をカウント
    counter = Counter(S[:i+1]) - Counter(T)
    for r in R:
        # 確定済み文字のdiff + みている文字のdiff
        diff1 = diff + (r != S[i])
        # 確定していない文字のdiff
        diff2 = sum(counter.values()) - (counter[r] > 0)
        if diff1 + diff2 <= K:
            T += r
            R.remove(r)
            diff = diff1
            break
print(T)

D

D.py

def matrix_pow(a, b):
    ret = [[0] * len(b[0]) for _ in range(len(b))]
    for x in range(len(b)):
        for y in range(len(b[0])):
            for z in range(len(b)):
                ret[x][y] ^= a[x][z] & b[z][y]
    return ret


K, M = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
C = list(map(int, input().split(' ')))

if K >= M:
    print(A[M-1])
    exit()


# 漸化式計算用の行列を作成
A.reverse()
matrix = [[0] * len(C) for _ in range(len(C) - 1)]
for i in range(len(C) - 1):
    for j in range(len(C)):
        matrix[i][j] = (1 << 32) - 1 if i == j else 0
matrix.insert(0, C)

# 行列の累乗計算結果をスタック
matrix_list = [[[0] * len(C) for _ in range(len(C))] for _ in range(len(format(M-K, 'b')))]
for i in range(len(matrix_list)):
    mat = matrix if i == 0 else matrix_pow(matrix_list[i-1], matrix_list[i-1])
    for j in range(len(matrix_list[0])):
        for k in range(len(matrix_list[0][0])):
            matrix_list[i][j][k] = mat[j][k]

# フラグが立っている部分で累乗計算を適用
ans = [[a] for a in A]
for m, bit in zip(matrix_list, reversed(format(M-K, 'b'))):
    ans = matrix_pow(m, ans) if bit == '1' else ans
print(ans[0][0])

解説を見て実装をしましたが、TLEになりひたすら苦しめられました。
最終的にPypyなら通る可能性があるとの記事を発見したため、Pypyで提出したら通りました。

終わりに

D問題をpython3でACしている人が10人もおらず驚きました。(Pypyでも1ページ程度)
あまり過去問解いていく人はいないのでしょうか。。

以上です。