結果
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 しか見えてなかったので、
その方針で解けなかったときはちょっと絶望した。
でも、なんとか時間内に解けたのは、僥倖!