AtCoder Regular Contest 102

C - Triangular Relationship

問題

  • 整数 $N,K$ が与えられる
  • $1 \le a,b,c \le N$ なる3つの整数を考える
  • $a+b,b+c,c+a$ のいずれも $K$ の倍数となる $(a,b,c)$ の組の個数を求めよ
    • $a,b,c$ は互いに区別する

解法

  • $a+b=l \times K$
  • $b+c=m \times K$
  • $c+a=n \times K$

とした時、$(a+b)+(b+c)-(c+a)=2b=(l+m-n)\times K$ なので、$2b$ は $K$ の倍数となる。同様のことが $2a,2c$ にも言える。

Kが奇数

$a,b,c$ は全て $K$ の倍数となる。

$N$ 以下の整数で $K$ の倍数が $k$ 個とすると、$a,b,c$ のそれぞれがその中のどれになってもよいので、$k^3$ 通りが答えとなる。

Kが偶数

$a,b,c$ は「全て $K$ の倍数」か「全て $K$ で割ると $K/2$ 余る数」となる。

それぞれの個数が $k,l$ の時、$k^3+l^3$ が答えとなる。

n, k = map(int, input().split())
if k % 2 == 0:
    d1 = n // (k // 2)
    d2 = n // k
    ans = d2 ** 3 + (d1 - d2) ** 3
else:
    d = n // k
    ans = d ** 3
print(ans)

D - All Your Paths are Different Lengths

問題

  • 整数 $L$ が与えられる
  • 頂点数 $N \le 20$、辺数 $M \le 60$ の有向重み付きグラフを作る
    • 頂点には1から $N$ までの番号が付く
    • 辺は必ず小さい番号から大きい番号に張る
    • 多重辺があってもよい
  • 頂点1から $N$ までの経路の数は $L$ 通りになるようにする
  • 各経路の距離は、全て異なり 0~$(L-1)$ の $L$ 通りとなるようにする
  • $1 \le L \le 10^6$

L=5
        ,------0-----,
①--0--②--1--③--0--④--0--⑤
  `-----3-----' `-----1-----'
  • 1-2-4-5: 0
  • 1-2-3-4-5: 1
  • 1-2-3-5: 2
  • 1-3-4-5: 3
  • 1-3-5: 4

5通りの経路があり、各距離が0~4となっている。

解法(1)

たとえば、ある頂点 $v$ までの経路が3通りあり、各経路の距離が $\{2,5,9\}$ だった時、$v$ から重み4の辺を通った先の頂点 $w$ は、$\{6,9,13\}$ となる。さらに多重辺として重み5の辺もあれば、経路は6通りに増え、$\{6,7,9,10,13,14\}$ となる。

{2,5,9}          {6,9,13}
   v ----- 4 ----- w
{2,5,9}          {6,9,13, 7,10,14}
   v ----- 4 ----- w
    `----- 5 -----'

異なる辺を通った時の数値が被らないように各辺の重みを設定する必要がある。すると、飛び飛びよりは、なるべく $v$ に至る経路の距離は連続してる状態を保った方がやりやすそう。

{0,1,2}          {0,1,2, 3,4,5, 6,7,8}
   v ----- 0 ----- w
   |------ 3 ------|
   `------ 6 ------'

$n$ 進数のように考えると、下記のようにすると $n$ の冪乗数通りの経路までは距離が被らずに構築できると分かる。(辺数の制約もあるが)

