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))

programming_algorithm/contest_history/atcoder/2020/0627_abc172.txt · 最終更新: 2020/06/28 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0