目次
AtCoder Beginner Contest 141 D～F問題メモ
D - Powerful Discount Tickets
問題
- $N$ 個の品物を1個ずつ買いたい
- 価格は $A_1,A_2,...,A_N$ 円
- $M$ 枚の割引券があり、品物1つに対し何枚でも使える
- $x$ 円の品物を買う際に割引券を1枚使うと半額（小数点以下切り捨て）、2枚使うとさらにその半額……となる
- 正確には、$y$ 枚の割引券を使うと、$\displaystyle [\frac{x}{2^y}]$ 円で購入できる
- どの商品に何枚割引券を使うかを上手く考え、購入費の合計を最小化せよ
- $1 \le N,M \le 10^5$
- $1 \le A_i \le 10^9$
解法
高い順に割引券を多く使いたい。1枚使ってもまだ他より高ければ2枚、3枚、、、と使えばよいが、ある程度使って他の商品が高くなれば、そちらに使った方がよい。
なので、「今の最高額の商品を、半額で置き換える」ことを $M$ 回繰り返す。
heapqを使うと1回の操作に $O(\log{N})$ かかるので、全体で $O(M \log{N})$ となる。
pop()してpush()してもよいが、replace()を使えば2つの操作を1度に行え、heap構造を保つための比較処理も1回で済むので定数倍高速。
from heapq import heapify, heapreplace
n, m = list(map(int, input().split()))
aaa = [-a for a in map(int, input().split())]
heapify(aaa)
for _ in range(m):
heapreplace(aaa, aaa[0] // 2 + aaa[0] % 2)
print(-sum(aaa))
E - Who Says a Pun?
問題
- 長さ $N$ の文字列 $S$ がある
- $S$ の連続する部分文字列を考える
- 重ならずに2回以上現れる部分文字列で、最長のものの長さを求めよ
- 存在しない場合は0とする
- $2 \le N \le 5000$
例
aabbaabbaa
aabbaa などは、2箇所で取れるが、重なっている
aabbaabbaa
|----|
|----|
重ならずに取れるのは、aabb, abba など、長さ4が最長
aabbaabbaa
|--||--|
解法
同じ文字列が出現するかを探索するので、ローリングハッシュが使えそう。 ただしローリングハッシュは（基本的には）検索文字列長が決まってないといけないので、今回のように最長のものを探索する場合は、二分探索を組み合わせる。
今回の場合、ハッシュの衝突がなかなか厄介で、modを交換しても結構衝突する。$D$ 進数の $D$ の方を変えれば、効率よく衝突を回避できた。
まず、答えとなる長さは長くても $N/2$ なので、二分探索で lo = 0, hi = N/2+1 として、長さ $l$ を決め打ちしてチェックする。
l=4
gamblerumble
---- 先頭からはじめて4文字目の'b'で最初の'gamb'のハッシュ値が計算される
---- ずらして次々計算する
....
---- 先頭から2*4文字目で、最初の'gamb'が被らなくなるので検索対象に入れる
---- 'ambl' を検索対象に入れる
---- 'mble' を検索対象に入れる
....
---- 'mble' が検索対象の中に見つかるので、長さ4はOK
1回のチェックにかかる計算量は、ハッシュ値を計算するのに $O(N)$、検索対象に存在するかを調べるのに、二分探索木などを使って $O(\log{N})$。 文字列長を二分探索で見つけるのに $O(\log{N})$ で、合わせて $O(N \log^2{N})$ で間に合う。
また、他の方の解答を見るに、Pythonではローリングハッシュでなく、ビルトインのhash()関数を使えば、面倒なハッシュ値の計算を実装せずとも衝突しにくいハッシュ値が高速に計算されるようだ。ローリングハッシュは前の計算結果を利用してずらしながら計算を行うから速い……はずなのだが、Pythonでは悲しいかな毎回ゼロから計算することになろうが、組み込み関数を使った方が速くなるようだ。これからは手段の1つに加えよう。
def solve(n, s):
l, r = 0, n // 2 + 1
while l < r:
m = (l + r + 1) // 2
if search(m, s):
l = m
else:
r = m - 1
return l
def search(w, s):
w2 = w * 2
appeared = [hash(s[i - w:i]) for i in range(w, w2)]
comparing = set()
for i in range(w2, n + 1):
t = hash(s[i - w:i])
comparing.add(appeared[i - w2])
if t in comparing:
return True
appeared.append(t)
return False
n = int(input())
s = input()
print(solve(n, s))
F - Xor Sum 3
問題
- $N$ 個の非負整数 $A_1,A_2,...,A_N$ がある
- 整数を2グループに分ける
- グループ分けの美しさを「各グループで、属する数のXORを計算し、その合計」とする
- 美しさの最大値を求めよ
- $2 \le N \le 10^5$
- $0 \le A_i \lt 2^{60}$
解法
XORだし、制約も意味ありげに2進数で書いてあるし、2進数で考える。
上から $d$ 桁目に着目し、$d$ 桁目が'1'の数の個数を数える。
奇数個
どう分けたところで一方が偶数個、一方が奇数個になり、そのXORは'0'と'1'、和は'1'となる。
0個
どう分けたところで'0'。
正の偶数個
ここをどうするかが重要となる。
偶数個+偶数個に分ければともに'0'、奇数個+奇数個に分ければともに'1'となるので、なるべく奇数個同士に分けたい。 だが、他の桁との兼ね合いで、偶数個同士に分けざるを得ない場合もある。
N=3 6 110 5と6を別グループにしようとすると、 5 101 3はどちらのグループに入れても、 3 011 どちらかの桁が0個と2個（偶数個同士）に分かれてしまう
下位の桁がどれほど犠牲に（偶数個にしかできなく）なろうが、上位の桁がひとつ'1'になった方が数字は大きくなるため、上位の桁から貪欲に決めていく。
決め方
まず、どう分けてもいい '1' が奇数個の桁は、全ての数字で '0' にして考慮から除いておく。（最後に足せばよい）
23 0010111 7 0000111
36 0100100 => 4 0000100
66 1000010 66 1000010
65 1000001 65 1000001
~~
残る偶数個の桁については、2グループに分ける時、一方を'1'にするともう一方も'1'、'0'なら'0'で一致するので、各グループでXORを取ると等しくなる。 よって、一方だけに着目して、いくつかの数字を取ってXORを最大化するようにすると、自動的にもう一方も最大化されている。
XOR最大化は、行列の掃き出し法のようなことをすれば求まる。以下の形を目指す。
- 全ての行は、ビットが0個か1個だけ立っている
- 同じビットが立っている行は無い
7 0000111 64 1000000
4 0000100 => 4 0000100
66 1000010 2 0000010
65 1000001 0 0000000
============
70 1000110 が最大
ここの解法の冒頭にある説明が、理屈がわかりやすい。
$\{a_1,a_2,a_3,...\}$ と $\{a_1,(a_1 \oplus a_2),a_3,...\}$ とで、その中からいくつかの数字を取ってXORで作れる数字は変わらない。
ので、2つの数 $a,b$ を選んで、$b$ を $a \oplus b$ で置き換える、という操作を繰り返すと、上記のような形に変形できる。 変形したら、同じビットが立っている桁は無いという前提の元、全ての数のXORを取ることで最大化できる。
以下の手順で行う。
- 上位の桁から確定させていく。着目中のビットを $d$ とする
- $d$ が最上位ビットである数字を1つ選び、$a$ とする
- 他に、$d$ が立っている数字があれば、$a$ とXORを取った数に置き換える
d d d 7 0000111 7 0000111 a 7 0000111 4 0000100 4 0000100 => 4 0000100 => 3 0000011 a => 3 0000011 66 1000010 a 66 1000010 66 1000010 65 1000001 65 1000001 3 0000011 3 0000011 0 0000000
最後がちょっと残ってしまうが、残ってしまうのは「より上位の桁に影響を与えないと、単独では自由に決められないビット」である。 自由に決められるビットは上位桁から全て立てたので、XORを取れば最大値が求まる。
最大値は両グループで同じ値となるので2倍して、最初に除いた'1'が奇数個の桁を加えたものが答えとなる。
実装の上では、暫定の答え用の変数 $ans$ を用意しておいて、
- $ans$ で $a$ の最上位ビットが立ってなければ、$ans ← ans \oplus a$ として更新、立ってたら何もしない
- 元の行列では $a$ は考慮済みとして0にする
とすると、各 $d$ に対する $a$ の発見がmaxで済むのでちょっと楽。
d d d 7 0000111 7 0000111 a 0 0000000 0 0000000 4 0000100 => 4 0000100 => 3 0000011 a => 0 0000000 66 1000010 a 0 0000000 0 0000000 0 0000000 65 1000001 3 0000011 3 0000011 0 0000000 ans 0000000 1000010 1000101 1000110
import numpy as np
n = int(input())
aaa = np.fromiter(map(int, input().split()), np.int64)
all_x = np.bitwise_xor.reduce(aaa)
bbb = aaa & ~all_x
ans = 0
while any(bbb):
a = bbb.max()
b = 1 << (int(a).bit_length() - 1)
bbb[bbb & b > 0] ^= a
if ans & b == 0:
ans ^= a
print(2 * ans + all_x)
