30歳で競プロに目覚めた霊長類のブログ

ウホウホ (競プロの世界にやってきました。がんばります。)

天下一プログラマーコンテスト2017

結果

C,Dの2完。タイム85:20、264位。
レート上がる気がしたけど、Unratedの模様。
まあ、楽しかったので気にしない。

C: 4/N

C: 4/N - Tenka1 Programmer Contest | AtCoder

4⁄N = 1⁄h + 1⁄n + 1⁄w
式を満たす正整数h, n, w を求めよ、って問題。 (h, n, wって何の意味だろう...)


h,n,w <= 3500 を満たす解が存在するとのことだけど、
組み合わせを全部試すのはO(M3)でもちろん無理。M=3500。

よく考えたら3つの変数のうち2つが決まれば、残り1つが計算で求まるので、
ループするのは2つでおk。
求めた結果が正の整数だったらそれが答え。

M2 だと107 ループ位だから、イケる、、
いや、Pythonだと非常に際どいなー。どうかなー。
と思いながらも、下のようなコードを書いた。

import sys
N = int(input())

def is_int(a):
    return (abs(a - int(a)) < 0.1**8)

for a in range(1, 3501):
    for b in range(a, 3501):
        tmp = 4/N - 1/a - 1/b
        if tmp <= 0: continue
        if is_int(1/tmp):
            c = int(1/tmp)
            print(a, b, c)
            sys.exit()

is_int() は整数判定のために書いたコード。
浮動小数==で比較するのって誤差ありそうでマズかった気がした。
許容誤差10-8 ってのも適切なのか全然分からないけど、もう、エイッと8(エイト)を書いた。

それで、サンプルケース動かしてみたら、
やっぱり、明らかに3つ目のケースで3秒以上かかったのでダメ。
内側のbのループを、1じゃなくaから始めて、ループを半分にする工夫をしてもダメ。

これ以上考えてもしょうがないと思い、上のコードはsubmitせず、Javaで書き直し。
メインPythonなので、TLE対策で最近この手口を使っている。
(最初からそっちで書けよ、と言われそうだけど、いろいろメンドくさいのよ。。。)

というわけで無事にAC。やったね!

Submission #1638385 - Tenka1 Programmer Contest | AtCoder

D: IntegerotS

D: IntegerotS - Tenka1 Programmer Contest | AtCoder

整数A と その価値B の組み合わせが N個与えられて、
そこからいくつか選んで、価値の総和を最大化する問題。
ただし、選んだ整数を全てbitwise OR したときに、Kを超えちゃいけない。


下のコードでACできた!

N,K = map(int,input().split())
masks = [K]

bs = str(bin(K))[2:]
for i in range(len(bs) - 1):
    if bs[i] == '1':
        a = len(bs) - 1 - i
        mask = K - (1 << a)
        mask |= ((1 << a) - 1)
        masks.append(mask)

anss = [0 for i in range(len(masks))]
for i in range(N):
    a,b = map(int,input().split())
    for i,m in enumerate(masks):
        if (m | a) == m:
            anss[i] += b

print(max(anss))

Kが 1010010(2) だとしたら、調べるべき、使えるビット(mask) のパターンは

  • 1010010 (K自身)
  • 0111111 (Kの1番目の1を0にして、あと全部1)
  • 1001111 (Kの2番目の1を0にして、あと全部1)
  • 1010001 (Kの3番目の1を0にして、あと全部1)

の4通りで十分。
なぜなら、例えば0111111(2) の他に、0111110(2)もK以下の数だけど、
最下位のビットを使っていいのと、いけないのでは、使っていい方が価値の総和が高いに決まってる。(価値は正の値)

ちなみに、こういうビットのパターンのこと、マスクって呼び方であってるのか、ちょっと不安。
まあ誰も気にしないか。

ビットを扱うのは慣れてないので、いつも考察に時間がかかっちゃうのが課題。
最初、上の例でいう0111111 しか見えてなかったので、
その方針で解けなかったときはちょっと絶望した。
でも、なんとか時間内に解けたのは、僥倖!

Submission #1640474 - Tenka1 Programmer Contest | AtCoder