AtCoder ABC148

AtCoder ABC148解いた分だけまとめ。
今回はABCDの4完。今回は易しかった気がする。
Eは純粋に再帰関数で解こうとして深さ制限に引っかかり爆死。
あれ、多分再帰関数だけでなく素因数分解要素もあったよなーとは思った。
そう思えただけ少しは精進が効いたと思うことにする。

目次

• A問題
• B問題
• C問題
• D問題

追記 2019.12.23 - E問題

A. Round One

問題文 答えが1,2,3しかないので、a,b以外のものを出しておしまい

#coding:utf-8
a = int(input())
b = int(input())
ans = [1, 2, 3]

for i in ans:
    if i != a and i != b:
        print(i)
        break

B. Strings with the Same Length

問題文

2つの文字列を1文字ずつ取り出して交互に出力するだけ。
あっさりfor文を回して、文字を連結させて繰り返し出力する。

#coding:utf-8
n = int(input())
s, t = map(str, input().split())
ans = []

for i in range(0, n):
    ans.append(s[i]+t[i])

print(''.join(ans))

C. Snack

問題文

結局は最小公倍数を求める問題に帰結。
AtCoderは2019年12月時点でPython3.4.3なので、gcdのライブラリがfractionsにある。
Python3.5以降はmathにある。その点だけ気をつけて実装する。

#coding:utf-8
import fractions
#import math

#最小公倍数
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

if __name__ == "__main__":
    a, b = map(int, input().split())
    print(lcm(a, b))

D. Brick Break

問題文

レンガの列の中からいくつか壊して、1,2,3...と順番になるようにする。
壊す数の最小を出すので、若い番号で1が書いてあるところを探してから追いたい。
レンガの順番を入れ替えられるわけではないので、1を最初に探して、
そこから2,3...と探して、残るレンガリスト(brick)に追加。
最後はすべてのレンガから残るレンガの数を引いて、壊した分を出す。

#coding:utf-8
n = int(input())
a = list(map(int, input().split()))
brick = []

#1が書いてあるレンガがない場合は解答なし
if 1 not in a:
    print('-1')
    exit()
else:
    num = 1
    for i in a:
        if i == num:
            brick.append(i)
            num += 1
#print(brick)
print(n-len(brick))

E. Double Factorial

問題文

再帰で解こうとしたけど普通にnの範囲が10¹⁸の時点でタダで解けると思ってはいけない！

こちら、大会中に途中まで書いたコード。
とりあえずf(x)を出してから0をカウントしようとしてしまった... サンプル3で再帰の深さ制限に引っかかって爆死します。
import sys して sys.setrecursionlimit(50000)で再帰の深さを一時的に上げる無駄な抵抗も効かず。

#このままでは解けない
#coding:utf-8
import sys
sys.setrecursionlimit(50000)

#普通に計算するとこれでfxは求まるが、再帰関数の深さ制限にひっかかる
#全部計算するのではなく、多分10の倍数が何回出てくるかが答え
def double_factorial(n):
    if n < 2:
        return 1
    return n * double_factorial(n-2)

if __name__ == "__main__":
    n = int(input())
    num = double_factorial(n)
    print(num)

解説を読むと、nの偶数・奇数の場合で分けましょうとのこと。
0がつくのはnが偶数の時だけで、f(x)について2,5で割り切れる数をカウントするだけだった

#coding;utf-8
n = int(input())
#nが奇数の場合は0
if n % 2 != 0:
    print(0)
    exit()
#偶数の場合は、2と5で割り切れる数を数える
else:
    n //= 10
    ans = n
    while n > 0:
        n //= 5
        ans += n
    print(ans)