htkb-proconの日記

初心者がPythonで問題解いた記録

第5回 ドワンゴからの挑戦状 予選

oo--- 1540 -> 1542

A - Thumbnail

AC: Submission #3652781 - Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選

解説では平均値と数列の各項にNをかけて整数での比較を勧めているが、そこまで頭が回らなかった。誤差でWA食らってたらなんでWAなのかすぐに気付けたか怪しい。こわい。

B - Sum AND Subarrays

AC: Submission #3657153 - Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選

全然解法が浮かばなくて迷走しものすごい時間を食ってしまった。この問題の重要な気付きとして、立てられるビットの中で最上位ビットを立てることが必ず最善だということがある(当たり前だけど)。辞書順最小なんかと似たような感じで、

10000(2) = 16

は、下位ビットが全て立っている

01111(2) = 15

よりも真に大きいので、上位ビットから見ていって立てられるビットはその時点で確定していく貪欲が最善となる。部分列の和N(N+1)/2個を全列挙し、その全てに対して最上位ビットから順に見ていき、ビットが立っている部分和の個数がK個以上ならばそのビットは確定(ansに加算)。下のビットを見るときは、すでに確定したビットが立っている部分和のみを対象に集計を行う。

ans = 0 # 確定ビットを加算していく

for bit in range(max_bit, -1, -1):
    bit, count = 2**bit, 0
    for n in subtotal_list:
        if n & ans != ans:
            # 確定ビットが全部立ってない数は集計対象外
            continue
        if n & bit:
            # 今見ているビットが立っている
            count += 1

    if count >= K:
        ans += bit

丁寧に書くとこんな感じ。計算量はO(N^2・log(max(部分和)))な感じでもう全然駄目な感じなので最初からpypyで投げて通した。終了後pythonで投げたら余裕でTLEだったのでよかった。でもpythonで通してる人もいるので頑張ればなんとかなるんだろう。

C - k-DMC

Q=1のケースでもうまい数え方が全く浮かばなかったのでダメ。解説にある状態の持ち方は全く思いつけなかったので覚えておきたい。でほぼ写経して提出したらpythonでもpypyでも通らず、試行錯誤して一応(無理やり)通した。

Submission #3666266 - Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選

pypyは単にpythonより早いってわけじゃなくかなり性質が違いそう(pythonでクソ遅いa[i]のようなindexingが、pypyではenumerateで値回すより早かったりする?とか)なのである程度調べておいたほうが良さそうかも