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,\ldots$ と $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,\ldots,q$ について、$a+2a+3a+\ldots+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 \ldots $ と $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)+\ldots+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))

本WebサイトはcookieをPHPのセッション識別および左欄目次の開閉状況記憶のために使用しています。同意できる方のみご覧ください。More information about cookies
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