#--------- 入力例 ---------- s = "FisHDoGCaTAAAaAAbCAC" #--------------------------- words = [] # 単語のリスト
# 文字列 s を単語ごとに分解する i = 0 while i < len(s): j = i + 1# s[j] が大文字になる j を見つける while j < len(s) and s[j].islower(): j += 1 # 単語を切り出してリストに追加 words.append(s[i:j + 1])
i = j + 1# i を j + 1 に移動
# 単語を大文字小文字を無視した状態でソート words = sorted(words, key=str.lower)
res = 0 for p inrange(m // 5 + 1): # グーを出せる回数分ループ c = (m - p * 5) // 2# チョキの回数を求める g = n - p - c # グーの回数を求める if g < 0: # グーの回数がマイナスの場合パス pass elif p * 5 + c * 2 == m: # 指の合計本数が指定回数と同じ場合 x = min(cnt_g, p) + min(cnt_p, c) + min(cnt_c, g) res = max(res, x)
#--------- 入力例 ---------- m = 4# M日後 # (days)日後に、(reward)の報酬を受け取れる仕事 jobs = [{'days':4, 'reward':3}, {'days':4, 'reward':1}, {'days':2, 'reward':2}] #--------------------------- from heapq import heappush, heappop
# days_reward[v]：days[i] = v となる i に対する reward[i] の集合 days_reward = [[] for _ inrange(m + 1)] for job in jobs: # 報酬の支払いが M 日を超える場合はパス if job['days'] > m: pass else: # データ登録 days_reward[job['days']].append(job['reward'])
res = 0# 報酬の最大値 que = [] # ヒープ
# M - 1 日目から 0 日目へとさかのぼる(days_reward[0]から順に見る) for reward in days_reward: for reward1 in reward: # ヒープは小さい順となるので符号反転して追加 heappush(que, reward1 * -1) if que: x = heappop(que) res -= x
from itertools import combinations_with_replacement #--------- 入力例 ---------- n, m, q = 3, 4, 3 a = [1, 1, 2] b = [3, 2, 3] c = [3, 2, 2] d = [100, 10, 10] #--------------------------- # 添字(a, b)を0始まりにする for i inrange(q): a[i] -= 1 b[i] -= 1
# 数列Ａのスコアを算出 defcalc_score(A): score = 0 for ai, bi, ci, di inzip(a, b, c, d): if A[bi] - A [ai] == ci: score += di return score
res = 0# 最大値 # 数列Ａを全探索する for A in combinations_with_replacement(range(1, m + 1), n): x = calc_score(A) print(A, x) res = max(res, x) print('------------------') print('解（最大値）：', res)