①--- 0 ----②---- 0 ----③---- 0 -----④- ... (N)
 |--- 1 ---|  |--- n ---|  |--- n^2 --|  |-     -|
 |--- 2 ---|  |---2n ---|  |--2(n^2)--|  |-     -|
 ...     ...  ...     ...  ...      ...  ...   ...
 `-- n-1 --'  `-(n-1)n--'  `(n-1)(n^2)'  `-     -'

経路のパターン数
 1         n          n^2         n^3      n^(N-1)
各経路の距離
(0)     0~n-1     0~n^2-1    0~n^3-1  0~n^(N-1)-1

ここで制約を見ると頂点数20以下なので、$n^{19}$ 通りの経路が構築できる。

試しに $n=2$ とすると、$2^{19}=524288$。$L=10^6$(制約の最大値)の時、$10^6$ を超えない2の冪乗数が19、つまり必要な頂点数20で丁度合致するので、2進数で考えてよさそう。

必要な辺数も38本なので、残りの経路の調整分を追加することを考えても、余裕がある。

これで $L$ を超えない2の冪乗数までは構築できた。残りの経路をどうするか。

途中の頂点 $k$ から(N)に直接辺を張ると、新たに $2^{(k-1)}$ 通りの経路が追加される。

                       ,------------------,
①--- 0 ---②--- 0 ---③--- 0 ---④- ... (N)
 `--- 1 ---'`--- 2 ---'`--- 4 ---'`-     -'

$L$ を2進数で表現し、最上位を除いて下から $d$ 桁目が'1'であれば、頂点 $d$ から(N)に辺を張ればよい。

辺追加前のグラフにおける経路のパターン数が $p$ で、各距離が 0~$(p-1)$ を実現できているとすると、追加する辺の重みを $p$ とすることで、辺追加後は経路のパターン数が $p+2^{(k-1)}$ となる。これを繰り返せばよい。

L=13
13を超えない2の冪乗数が8なので、8通りの経路を持つグラフを構築
  ,--0--,  ,--0--,  ,--0--,
①---1---②---2---③---4---④

L=13 → 2進数で1101 → 最上位を除いた101に着目
下から3桁目が'1' → ③から④に辺を追加する
  ,--0--,  ,--0--,  ,--0--,
①---1---②---2---③---4---④
                    `--8--'
重みは、今の経路数が8で、0~7の距離が埋まっているので、8とする
これにより、経路数は12、0~11の距離が埋まる

下から1桁目が'1' → ①から④に辺を追加する
  ,--0--,  ,--0--,  ,--0--,
①---1---②---2---③---4---④
 |                  `--8--'
 `-----------12-----------'
重みは、今の経路数が12で、0~11の距離が埋まっているので、12とする
これにより、経路数は13、0~12の距離が埋まる

def solve(l):
    buf = []
    lb = len(bin(l)) - 3
    for i in range(lb):
        buf.append((i + 1, i + 2, 0))
        buf.append((i + 1, i + 2, 1 << i))
    ofs = 1 << lb
    for i, c in enumerate(bin(l)[3:]):
        if c == '1':
            buf.append((lb - i, lb + 1, ofs))
            ofs += 1 << (lb - i - 1)
    return lb + 1, buf


l = int(input())
n, buf = solve(l)
print(n, len(buf))
print('\n'.join(' '.join(map(str, e)) for e in buf))

解法(2)

解説放送の方法。

$L=2$ の時、グラフは以下の形で実現できる。

①-- 0 --②
  `- 1 -'

$n=2$ から始めて「$n$ に1を足す」「$n$ に2をかける」のいずれかを繰り返して、$L$ にする最短操作手順を求める。

各操作に対応して、グラフを更新していく。

「$n$ に1を足す」場合、①から(N)(現時点の最大番号の頂点)に、重み $n$ の辺を追加する

①-- 0 --②  →  ①-- 0 --②
  `- 1 -'          |- 1 -|
                   `- 2 -'

「$n$ に2をかける」場合、各辺の重みを2倍し、さらに頂点を追加して重み0,1の2辺を張る

①-- 0 --②  →  ①-- 0 --②-- 0 --③
  `- 1 -'          `- 2 -'  `- 1 -'

$L=13$ での挙動を見て見る。操作手順は2ー(+1)→3ー(x2)→6ー(x2)→12ー(+1)→13である。

