目次
AtCoder Beginner Contest 172 D,E,F問題メモ
D - Sum of Divisors
問題
- 正整数 $N$ が与えられる
- $f(x)=x$ の約数の個数、と定義する
- $\displaystyle \sum_{x=1}^{N} x \times f(x)$ を求めよ
- $1 \le N \le 10^7$
- 制限時間: 3sec
解法
公式解説に加え、maspy氏のHPに複数の解法が計算量別にまとめられている。
「$x$ は $a$ を約数に持つ」という関係を2次元表にすると以下のような感じになる
a \ x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 o o o o o o o o o o o o o o o o 2 o o o o o o o o (2個おき) 3 o o o o o (3個おき) 4 o o o o (4個おき) 5 o o o (5個おき) 6 o o ...
個々の 'o' について、その上にある $x$ の値を全て合計したものが、答えとなる。
問題文はこれを縦に見て $x$ の軸を $1～N$ まで合計するように言っているが、視点を変えて $a$ の軸を中心に横に見ても答えは変わらない。
ある数 $a$ の約数は $a,2a,3a,...$ と $N$ を超えるまで $\dfrac{N}{a} = k$（切り捨て）個ある。
この合計は等差数列の和で $a \times \dfrac{k(k+1)}{2}$ となる。
これを $a=1～N$ まで合計すればよい。
def solve(n):
ans = 0
for i in range(1, n + 1):
k = n // i
ans += i * k * (k + 1) // 2
return ans
n = int(input())
ans = solve(n)
print(ans)
$O(\sqrt{N})$ 解法
上記のように「$N$ までに $a$ の倍数は $b$ 個ある」は $b = \dfrac{N}{a}$ で求められる。
しかし、$b$ が小さい場合（1個や2個など）、$b$ が同じになる $a$ は数多く存在する。$b$ が小さい範囲については、それらをまとめて計算してやりたい。
a \ x 1 2 3 4 5 6 7 8 9 10 11 12 1 o o o o o o o o o o o o 約数12個 2 o o o o o o ~~~ 約数6個 ~~~ 3 o o o o ~~~ 約数4個 ~~~ ↑aを中心に計算 4 o o o ~~~ 約数3個 ~~~ ~~~~~~~~~~~~~ 5 o o ~~~~~~~~~~~~~~~ ↓bを中心に計算 6 o o 約数2個 7 o ~~~~~~~~~~~~~~~ 8 o 以下約数1個 ...
「$N$ までに倍数が $b$ 個ある最大の $a$」は、$a = \dfrac{N}{b}$ で求められる。
要は $a \times b \le N$ なので、$\sqrt{N}$ 付近で $a,b$ の大小が切り替わる。
$a \lt b$ の範囲は $a$ を中心に計算し、$a \gt b$ の範囲は $b$ を中心に計算すると、探索範囲の上限は $\sqrt{N}$ となる。
注意すべきは $a=b$ となるような場合で、重複して数えないようにする。
$N$ までに倍数が $b$ 個ある最大の数を $q = \dfrac{N}{b}$、$b+1$ 個（以上）ある最大の数を $p=\dfrac{N}{b+1}$ とすると、 $a=p+1,p+2,...,q$ について、$a+2a+3a+...+ba$ を求める計算になる。
これは、2つの等差数列の和のかけ算で、$\dfrac{(p+1+q)(q-p)}{2} \dfrac{b(b+1)}{2}$ で求められる。
n = int(input())
ans = 0
for i in range(1, int(n ** 0.5) + 1):
k = n // i
ans += i * k * (k + 1) // 2
if i != k:
l = n // (i + 1)
ans += i * (i + 1) * (k + l + 1) * (k - l) // 4
print(ans)
E - NEQ
問題
- 以下の条件を満たす長さ $N$ の2つの数列 $A,B$ の組が何通りあるか $\mod{10^9+7}$ で求めよ
- 条件
- 全要素は $1$ 以上 $M$ 以下の整数
- $A$ の要素は全て異なる
- $B$ の要素は全て異なる
- 全ての $i$ について、$A_i \neq B_i$
- $1 \le N \le M \le 5 \times 10^5$
解法
包除原理。
$A_i \neq B_i$ という条件がなければ、1つの数列の作り方は $M \times (M-1) \times ... $ と $N$ 個かけた数なので、${}_MP_N$、それが2つで2乗。
この中から、条件を満たさないものを消していく。
必ず $A_i=B_i$ となっている $i$ の個数を $k$ 個と固定し、残りはどっちでもよいとすると、
- $N$ 個中どの要素が同じか ${}_NC_{k}$
- 同じ要素の具体的な値の決め方 ${}_MP_k$
- 残りの具体的な値の決め方 ${}_{M-k}P_{N-k}^2$
これをあわせて、$\dfrac{N!M!(M-k)!}{k!(N-k)!(M-N)!^2}$ となる。これを $f(k)$ と表す。
包除原理を利用すると、$f(0)-f(1)+f(2)+...+f(N)$ が答えとなる。
def prepare(n, MOD):
f = 1
factorials = [1]
for m in range(1, n + 1):
f *= m
f %= MOD
factorials.append(f)
inv = pow(f, MOD - 2, MOD)
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
return factorials, invs
n, m = map(int, input().split())
MOD = 10 ** 9 + 7
facts, finvs = prepare(m, MOD)
c = 1
ans = 0
base = facts[n] * facts[m] * finvs[m - n] * finvs[m - n] % MOD
for k in range(n + 1):
tmp = base * facts[m - k] * finvs[k] * finvs[n - k] % MOD
ans = (ans + c * tmp) % MOD
c *= -1
print(ans)
F - Unfair Nim
問題
- 2人で ニム を行う
- 石山は $N$ 個、山 $i$ の初期の石の個数は $A_i$
- ゲームを始める前に、1度だけ山1から山2に石を移して、後手必勝にしたい
- 移せる個数は $0$ 個以上 $A_1$ 個未満（山1を0個にしてはいけない）
- 可能か判定し、可能ならその最小個数を求めよ
- $2 \le N \le 300$
- $1 \le A_i \le 10^{12}$
解法
まずニムの必勝法を知っている前提となる。全ての山のXORの値が0なら後手必勝、違うなら先手必勝。
なので、$A_3～A_N$ のXORはまず計算してやる（$X$ とする）。操作後の山1、山2の個数を $p,q$ として、$p \oplus q \oplus X = 0$ ならよい。
これを含め、問題設定を考えると、以下の条件に言い換えられる。$A_1+A_2=S$ とする。
- $p \oplus q = X$
- $p+q=S$
- $0 \lt p \le A_1$
- $p$ は上記の条件を満たす中での最大値
- $A_1-p$ を求めよ
2進数で考えて、$p,q$ を0で初期化して上から貪欲に決めていく。（厳密には貪欲には決められないケースが1つあるけど、それは後述）
上から $d$ 桁目が表す数を $b$ とする。
$X$ の $d$ 桁目が'1'のとき
$p,q$ の $d$ 桁目は、どちらかが'1'、どちらかが'0'。
ここで、$S \lt p+q+b$ の場合、どちらかに'1'を立てたら $S$ をオーバーしてしまうので、不可能。
もし $p$ に $b$ を加えても $A_1$ をオーバーしないのであれば、最大化したいので $p$ の方に足す。
オーバーしてしまうなら、$q$ の方に足す。
$X$ の $d$ 桁目が'0'のとき
$p,q$ の $d$ 桁目は、どっちも'1'か、どっちも'0'か。
ここで、$S$ の値により、どちらを取るかがわかる。
- $S \lt p+q+2b$ の場合
- 両方'1'を立てたら $S$ をオーバーしてしまうので、どっちも'0'確定
- $S \ge p+q+2b$ の場合
- もし両方'0'なら、それ以下の $p,q$ の桁をすべて'1'にしても $S$ に足りなくなってしまうので、どっちも'1'確定
ただし、どっちも'1'の場合に問題が起こる。ひょっとしたら、$p$ に'1'を立てたら $A_1$ をオーバーしてしまうかも知れない。
d 123456 ------------ A1 010010 A2 100100 X 110000 ------------ p 01001_ (S 残り 2) q 10001_
6桁目、両方1を立てなければならないが、立てたら $A_1$ をオーバーする。
ここで、「それより上の桁に、$p$ が'1'、$q$ が'0'の桁があったか？」がポイントとなる。 あったら、そのうち最も低い桁の '1' を $q$ に移すことで、$p+q$ を変えずに $p$ は減り、6桁目に'1'を立ててもオーバーしなくなる。
p 000011
q 110011
~
そういう桁が無かったら不可能。（というのが未証明）
「$X$ の $d$ 桁目が'1'のとき、最後に $p$ の方に'1'を立てた桁」を記録しておけばよい。
本番では貪欲で実装後、1ケースだけWAになり、そのケースを見つけるのができなかった。 未証明貪欲は危ないので、最初からきちんとDPで考えないとね。 （今回、貪欲解が少しだけの補正で済んだのはたまたまな気がする）
偽貪欲という結構根本的な間違いでも、WAとなるのは1ケースだけだったのが何ともデバッグの方向性を狂わせた。
import sys
def solve(n, aaa):
if n == 2:
h, m = divmod(sum(aaa), 2)
if m == 1 or h > aaa[0]:
return -1
return aaa[0] - h
x = 0
for a in aaa[2:]:
x ^= a
a0, a1 = aaa[:2]
s = a0 + a1
if s & 1 != x & 1:
return -1
p, q = 0, 0
b = 1 << 40
last_b = -1
while b:
bx = x & b
if bx == 0:
if s >= 2 * b:
if p | b <= a0:
p |= b
q |= b
s -= 2 * b
elif last_b > 0:
p ^= last_b
q ^= last_b
p |= b
q |= b
s -= 2 * b
else:
return -1
else:
if s < b:
return -1
if p | b <= a0 and q | b > a1:
p |= b
last_b = b
else:
q |= b
s -= b
b >>= 1
if p == 0:
return -1
assert s == 0
assert p ^ q == x
assert a0 - p == q - a1
return a0 - p
n, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, aaa))
上記をメモ化DFSにしたもの。あまり変わっていないが、こちらなら貪欲で破綻したとき、戻って違う方を試す、というのが明確になる。
import sys
from functools import lru_cache
def solve(n, aaa):
if n == 2:
h, m = divmod(sum(aaa), 2)
if m == 1 or h > aaa[0]:
return -1
return aaa[0] - h
x = 0
for a in aaa[2:]:
x ^= a
a0, a1 = aaa[:2]
s = a0 + a1
if s & 1 != x & 1:
return -1
b = 1 << 40
MASK = (b << 1) - 1
@lru_cache(maxsize=None)
def dfs(p, b):
if b == 0:
return p
q = p ^ x & (MASK ^ ((b << 1) - 1))
if x & b == 0:
if s >= p + q + 2 * b:
if p | b <= a0:
return dfs(p | b, b >> 1)
else:
return -1
return dfs(p, b >> 1)
else:
if s < p + q + b:
return -1
if p | b <= a0:
ret = dfs(p | b, b >> 1)
if ret != -1:
return ret
return dfs(p, b >> 1)
ret = dfs(0, b)
if ret <= 0:
return -1
return a0 - ret
n, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, aaa))
