−目次

AtCoder Beginner Contest 172 D,E,F問題メモ
- D - Sum of Divisors
- E - NEQ
  - 問題
  - 解法
- F - Unfair Nim
  - 問題
  - 解法

AtCoder Beginner Contest 172 D,E,F問題メモ

AtCoder Beginner Contest 172

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に複数の解法が計算量別にまとめられている。

[AtCoder 参加感想] 2020/06/27:ABC 172 | 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))

            

        
      

−目次