久々のコンテスト参加です。

A

日本語読解に苦労したが、サンプルからT/Xが解と推測して提出しました。

B

難易度の割に時間を食ってしまった問題。最初、以下のコードを書いたらサンプル1から通らなくて焦りました。

N = int(input())
L = map(int, input().split())
ans = 'Yes' if 2 * max(L) < sum(L) else 'No'
print(ans)

2, 3分printデバッグしながら考えて、L がgeneratorになっていることに気づく。 L の右辺をリストに変換して、無事通しました。

C

ざっと読んで難しそうだと感じました。以下の思考順序でアルゴリズムを導きました。

コマの初期位置はM個の地点に置くべきだろう（わざわざM個の地点以外に置くメリットはない）
各コマはバラバラの地点に置くべきだろう
各コマはなるべく離れた地点に置くべきだろう（サンプル1なら、あるコマは地点3, 4を担当させ、もう片方のコマは地点1, 2, 5を担当させるべきだろう）
各コマはそれが担当する地点のうち、最も左の地点に初期配置すると仮定してもよいだろう（もちろん、右でもよいですが）。
この問題は「M個の地点のうち、一番左の地点のコマを置き、N-1回コマをジャンプさせることができるとして、一番右の地点まで何回動かす必要があるか？」という問題ではないだろうか
ジャンプできる権利は、地点の間が広い区間で行使すべきだろう

実装はそこまで手こずりませんでした。ここまで、14分51秒。

D

結論: 通せずに終わりました。完全に弛んでいますね。

最初、サンプル1を紙に書いて遊びました。 Aの各値の各桁のbitで多数決をとり、

0が多いならば、Xのその桁を1にする
1が多いならば、Xのその桁を0にする

という方針は思いつきました。簡単じゃん、と思ったのですが、XはK以下という制約が思ったより厄介に感じました。例えば、Kが5のとき、Xの最上位ビットを1にすると、2桁目のビットは必ず0にしなければなりません。ここをうまく処理しつつK以下で最適なXを求めるコードが思ったように書けませんでした。あと、ビット演算も久々で、基本的な操作（最上位ビットは何桁か、とか）もすらすら書けなかったです。コンテスト終わる15分前くらいに、サンプルは通るコードはできましたが、2回出して2回WA。無念。

と、コーディング能力の低下が露呈した結果になりました。アルゴリズム自体はそこまで難しくないと思うので、今週中にこの問題を通すコードを書きたい。

コンテスト終了時点で通らなかったコードは以下です。

from math import log2, floor
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = floor(log2(K)) if K > 0 else 0
z = [sum([1 if a & (1 << k) else 0 for a in A]) for k in range(m + 1)]


def f(x):
    return sum(x ^ a for a in A)


def g(r):
    return sum(1 << k if 2 * z[k] > N else 0 for k in range(r))


def h(k, t):
    print(k, t)
    if k == 0:
        return f(t)
    r = floor(log2(k))
    print('@:' + str(f(t + g(r))))
    return max(
      f(t + g(r)),
      h(k - (1 << r), t + (1 << r))
    )


ans = h(K, 0)
print(ans)

感想

久々に刺激的な100分間でした。後半は集中力が欠けちゃいましたけど。次回もなるべく参加します。スキー行く日と被らなければだけど。

Bみたいなグダグダは避けたいですね。あとはビット演算も要復習。

024号文書

主にプログラミング

ABC117 参加メモ

A

B

C

D

感想