400点とれなかったー。回答なしで時間切れ後にできるのは悔しい。
これは200点問題だろう、、。解説も要らん。
def solve(N, M, ABs): ABs = sorted(ABs) ans = 0 for a, b in ABs: if b < M: ans += a * b M -= b else: ans += M * a break return ans if __name__ == "__main__": N, M = tuple(map(int, input().split(" "))) ABs = [tuple(map(int, input().split(" "))) for __ in range(N)] print(solve(N, M, ABs))
そしてこっちは2時間かかって爆死。
Aから始まってBの間にはそれぞれのbitで周期性があることはすぐわかるので、この間の1の数を数える。
周期性というのは、例えば、3から10まで書き出したとき、一番下のビットは2つごとに同じビット列が並び、 次のビットは4つごと、さらに次は8つごととなってること。
0000000011 0000000100 0000000101 0000000110 0000000111 0000001000 0000001001 0000001010
どん詰まりしたのは、「Aから始まって、周期の始まり」、「周期中」、「周期の終わりからBまで」の3つをバラバラに求めてカウントしようとしたから。
はまりにはまって、コンテスト終了後に、AからBまでの1の数は「0からBまでの1の数」から「0～A-1までの1の数」を引けばよいことに気が付く。 これは、別のメソッドの切り出して実装。 もっと大局的に考えなきゃならん。
明らかに遅いとわかりつつ、今回はslow_solveの実装が楽だったのでさくっと書いてテストで実行。 これがあるとほぼ完ぺきなテストができるので安心。
countのメソッドに関してはテストそのものを間違えてしまった。0を周期にカウントしなかったために、一つずれていた。 修正は苦労しなかったが気が付くのに時間がかかった、、assertの量が苦労を物語る。
def slow_solve(A, B): ans = A for i in range(A + 1, B + 1): ans = ans ^ i return ans def count(k, cycle): k += 1 tans = (k // cycle) * (cycle // 2) res = k % cycle if res >= cycle // 2: tans += res % (cycle // 2) return tans assert (count(8, 8) == 4) assert (count(7, 8) == 4) assert (count(6, 8) == 3) assert (count(5, 8) == 2) assert (count(4, 8) == 1) assert (count(3, 8) == 0) assert (count(2, 8) == 0) assert (count(1, 8) == 0) assert (count(0, 8) == 0) assert (count(8, 4) == 4) assert (count(7, 4) == 4) assert (count(6, 4) == 3) assert (count(5, 4) == 2) assert (count(4, 4) == 2) assert (count(3, 4) == 2) assert (count(2, 4) == 1) assert (count(1, 4) == 0) assert (count(0, 4) == 0) assert (count(8, 2) == 4) assert (count(4, 2) == 2) assert (count(3, 2) == 2) assert (count(2, 2) == 1) assert (count(1, 2) == 1) assert (count(0, 2) == 0) def solve(A, B): cycle = 2 ans = "" for _ in range(40): acount = count(A - 1, cycle) bcount = count(B, cycle) ans = str((bcount - acount) % 2) + ans cycle *= 2 return int(ans, base=2) assert (slow_solve(2, 4) == solve(2, 4)) assert (slow_solve(2, 5) == solve(2, 5)) assert (slow_solve(2, 6) == solve(2, 6)) assert (slow_solve(2, 7) == solve(2, 7)) assert (solve(1, 1) == 1) assert (solve(2, 4) == 5) assert (solve(123, 456) == 435) if __name__ == "__main__": A, B = tuple(map(int, input().split(" "))) print(solve(A, B))
もっとしっかり考えましょう。そして400問題で精進しよう。 来週はGrandコンテストでレート下降は避けられないので水色はしばらくお預けかな、、、
