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)