#--------- 入力例 ----------- N = 7# 草の数 S = ['A', 'A', 'B', 'A', 'B', 'B'] # 隣合う草の高低情報 #---------------------------- # 配列の準備 ret1 = [ None ] * N ret2 = [ None ] * N
# 1からNへ'A'の連続数を数える sa = 1# 'A'の連続回数 ret1[0] = 1 for i inrange(N - 1): if S[i] == 'A': sa += 1 if S[i] == 'B': sa = 1 ret1[i + 1] = sa print('ret1', ret1)
# Nから1へ'B'の連続数を数える sa = 1# 'B'の連続回数 ret2[N - 1] = 1 for i inreversed(range(N - 1)): if S[i] == 'A': sa = 1 if S[i] == 'B': sa += 1 ret2[i] = sa print('ret2', ret2)
# 連続数の多いほうを選ぶ ret3 = [max(a, b) for a, b inzip(ret1, ret2)] print('ret3', ret3)
#--------- 入力例１ --------- N = 15# 要素数 X = 47# 探す要素 A = [8, 13, 17, 19, 24, 27, 33, 37, 41, 43, 47, 53, 59, 61, 68] #--------- 入力例２ --------- # N = 10 # 要素数 # X = 80 # 探す要素 # A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] #---------------------------- # 整数 x が何番目に存在するかを返す関数 defsearch(x, A): L = 0 R = N - 1 while L <= R: M = (L + R) // 2 if x < A[M]: print('求める要素{}は、要素{}({}番目)より小さい'.format(x, A[M], M)) R = M - 1 if x == A[M]: print('求める要素{}は、要素{}({}番目)と同じ'.format(x, A[M], M)) return M if x > A[M]: print('求める要素{}は、要素{}({}番目)より大きい'.format(x, A[M], M)) L = M + 1 return - 1# 整数 x が存在しない（注：この問題の制約で -1 が返されることはない）
🔹白色のカードに書き込む整数を $ x $ とする。 🔹青色のカードに書き込む整数を $ y $ とする。 🔹赤色のカードに書き込む数字は $ K - x - y $ となる。
この方法ですと３枚全部ではなく２枚の書き方のみを全探索するという解法が成り立ちます。
計算量は $ O(N^2) $ であり、十分に実行が可能です。
[Google Colaboratory]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
#--------- 入力例1 --------- N = 3# カードに記入できる数字の最大値 K = 6# 合計値 #--------- 入力例2 --------- # N = 3000 # カードに記入できる数字の最大値 # K = 4000 # 合計値 #--------------------------- Answer = 0 # 全探索 for x inrange(1, N + 1): for y inrange(1, N + 1): z = K - x - y if z >= 1and z <= N: Answer += 1
#--------- 入力例 ---------- N = 5 S = 7 A = [2, 1, 3, 8, 2] #--------------------------- # 動的計画法（i=0） dp = [[ None ] * (S + 1) for i inrange(N + 1)] dp[0][0] = True for i inrange(1, S + 1): dp[0][i] = False
# 動的計画法（i=1） for i inrange(1, N + 1): # カードの枚数分ループ for j inrange(0, S + 1): # 0から合計値Sまでループ if dp[i - 1][j] or (j - A[i - 1] > -1and dp[i - 1][j -A[i - 1]]): dp[i][j] = True else: dp[i][j] = False
# 答えの復元 Answer = [] Place = S for i inreversed(range(1, N + 1)): # 合計値Sから、1までループ（今回の場合:5,4,3,2,1） if dp[i - 1][Place]: Place = Place - 0# カード i を選ばない else: Place = Place - A[i - 1] # カード i を選ぶ Answer.append(i)
# 答えを出力（インデックスよりカードに書かれた数字を出力） print('解：', ' '.join(str(A[i - 1]) for i inreversed(Answer)))
#--------- 入力例1 --------- N = 3 S = 7 A = [2, 2, 3] #--------- 入力例2 --------- # N = 3 # S = 6 # A = [2, 2, 3] #--------------------------- # 動的計画法（i=0） dp = [[ None ] * (S + 1) for i inrange(N + 1)] dp[0][0] = True for i inrange(1, S + 1): dp[0][i] = False
# 動的計画法（i=1） for i inrange(1, N + 1): # カードの枚数分ループ for j inrange(0, S + 1): # 0から合計値Sまでループ if dp[i - 1][j] or (j - A[i - 1] > -1and dp[i - 1][j - A[i - 1]]): dp[i][j] = True else: dp[i][j] = False