AtCoder:ABC117-Dに苦戦したので復習した-ぐぐりらにっき

先頭からいくつかの桁は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関数の累積和をとるところを累積和にしてなくて提出時におちた(サンプルは通る！)」
はひどくて、サンプルは全部通るのに他のテストケースは全部落ちるという。

デバッグがしんどかったです。

AtCoder:ABC117-Dに苦戦したので復習した

0 件のコメント:

コメントを投稿

PROFILE

このブログを検索

POPULAR POSTS

SPONSORED LINK

RECENT POSTS

TWEETS

ARCHIVES

LABEL

CONTACT