pythonでAtCoder -ABC006-

対象

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

動機

AtCoderは全ての問題に対して解説スライドが存在するが
解説をみて何となく理論を理解しても独力で実装ができない場合が多かった。

他の提出を見ても親切に解説コメントがついている回答はあまり存在せず、理解を実装に落とすことに苦労したため、簡単にでも解説がある回答はないものかと思い立ったことが動機である。

同様の苦労をしている人のためにも、稚拙なコードではあるが何らかの参考になればと思い
私の回答とそれに対する簡単なコメントを付与したコードをアップロードする。

実行環境

• python3

A

print('YES' if int(input()) % 3 == 0 else 'NO')

pythonは単純なif else が1行で書けます。

B

N = int(input())
S = [0, 0, 1]
if N <= len(S):
    print(S[N-1])
else:
    for i in range(len(S), N-1):
        S[i % 3] = sum(S) % 10007
    print(sum(S) % 10007)

トリボナッチ数列と呼ばれる数列を計算する問題。
注意点として

• 和を素直に持ち続けるとTLE(Time Limit Exceeded)になってしまう
  ことが挙げられます。
  この対策のために和に対して10007の余りをとりながら処理を実行しています。

C

N, M = map(int, input().split(' '))

if M % 4 == 0:
    ans = (M//2-(M//2-N)*2, 0, M//2-N) if M//4 <= N <= M//2 else (-1, -1, -1)
elif M % 4 == 2:
    ans = (M//2-(M//2-N)*2, 0, M//2-N) if M//4+1 <= N <= M//2 else (-1, -1, -1)
else:
    ans = (M//2-(M//2-N)*2-1, 1, M//2-N) if M//4+1 <= N <= M//2 else (-1, -1, -1)
print(ans[0], ans[1], ans[2])

カオスな数式ですが、条件式から読み解くとわかりやすいかと思います。

可能な限り赤ちゃんで構成すると必要最小人数がわかり、可能な限り大人で構成すると必要最大人数が分かります。指定の人数がこの範囲に入っていない場合は構成ができません。

組み合わせの中身については、赤ちゃんを1人減らして大人を2人増やすと足の数を変えずに人間の数を変えることができるので、求まります。足が奇数の場合1人、偶数の場合は０人でOKです。

D

from bisect import bisect_left
N = int(input())
C = [int(input()) for _ in range(N)]
S = [0]
for c in C:
    i = bisect_left(S, c)
    if len(S) == i:
        S += [c]
    else:
        S[i] = c
print(N - len(S) + 1)

終わりに

B問題が普段より難しかったですね。
次回もよろしくお願いします。