ABC021を解いてみた

A問題

　nが8より大きいか、4より大きいか…と貪欲的に判定していきました。
A問題にしては難しいなーと思ったら数字の重複可能なことを見逃してました…

n = int(input())

flag = [0 for _ in range(4)]
count = 0

if n >= 8:
    flag[3] = 1
    n -= 8
    count += 1
if n >= 4:
    flag[2] = 1
    n -= 4
    count += 1
if n >= 2:
    flag[1] = 1
    n -= 2
    count += 1
if n >= 1:
    flag[0] = 1
    n -= 1
    count += 1

print(count)

for i in range(4):
    if flag[i] == 1:
        print(2 ** i)

B問題

　入力例を見て考えると、同じ街を通っていれば最短経路ではないといえそうです。
そこで始点、終点、経由した街に重複がなければYESを出力すれば良さそうです。

import sys

n = int(input())
a, b = map(int, input().split())
k = int(input())
p = [int(i) for i in input().split()]

p.append(a)
p.append(b)

# 重複確認
for i in range(len(p)):
    for j in range(len(p)):
        if i != j and p[i] == p[j]:
            print("NO")
            sys.exit()

print("YES")

C問題

　ワーシャルフロイド法を用いて始点から全ての点への最短経路を求め、始点からメモ化再帰で最短経路を数えたつもりだったんですがREが出てしまいました…　手元の環境では実行時エラーが出せず、直せません…

D問題

　深さ優先探索→メモ化再帰→動的計画法とアルゴリズムを変えていき計算量O(nk)で部分点解法になりました。

# メモ化再帰
n, k = map(int, input().split())

dp = [[0 for i in range(n)] for j in range(k)]
mo = 1000007

def dfs(i, num):
    count = 0
    if(dp[i-1][num-1] != 0):
        return dp[i-1][num-1]
    # print("i:{0} num:{1}".format(i, num))

    if(i == k):
        return 1

    for j in range(n-num+1):
        count = (count + (dfs(i+1, num+j) % mo)) % mo

    dp[i-1][num-1] = count % mo
    print("dp[{0}][{1}] = {2}".format(i-1, num-1, dp[i-1][num-1]))
    return count % mo

ans = 0
for i in range(1, n+1):
    ans = (ans + dfs(1, i)) % mo
print(ans)

# 動的計画法
n = int(input())
k = int(input())

dp = [[0 for i in range(n)] for j in range(k)]
for i in range(n):
    dp[k-1][i] = 1

mo = 1000000007

for i in range(1, k):
    _i = k-i-1
    for j in range(n):
        _j = n-j-1
        if(_j == n-1):
            dp[_i][_j] = dp[_i+1][_j] % mo
        else:
            dp[_i][_j] = (dp[_i+1][_j] + dp[_i][_j+1]) % mo

ans = 0
for i in range(n):
    ans = (ans + dp[0][i]) % mo

print(ans)

次に解説を読んで重複組み合わせの考え方を用いてO(NlogP)で実装したつもりなんですがTLEでした…

n = int(input())
k = int(input())

mod = 1000000007

# 二分累乗法
def pow(x, n, mo):
    if n == 0: return 1
    if n == 1: return x

    if (n%2)==0:
        return ((pow(x, n/2, mod) % mo) ** 2) % mo
    else:
        return (x * (((pow(x, int(n/2), mod) % mo) ** 2) % mo)) % mo

fact = [0 for i in range(n+k)]
ifact = [0 for i in range(n+k)]
fact[0] = 1
ifact[0] = 1

for i in range(1, n+k):
    fact[i] = fact[i-1] * i % mod
    ifact[i] = pow(fact[i], mod-2, mod)

ret = (fact[n+k-1]*ifact[k]%mod)*ifact[n-1]%mod
print(ret)