AtCoder:ABC117-Dに苦戦したので復習した - 2月 04, 2019 こんにちは、ぐぐりら(@guglilac)です。 AtCoder:ABC117に参加しましたが、前回の記事に書いた通りDが嘘解法でした。 悔しいので復習していたら苦戦したので備忘録に載せておきます。 前回の記事はこちらになります。 AtCoder:ABC117に参加した 先頭からいくつかの桁はKと同じで、ある桁でKが1、Xが0になって、その後ろは貪欲にやる、というのをKの桁が1になってる全ての桁について調べてmaxをとる、という解法が想定解法っぽいので、それで書き直す。 前処理部分は前書いたのと同じです。 ```python N, K = map(int, input().split()) A = list(map(int, input().split())) binary = [bin(a) for a in A] bin_K = bin(K) ma_len = max([len(e) for e in binary] + [len(bin_K)]) - 2 B = [e[2:].zfill(ma_len) for e in binary] bin_K = bin_K[2:].zfill(ma_len) ``` ```python def latter(div, ma_len, B, bin_K): X = [] for i in range(div, ma_len): num_0 = 0 num_1 = 0 for j in range(len(B)): if B[j][i] == "0": num_0 += 1 else: num_1 += 1 if num_1 >= num_0: X.append("0") else: X.append("1") return X ``` サンプルは通ったけど、TLEとWAがいくつか。 毎回このlatter関数を呼び出して貪欲部分を再計算していたけど、それだと無駄があってTLEしてしまうので、あらかじめ後ろ$i$桁を貪欲した時のXのbit表示を計算しておこうとしたのが次のgreedy関数。 ```python def greedy(ma_len, B, bin_K): result = [] X = [] for i in range(ma_len - 1): num_1 = 0 num_0 = 0 for j in range(len(B)): if B[j][ma_len - i - 1] == "0": num_0 += 1 else: num_1 += 1 if num_1 >= num_0: X.append("0") else: X.append("1") result.append(list(X)) return list(reversed(result)) + [[]] former = [] cand = [bin_K] latter = greedy(ma_len, B, bin_K) # print(latter) for i in range(ma_len): if bin_K[i] == "1": cand.append("".join(former + ["0"] + latter[i])) former.append(bin_K[i]) # print(B) # print(bin_K) # print(cand) print(max([sum([int(e, 2) ^ int(b, 2) for b in B]) for e in cand])) ``` これでもなおTLEとWAがでて、つらい Xの候補となるもののbit表示を求めて全部関数$f(X)$を計算してっていうのは無駄があるなあとか、毎回$2^k$をかけてとかやるの間違えそうだったので、思い切って全部書き換えることに ```python def greedy(C): result = [] s = 0 for i in range(len(C) - 1): s += C[len(C) - i - 1]["score"] * \ max(C[len(C) - i - 1]["1"], C[len(C) - i - 1]["0"]) result.append(s) return list(reversed(result)) + [0] C = [] for i in range(ma_len): c = {"0": 0, "1": 0} for j in range(N): c[B[j][i]] += 1 c["score"] = 2**(ma_len - i - 1) C.append(c) latter = greedy(C) ans = 0 former = 0 for i in range(ma_len): if bin_K[i] == "1": ans = max(ans, former + C[i]["1"] * C[i]["score"] + latter[i]) former += C[i]["score"] * C[i]["0"] else: former += C[i]["score"] * C[i]["1"] print(max(ans, former)) ``` これでACしました。 いくつかはまったところは * greedy関数の累積和をとるところを累積和にしてなくて提出時におちた(サンプルは通る!) * K=0のときに一度も`if bin_K[i] == "1"`をとおらないで0を出力するので、formerも候補に入れる などでした。 特に一つ目の「greedy関数の累積和をとるところを累積和にしてなくて提出時におちた(サンプルは通る!)」 はひどくて、サンプルは全部通るのに他のテストケースは全部落ちるという。 デバッグがしんどかったです。 この記事をシェアする Twitter Facebook Google+ B!はてブ Pocket Feedly コメント
コメント
コメントを投稿