L=2
①-- 0 --②
  `- 1 -'
L=3 (+1)
①-- 0 --②
  `- 1 -'
  `- 2 -'
L=6 (x2)
①-- 0 --②-- 0 --③
  `- 2 -'  `- 1 -'
  `- 4 -'
L=12 (x2)
①-- 0 --②-- 0 --③-- 0 --④
  `- 4 -'  `- 2 -'  `- 1 -'
  `- 8 -'
L=13 (+1)
①-- 0 --②-- 0 --③-- 0 --④
  `- 4 -'  `- 2 -'  `- 1 -'
  `- 8 -'                 |
  `----------12-----------'

このように、

  • 自明な $n$ で答えを求める
  • 「$n$ に1を足す」「$n$ に2をかける」の手順を求める
  • 各操作に対応した処理を行う

という発想は解法1より汎用的で、当てはめられる問題がたまにあるらしい。

E - Stop. Otherwise...

問題

  • 整数 $K,N$ が与えられる
  • $K$ 面サイコロを $N$ 個振る
    • $K$ 面サイコロには、1~$K$ の整数が書かれている
    • サイコロは互いに区別しない
  • 各 $i=2,3,\ldots,2K$ に対し、以下の値を $\mod{998244353}$ で求めよ
    • どの異なる2つのサイコロの出目の合計も $i$ にはならない、出目の組の場合の数
  • $1 \le K \le 2000$
  • $2 \le N \le 2000$

$K=6$ 面サイコロを $N=3$ 個振る。
$i=2,3,\ldots,12$ について答えを求める。

たとえば $i=5$ の時、(1,4)または(2,3)の組があってはいけない。
それを含まない (1,3,6) や (2,2,2) のような出目の組はOK。
(1,4,5) や (2,2,3) のような出目の組はNGとなる。

サイコロは互いに区別しないことに注意すると、44組が該当する。

解法

1面サイコロとは一体……

公式解説の解法はこの問題に特化したスマートな方法だが、より汎用的な方法として、包除原理を使って解ける。

各 $i$ ごとに、「合計が $i$ となる組を含む出目の場合の数」を求めて全体 ${}_KH_N$ から引けば、答えである「合計が $i$ となる組を含まない出目の場合の数」が求まる。サイコロは区別しないので全体の場合の数は重複組み合わせで求める。

「合計が $i$ となる組を含む出目の場合の数」を求める際に包除原理を用いる。

包除原理

最近のARCでも何度か出ているが、数え上げ問題で、ダブリを解消するのに有効な手法。

たとえば $i=5$ の時、合計が5となる組は(1,4)と(2,3)のいずれか。($K$ が4以上の場合)

これらが含まれる場合の数を数えるには、「$N$ 個中2個を(1,4)や(2,3)に固定して、残りを自由に決める」という方法を用いるとよい。

$K=4,N=5$ を例に取ると、「2個を(1,4)または(2,3)に固定」で2通り、残りの3個を決めるのに ${}_4H_3=20$ 通り、掛け合わせて40通り…となりそうだが、実際には間違いとなる。

それは、(1,4)も(2,3)も両方含む場合を重複して数えているから。これが4通りあるため、36通りが正しい答えとなる。

(1,4)を含む   (2,3)を含む
     /~~~~~~x~~~~~~\
    /      / \      \
   |   16 | 4 | 16   |
    \      \ /      /
     \______x______/

$i=5$ のように該当する組が2通りの場合は「(1組を固定する場合の合計)-(2組をともに固定する場合)」でよかったが、これが $i=10$ で(1,9),(2,8),(3,7),(4,6),(5,5)の5つとかとなると、3組固定する場合、4組固定する場合…を一体どう考えればいいか?

包除原理によると、以下のように考えてよい。シンプル。

  • (1組を固定)-(2組を固定)+(3組を固定)-(4組を固定)+…
  • $\displaystyle =\sum_{q=1}(-1)^{(q-1)}(q組を固定する場合の数)$

各場合の数

合計がiになるペアの数

並び順は区別しないので、ペアの小さい方を数える。上限は $\frac{i}{2}$(切り捨て)。下限は、$i \ge K+2$ の場合は $i-K$、それ以外は1となる。

