PythonでJOI難易度6を埋める #8
stairs - 階段 (Stairs)
解法は思い浮んだけど，実装できず...
]を
段目までの行きかたの場合の数，とすると，
]は
まで一回のジャンブで行ける範囲の
の総和となる．
の累積和を用意すれば，一回のジャンプで
まで行くことができる範囲は二分探索で求めることができる．範囲が分かれば，dpの累積和から
]を求めればよい．1234567の余りをとることに注意．
from bisect import bisect_left #二分探索ライブラリ n, p = map(int, input().split()) h = [int(input()) for _ in range(n)] mod = 1234567 csum_step = [0] for i in range(n): csum_step.append(csum_step[-1] + h[i]) csum_dp = [0, 1] #0, 1段目までの行きかた for i in range(1, n + 1): #2段目~ low = csum_step[i] - p index = bisect_left(csum_step, low) tmp = csum_dp[i] - csum_dp[index] csum_dp.append((csum_dp[-1] + tmp) % mod) print((csum_dp[-1] - csum_dp[-2]) % mod)
PythonでJOI難易度6を埋める #7
C - つらら
indexを付けて，最初のつららの高さでsortする．sortされたつららの配列から高い順に折れる時間を決定していく．
n, l = map(int, input().split()) turara = [[int(input()), i] for i in range(n)] turara_s = sorted(turara, reverse = True) time = [0] * n for i in range(n): index = turara_s[i][1] if index == 0: #一番左のつらら if turara_s[i][0] > turara[1][0]: time[0] = l - turara_s[i][0] else: time[0] = time[1] + l - turara_s[i][0] elif index == n - 1: #一番右のつらら if turara_s[i][0] > turara[-2][0]: time[-1] = l - turara_s[i][0] else: time[-1] = time[-2] + l - turara_s[i][0] else: if turara_s[i][0] > turara[index + 1][0] and turara_s[i][0] > turara[index - 1][0]: #左右より長い time[index] = l - turara_s[i][0] elif turara_s[i][0] > turara[index + 1][0] and turara_s[i][0] < turara[index - 1][0]: #左 > つらら > 右 time[index] = time[index - 1] + l - turara_s[i][0] elif turara_s[i][0] < turara[index + 1][0] and turara_s[i][0] > turara[index - 1][0]: #左 < つらら < 右 time[index] = time[index + 1] + l - turara_s[i][0] elif turara_s[i][0] < turara[index + 1][0] and turara_s[i][0] < turara[index - 1][0]: #左 > つらら < 右 time[index] = max(time[index - 1], time[index + 1]) + l - turara_s[i][0] print(max(time))
PythonでJOI難易度6を埋める #6
メモリが厳しい．
nile - ナイルドットコム (Nile.Com)
問題文から溢れるDP臭．愚直なDPにするとになったから，うまく更新回数を減らす必要がある．
そこで，日目に新しく行くお店(連続して買わないお店)は，前日の最も安い要素から移動することに注目する．そうすると，それぞれの日ごとにその日の最小値を計算して，次の日の計算に使えばよいことが分かる．
TLEの次はMLEが待っています．雑に配列を作るとMLEで弾かれるので，dp[連続で買ってる回数][お店の番号]だけで管理します．
n, d = map(int, input().split()) dp = [[float('inf')] * n for _ in range(3)] for i in range(d): price = list(map(int, input().split())) if i == 0: pre_min = 0 else: pre_min = min(min(dp[0]), min(dp[1]), min(dp[2])) for j in range(n): dp[0][j], dp[1][j], dp[2][j] = pre_min + price[j], dp[0][j] + price[j] * 0.9, min(dp[1][j], dp[2][j]) + price[j] * 0.7 ans = min(min(dp[0]), min(dp[1]), min(dp[2])) print(int(ans))
PythonでJOI難易度6を埋める #5
解説AC
E - 通勤経路
制約のせいで場合分けが面倒．どこから来て，今どこへ曲れるかを考えて実装する．
w, h = map(int, input().split()) dp = [[[0]*4 for _ in range(w)] for _ in range(h)] for i in range(h): for j in range(w): if i == 0 and j == 0: continue if i == 0: dp[i][j][3] = 1 continue if j == 0: dp[i][j][0] = 1 continue dp[i][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][1]) % 100000 dp[i][j][1] = dp[i - 1][j][3] % 100000 dp[i][j][2] = dp[i][j - 1][0] % 100000 dp[i][j][3] = (dp[i][j - 1][2] + dp[i][j - 1][3]) % 100000 print(sum(dp[-1][-1]) % 100000)
PythonでJOI難易度6を埋める #4
難易度6，初自力AC
B - ピザ
お店の住所の配列に，配達先の住所の要素を挿入する．ここで，お店の住所の配列がsortされているなら，二分探索で挿入先のindexを調べることができる．indexが分かったら，左右どちらのお店が近いかを調べる．
from bisect import bisect_left d = int(input()) n = int(input()) m = int(input()) stores = [int(input()) for _ in range(n - 1)] deliver = [int(input()) for _ in range(m)] stores.append(0) #本店の住所 stores.append(d) #本店の住所 stores.sort() deliver.sort() ans = 0 for i in range(m): index = bisect_left(stores, deliver[i]) ans += min(abs(deliver[i] - stores[index]), abs(deliver[i] - stores[index - 1])) print(ans)
PythonでJOI難易度6を埋める #3
解説AC．
C - 連鎖
どこの色を変えるかを回調べて，それぞれで何連鎖するか計算します．
from collections import Counter n = int(input()) p = [int(input()) for _ in range(n)] ans = n for i in range(n - 3): delete = p[i: i + 4] color, cnt = Counter(delete).most_common(1)[0] if cnt != 3: #同じ要素が3個存在しない→色を変えても消えない continue #一回目の操作で，最大何個消えるか left, right = i - 1, i + 4 while left >= 0 and p[left] == color: left -= 1 while right < n and p[right] == color: right += 1 ans = min(ans, n - (right - left - 1)) #-1を忘れない #連鎖の処理 while left >= 0 and right < n: #一連鎖ごとに調べる cnt = 0 if p[left] == p[right]: color = p[left] while left >= 0 and p[left] == color: #左側がどこまで消えるかの確認 left -= 1 cnt += 1 while right < n and p[right] == color: #右側がどこまで消えるかの確認 right += 1 cnt += 1 if cnt < 4: #連鎖なし break else: #連鎖あり ans = min(ans, n - (right - left - 1)) print(ans)
PythonでJOI難易度6を埋める #2
期末テストが終わりやっとJOIできると思ったら，あと一週間しかないこの頃．
C - ダーツ
めちゃくちゃ有名?な問題．半分全探索で解けます．
from bisect import bisect_left n, m = map(int, input().split()) p = [int(input()) for _ in range(n)] one_throw = sorted(p) two_throw = [] for i in range(n): for j in range(n): two_throw.append(p[i] + p[j]) two_throw.sort() for i in range(4): if i == 0: #一回投げる index = bisect_left(one_throw, m) if index == 0: continue ans = one_throw[index - 1] if i == 1: #二回投げる index = bisect_left(two_throw, m) if index == 0: continue ans = max(two_throw[index - 1], ans) if i == 2: #三回投げる for j in range(n): w = m - one_throw[j] #許容できるスコア index = bisect_left(two_throw, w) if index == 0: continue ans = max(two_throw[index - 1] + one_throw[j], ans) if i == 3: #四回投げる for j in range(n ** 2): w = m - two_throw[j] index = bisect_left(two_throw, w) if index == 0: continue ans = max(two_throw[index - 1] + two_throw[j], ans) print(ans)
