CODE FESTIVAL 2015 予選A D - 壊れた電車
問題原文
解法
分で作業が終えることができる時、 分でも作業を終えられる。
つまり単調性があるので、答えを二分探索できる。
次に二分探索内の判定を考える。
これは左詰め(あるいは右詰め)をするように貪欲的に点検していくのが最適。
ただし以下の点に注意する必要がある。
答えの上界は ではない。
例えば で とかだと折り返しが発生する。
だいたい ぐらいに設定しておけばいい。( にしたけど)まず左に残っている点検し残りを処理 → 元の位置まで折り返し → 余った分右に進んで続きを点検、
だけでなく、「(左に残っている点検し残りを処理できるように)右に進んで続きを点検 → 元の位置まで折り返し → 左に残っている点検し残りを処理」 がある。
2にたいそうやられてしまった。
実装
N, M = map(int, input().split()) X = [int(input()) for _ in range(M)] + [N + 1] # 番兵 # にぶたん: T分で点検作業が終わるか? ok, ng = 2 * 10 ** 9, -1 while abs(ok - ng) > 1: T = (ok + ng) // 2 done = 0 for i in range(M): left_remain = X[i] - done - 1 if left_remain > T: break done = X[i] + max(max(0, T - 2 * left_remain), (T - left_remain) // 2) done = min(done, X[i + 1] - 1) if done >= N: ok = T else: ng = T print(ok)
感想
2にたいそうやられてしまった。。。
左詰め貪欲と右詰め貪欲をやるだけだと、 , のようなパターンで5にならないんですよね。。。
(両方端まで塗って折り返すのが最適のため)
Donutsプロコンチャレンジ2015 B - Tokyo 7th シスターズ
問題原文
解法
なんかすごそう。
入力がとてもとてもめんどくさそう。
少し落ち着いて見ると、 程度なので全部試せることがわかる。
実装
from itertools import combinations N, M = map(int, input().split()) A = list(map(int, input().split())) B, P = [], [] for i in range(M): row = list(map(int, input().split())) B.append(row[0]) P.append(set([r - 1 for r in row[2:]])) ans = 0 for select in combinations(range(N), 9): select = set(list(select)) tmp_ans = 0 tmp_ans += sum([A[s] for s in select]) for b, p in zip(B, P): if len(p & select) >= 3: tmp_ans += b ans = max(ans, tmp_ans) print(ans)
感想
試験管水が解けなくて逃げてきたのだけどこれも水diffゥ!!
Code Formula 2014 予選B C - 仲良し文字列
問題原文
解法
3回のswapで影響範囲があるのは最大6文字まで。それより大きいと3回では足りない。
よって と が異なるindexを列挙しておいて、実際に3回のswapを全探索する。
の中に同じ文字が複数あれば、それらをswapすることで回数を稼げることに注目。
具体的にはそのような場合、 ちょうど3回のswap でなく 3回以下のswap と条件が変わる。
実装
こういうのは再帰で書くのが楽なのではないでしょうか。
from itertools import combinations A = list(input()) B = list(input()) diff = [] dupulicate_char_index = -1 appeared = set() for i, (a, b) in enumerate(zip(A, B)): if a != b: diff.append(i) if a in appeared: dupulicate_char_index = i appeared.add(a) if dupulicate_char_index != -1: diff += [dupulicate_char_index] * (6 - len(diff)) # 達成不可能 if len(diff) > 6: print('NO') exit() def check(a, change_cnt): if (dupulicate_char_index != -1 or change_cnt == 3) and (a == B): print('YES') exit() def dfs(a, depth): if depth == 3: return for i, j in combinations(diff, 2): a[i], a[j] = a[j], a[i] check(a, depth + 1) dfs(a, depth + 1) a[i], a[j] = a[j], a[i] dfs(A, 0) print('NO')
感想
結構難しかった。。。
東京海上日動2020 C - Lamps
問題原文
解法
1回分の操作はいもす法を使うことで でできる。
これを 回行うので、 、さてどう高速化するか。。。となるけど、実は愚直にやっても 回程度の操作で に収束する。
ので、実際には で答えを求められる。
のケースを手計算してたら気がついた。
一番操作回数が多くなるのは で、両端が一番 になるまで時間がかかる、という事実をもとにちゃんと観察すればまだはやく気づけたかも。(だいたい倍々になっていく)
実装
from itertools import accumulate N, K = map(int, input().split()) A = list(map(int, input().split())) def calc_imos(arr): imos = [0] * (N + 1) for i, a in enumerate(arr): l = max(0, i - a) r = min(N - 1, i + a) imos[l] += 1 imos[r + 1] -= 1 imos = list(accumulate(imos)) return imos[:-1] for k in range(min(50, K)): A = calc_imos(A) print(*A, sep=' ')
感想
えーん、もう少し早く解きたかった。
ARC011 C - ダブレット
問題原文
解法
グラフ構築 + BFS + 経路復元、という問題。
グラフ構築
「1文字変えたら相手の文字列になれる」ような , を見つけ、その間に辺を張ってグラフをつくる。
単語の文字数は MAX30文字らしいので、愚直にやっても大丈夫。
BFS
辺のコストが全て1なので、単純なBFSで最短経路長が求められる。
復元できるように「どこから来たか」の情報を格納しながらやる。
経路復元
BFSのときにやった「どこから来たか」の情報を逆に辿りながら復元する。
sample2みたいな最初からゴールしてるやつがあるので注意(だるいので別で分けた)
実装
from collections import deque start, end = input().split() N = int(input()) words = [start] + [input() for _ in range(N)] + [end] G = [[] for _ in range(N + 2)] # だるいので別処理 if start == end: print(0) print(start) print(end) exit() # グラフ構築 for i, word1 in enumerate(words): for j, word2 in enumerate(words): diff = 0 for c1, c2 in zip(word1, word2): if c1 != c2: diff += 1 if diff > 1: break else: if diff == 1: G[i].append(j) # 復元できるようにしながらBFS que = deque([0]) froms = [None] * (N + 2) froms[0] = -1 while que: n = que.pop() for to in G[n]: if froms[to] is not None: continue que.appendleft(to) froms[to] = n # 答えを計算 if froms[-1] is None: print(-1) else: ans_num = 0 ans_words = [] marker = N + 1 while marker != -1: ans_num += 1 ans_words.append(words[marker]) marker = froms[marker] print(ans_num - 2) print(*ans_words[::-1], sep="\n")
感想
PASTででそう(雑)
ARC040 C - Z塗り
問題原文
解法
上から & 右から優先でみていけばいいです!
右上残しても結局後から塗らなきゃならないからね!おわり!
実装
N = int(input()) S = [list(input()) for _ in range(N)] S.append(['o'] * N) # 番兵 ans = 0 for r in range(N): for c in reversed(range(N)): if S[r][c] == '.': S[r] = ['o'] * (c + 1) + S[r][c + 1:] S[r + 1] = S[r + 1][:c] + ['o'] * (N - c) ans += 1 break print(ans)
感想
PAST初級で出そう!おわり!
ABC015 D - 高橋くんの苦悩
問題原文
解法
ナップサック問題発展版。「個数」という制約が追加されている。
やり方はいろいろあると思うんですが、 がなんか嫌な予感がしたので、「価値に対する最小の重さ」っぽくやりました。
詳しくは実装がわかりやすいかと。
実装
ちょっとサボっている。
PyPy3で700ms、142MBぐらい。
直前の配列だけ持つようにすれば想定解でもMLEしないのかな。しらんけど。
W = int(input()) N, K = map(int, input().split()) Items = [list(map(int, input().split())) for _ in range(N)] MAX_V = 50 * 100 INF = 10 ** 9 # dp[i][k][v] := i番目まで見てk個選んだ時に価値の総和がvになるために必要な最小幅合計 dp = [[[INF] * (MAX_V + 1) for j in range(K + 1)] for i in range(N + 1)] dp[0][0][0] = 0 for i, (a, b) in enumerate(Items): for k in range(K + 1): for v in range(MAX_V + 1): dp[i + 1][k][v] = min(dp[i + 1][k][v], dp[i][k][v]) if v + b <= MAX_V and k + 1 <= K: dp[i + 1][k + 1][v + b] = min(dp[i + 1][k + 1][v + b], dp[i][k][v] + a) ans = 0 for k in range(K + 1): for v in range(MAX_V + 1): if dp[-1][k][v] <= W: ans = max(ans, v) print(ans)
感想
サクッと解けたけど、数ヶ月前は手も足も出なかっただろうな。。。
dpは成長を感じられてうれしい。