[Python3] AtCoder Beginner Contest 048

たまには競技プログラミングも、ということでABC048に挑戦。
http://abc048.contest.atcoder.jp/assignments
C++は日常的に使うことが無くなってきたので、最近出番の多いPython3で挑戦。

A - AtCoder *** Contest

２語目の頭文字を出力すればよい。変数展開にはformatを。

s = input()[8]
print("A{0}C".format(s))

B - Between a and b ...

0からaまで、0からbまでと分けてxで割って切り捨て。

a,b,x = list(map(int, input().split()))
ans = max((b//x)-((a-1)//x),0)
print(ans)

C - Boxes and Candies

2箱ずつ見ていくが、後ろの箱からできるかぎり抽出していくのが最適。（貪欲法）
左から1箱ずつ見ていって、条件を満たすように処理していけば計算量$O(N)$

N, x = list(map(int, input().split()))
arr = list(map(int, input().split()))

cnt, prv = 0, 0

for i in range(N):
    diff = max(arr[i] + prv - x, 0)
    cnt += diff
    arr[i] -= diff
    prv = arr[i]

print(cnt)

D - An Ordinary Game

全通り試すと$O(N!)$になるし、DPでも上手く解けそうにない。調べると、交互にプレイして動けなくなった方が負け、といったゲームはNIMというゲームと同型であることが多いことがわかった。

• 2人
• 盤面の情報は公開
• 勝つか負けるか2値

極限状態を考えるといいようなので、遷移しきって勝敗が付く状態（最終状態）を考えると、

• 最初と最後の文字が一致していると、
• 最終状態の文字数はかならず奇数になる

ことがわかる。

この場合、交互にプレイするゲームなので、初期状態の文字数の偶奇でどちらが勝つかが一意に定まる。

逆に最初と最後の文字が一致していないと最終状態の文字数は偶数なので、その判定だけすればよい。

s = input()
xor = bool(len(s)%2==0) ^ bool(s[0]==s[-1])
print("Second" if xor else "First")