このペア数を $p$ とする。

p組の中からq組を固定する場合の数

まず、$q$ ペアの選び方で ${}_pC_q$ 通り。

残りの $N-2q$ 個のサイコロの出目は、${}_KH_{N-2q}$ 通り。

これを掛け合わせたのが「合計が $i$ になるペアが $q$ 組入った出目の場合の数(重複あり)」となる。

なお、ペアの中に(5,5)のように同じ数字のものが存在するかどうかは気にしなくてよい。(4,6)など異なる数字のペアと同様に扱ってよい。ペアを使うと決めた時点で2個固定されるし、使わないと決めたのに自由に決められる残りの方に入っていたとしても、後で除去される。

合計がiになる場合の数

全ての取り得る $q$ について上記の重複含みの場合の数を求め、包除原理に従って $q$ が奇数なら足し、偶数なら引いた合計が、重複無しの「合計が $i$ になるペアを含む場合の数」となる。

これを全体から引いた結果を出力すればよい。

$q$ の範囲は基本的に $1~p$ だが、$N$ が小さい場合はそもそも $p$ 個も作れないので $1~\frac{N}{2}$ となることに注意する。

対称性について

以上を考えると、場合の数に影響するのは $K,N$ の固定値を除けば $p$ のみであり($q$ は $p$ に依存)、$i$ が異なってもそこから算出される $p$ が同じであれば場合の数は等しいと分かる。

一度計算した $p$ については再計算を省くことが出来る。

どのような $i$ に対する $p$ が等しくなるかを考えると、以下のようになる。

K=6のときの2つのサイコロの合計
     1  2  3  4  5  6
  +------------------
 1|  2  3  4  5  6  7
 2|     4  5  6  7  8
 3|        6  7  8  9
 4|           8  9 10
 5|             10 11
 6|                12  (サイコロは区別しないので、入れ替えて被るものは空欄)

合計が同じになる出目は、斜めに現れる(この個数が p)
→2と12, 3と11, 4と10, ...は p が同じになる=答えが同じになる
→計算するのは2~7まででよい
(更に、2と3、4と5...も同じになるので、実質的な計算は1つ飛ばしでよい)

def prepare(k, n, MOD):
    def get_factorials(m):
        f = 1
        factorials = [1]
        for m in range(1, m + 1):
            f *= m
            f %= MOD
            factorials.append(f)
        inv = pow(f, MOD - 2, MOD)
        invs = [1] * (m + 1)
        invs[m] = inv
        for m in range(m, 1, -1):
            inv *= m
            inv %= MOD
            invs[m - 1] = inv

        return factorials, invs

    def solve(p):
        """Number of patterns where no pair of p appears when n dices are rolled"""
        if cache[p] > -1:
            return cache[p]

        ret = 0
        fp = factorials[p]
        for q in range(1, min(p, n // 2) + 1):
            tmp1 = (fp * invs[q] % MOD) * invs[p - q] % MOD
            tmp2 = (factorials[k + n - 2 * q - 1] * invs[n - 2 * q] % MOD) * ik % MOD
            if q % 2 == 1:
                ret += tmp1 * tmp2
            else:
                ret -= tmp1 * tmp2
            ret %= MOD

        cache[p] = ret = (all_patterns - ret) % MOD
        return ret

    factorials, invs = get_factorials(k + n)
    ik = invs[k - 1]
    all_patterns = factorials[k + n - 1] * invs[n] * ik % MOD
    cache = [-1] * (k // 2 + 2)

    return solve


MOD = 998244353
k, n = map(int, input().split())
if k == 1:
    print(0)
else:
    solve = prepare(k, n, MOD)
    ans = [solve(i // 2 - max(0, i - k - 1)) for i in range(2, k + 2)]
    print('\n'.join(map(str, ans)))
    print('\n'.join(map(str, ans[-2::-1])))

programming_algorithm/contest_history/atcoder/2018/0901_arc102.txt · 最終更新: 2018/09/05 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0