「diverta 2019 Programming Contest」をPythonで解く

A〜Dまで解きました。

atcoder.jp

A - Consecutive Integers（100点）

• サンプルなど、実際に具体的な数字で考えると良い

N, K = list(map(int, input().split()))
print(N - K + 1)

B - RGB Boxes（200点）

• r, gを固定したときにbが答えとなり得るか（割り切れる数字か）を考える
• pythonでも時間的に危ないが通った（提出）

R, G, B, N = list(map(int, input().split()))

cnt = 0
for r in range(N//R + 1):
    for g in range((N - r*R)//G + 1):
        if (N-r*R-g*G) % B == 0:
            cnt += 1

print(cnt)

C - AB Substrings（400点）

• まずは結合前の各文字列内の'AB'の数を数えておく
• あとは結合でいくつ増やせるか
• 解説の場合分けを考えれば良い
  • 'BCCCCA'が2つあっても、増やせる'AB'は2個ではなく1個

N = int(input())
S = [input() for i in range(N)]

cnt_ab_from_S = sum([s.count('AB') for s in S])
start_from_b_and_end_at_a = sum([(s[0] == 'B') and (s[-1] == 'A') for s in S])
not_start_from_b_and_end_at_a = sum([(s[0] != 'B') and (s[-1] == 'A') for s in S])
start_from_b_and_not_end_at_a = sum([(s[0] == 'B') and (s[-1] != 'A') for s in S])

ans = cnt_ab_from_S
if (start_from_b_and_end_at_a == 0):
    ans += min(not_start_from_b_and_end_at_a, start_from_b_and_not_end_at_a)
elif (not_start_from_b_and_end_at_a + start_from_b_and_not_end_at_a == 0):
    ans += (start_from_b_and_end_at_a - 1)
else:
    ans += (start_from_b_and_end_at_a + min(not_start_from_b_and_end_at_a, start_from_b_and_not_end_at_a))
print(ans)

D - DivRem Number（500点）

問題文の条件を数式で表すと、次のようになる。

(N - N%m)/m = N%m

ここで k = N%m と置いて整理すると、次の式を得る。

N = k(m + 1)

つまり、(m + 1) は N の約数である必要がある。ただしあくまで必要条件でしかないので、あとは候補の十分条件をそれぞれ確認する。

約数の候補を得るのは、次の実装などが高速。

qiita.com

N = int(input())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


ans = 0
divisors = make_divisors(N)

for d in divisors:
    m = (d - 1)
    if m and (N//m == N % m):
        ans += m

print(ans)