AtCoder Regular Contest 143 の C 問題の解説の行間を埋める

話題とする問題はこちら。 atcoder.jp

ゲームってことは xor？と思いきや、不偏ゲームは両プレイヤーの操作が同じ場合の話なので、今回のようなケースだと解けません。
もしかしたら適切にアドホックな改修を加えれば解けるのかもしれませんが。

カテゴリ的には「二人零和有限確定完全情報ゲーム」らしく、(手番プレイヤー, 状態)を節、遷移を辺として、グラフを構築し、トポロジカルソートして終了手番の方から埋めていけば勝敗を判定することができます。

計算量としては、今回の問題ですと $O(\max(A_{i})^{N})$ です。
制約は $1 \leq A_{i} \leq 10^{9}, 1 \leq N \leq 2 \times 10^{5}$ なので、さすがに2秒は間に合いません。

解説を見た感じ、

必敗盤面となる特定の盤面を列挙する。
- ここで列挙される必敗盤面は、 $X$ と $Y$ の大小に依存しない。
先手手番で、後手に ↑ の必敗盤面を押し付けることのできる盤面を列挙する。これは、必勝盤面となる。
- 条件として $X \leq Y$ が要求される。
- この時点で、 $X \leq Y$ における初期盤面を必勝盤面と必敗盤面に分類できたことになる。
のときに、適切な操作をすれば相手に必敗盤面を押し付けられる盤面を必勝盤面、どのような操作をしても相手に必勝盤面が渡ってしまう盤面を必敗盤面とする。
- 相手に渡した盤面が必勝盤面か、必敗盤面かは $X \leq Y$ における初期盤面が分類済みなので即座に判定可能。

１つ目、２つ目は結構ひらめき勝負かなという印象ですが、３つ目は知識として持っておいてよいかと思いました。特に太字にしたところ。

二項関係 $R$ において、 $\ _xR_y \lor \ _yR_x$ が成り立つとき、 $R$ は完全である、というそうです。今回の問題にもあるように $\mathbb{N}$ 上の $\leq$ は完全です。

先の解説の３つ目の手順と同様に $\ _xR_y$ 下での任意の初期盤面を必勝盤面と必敗盤面に判定できる場合、（ $\ _xR_y$ の真偽によらず）任意の初期盤面を必勝盤面と必敗盤面に判定することが可能です。

非不偏ゲームで、各プレイヤーの戦略集合に完全な二項関係を定義できる場合、この事実は便利...かも？

2022-06-28

AtCoder Regular Contest 143 の B 問題で出会った面白い等式

競技プログラミング（AtCoder Regular Contest）

問題はこちら。 atcoder.jp

概要としてはこんな感じ。

$1$ 以上 $N^{2}$ 以下の自然数を、 $N \times N$ のマス目に1つずつ書く。
$i$ 行 $j$ 列の値を $a_{i,j}$ と表すとき、すべての $a_{i, j}$ が以下を満たすような書き込み方が何通りあるか答えよ。

$\exists j' \in \{1, 2, \dots, N \}, a_{i, j'} \gt a_{i, j}$ または $\exists i' \in \{1, 2, \dots, N \}, a_{i', j} \lt a_{i, j}$

制約は $1 \leq N \leq 500$ です。
大きい数になるので、 $998244353$ で割ったものを出力してください。

本問題の解答については公式解説にゆずるとして、
この問題では、部分問題として、逆に条件を満たさないような $a_{i, j}$ が１つ存在する場合の、 $i$ 行と $j$ 列に書き込む数の組み合わせを求める問題を解くことになります。

解説では以下の式で計算しています。
$\ _{n^{2}}C_{2n-1} \times (n-1)! \times (n-1)!$

お気持ちとしてはこんな感じ。

とりあえず、 $1$ 以上 $N^{2}$ 以下の自然数を $2n-1$ 個集めてきて
下位 $n-1$ 個、真ん中 $1$ 個、上位 $n-1$ 個の３グループにわけ、
真ん中を $a_{i, j}$ とし、上位を $i$ 行、下位を $j$ 列に書き込む。

一方、私がコンテスト中に立てた式はこんな感じ。
$\displaystyle{\sum_{k=n}^{n^{2}-n+1} \ _{k-1}P_{n-1} \times \ _{n^{2} - k}P_{n-1}}$

お気持ちとしてはこう。

とりあえず $a_{i, j} = k$ とおく。
$a_{i, j}$ 未満の数字は、 $k-1$ 個あるので $j$ 列をそれで埋める。
同様に $a_{i, j}$ より大きい数字は、 $n^{2} - k$ 個あるので $i$ 行をそれで埋める。
$k$ を $n$ から $n^{2} - n + 1$ まで動かす。※ $\ _{n}P_{k}$ で $n \geq k$ を満たすため

計算量のオーダーは変わりませんが、定数項は解説の解き方の方が有利です。

当記事の趣旨としては、
$\ _{n^{2}}C_{2n-1} \times (n-1)! \times (n-1)! = \displaystyle{\sum_{k=n}^{n^{2}-n+1} \ _{k-1}P_{n-1} \times \ _{n^{2} - k}P_{n-1}}$
が成り立つことの証明です。

とりあえず、辺々 $(n-1)! \times (n-1)!$ で割っておきます。
$\ _{n^{2}}C_{2n-1} = \displaystyle{\sum_{k=n}^{n^{2}-n+1} \ _{k-1}C_{n-1} \times \ _{n^{2} - k}C_{n-1}}$
以下、これを示します。

$\ _{n}C_{m}$ については以下の有名な式が成り立ちます。
$\ _{n}C_{m} = \ _{n-1}C_{m-1} + \ _{n-1}C_{m} \quad (n, m \geq 1)$
証明としてはこんな感じ。
$\ _{n}C_{m} = \ _{n-1}C_{m-1} + \ _{n-1}C_{m}$
$\quad = \frac{(n-1)!}{(n-m)!(m-1)!} + \frac{(n-1)!}{(n-m-1)!(m)!}$
$\quad = \frac{1}{n-m} \times \frac{(n-1)!}{(n-m-1)!(m-1)!} + \frac{1}{m} \times \frac{(n-1)!}{(n-m-1)!(m-1)!}$
$\quad = \frac{1}{n-m} \times \frac{(n-1)!}{(n-m-1)!(m-1)!} + \frac{1}{m} \times \frac{(n-1)!}{(n-m-1)!(m-1)!}$
$\quad = \frac{n}{(n-m) \times m} \times \frac{(n-1)!}{(n-m-1)!(m-1)!}$
$\quad = \frac{n!}{(n-m)!(m)!}$

さらに、ここから以下が成り立ちます。
$\ _{n}C_{m} = \ _{n-1}C_{m-1} + \ _{n-2}C_{m-1} + \dots + \ _{m-1}C_{m-1}$
ただし $n \lt m$ のとき $\ _{n}C_{m} = 0$ としています。

ここで、
$\ _{n}C_{m} = \displaystyle{\sum_{j=0}^{n-m} x_{i, j} \times \ _{n-i-j}C_{m-i}}$
を満たす $x_{i, j}$ を考えます。 $1 \leq i \leq m, 0 \leq j \leq n-m$ です。
また、実際にこれを満たすような $x_{i, j}$ が存在することは、先の等式から帰納的に証明されます。

$\ _{n}C_{m}$ に関する等式から、 $x_{i, j}$ には以下の漸化式が成り立ちます。 $x_{i+1, j} = x_{i, j} + x_{i, j-1} + \dots + x_{i, 0} = x_{i, j} + x_{i+1, j-1}$
文字を置き換えて
$x_{i, j} = x_{i-1, j} + x_{i, j-1}$
すこし乱暴ですが、この漸化式と $x_{1, 0} = x_{1, 1} = \dots = x_{1, n-m} = 1$ より
$x_{i, j} = \ _{i+j-1}C_{j} = \ _{i+j-1}C_{i-1}$
が成り立ちます。

よって、
$\ _{n}C_{m} = \displaystyle{\sum_{j=0}^{n-m} \ _{i+j-1}C_{i-1} \times \ _{n-i-j}C_{m-i}}$
となります。

この等式の、

$n$ を $n^{2}$ に
$m$ を $2n-1$ に
$i$ を $n$ に
$j$ を $k - n$ に

置き換えると $\ _{n^{2}}C_{2n-1} = \displaystyle{\sum_{k=n}^{n^{2}-n+1} \ _{k-1}C_{n-1} \times \ _{n^{2} - k}C_{n-1}}$ を得ることができました。

2022-05-28

最小全域木：Prim Jarnik 法

競プロのアルゴリズムまとめ

今回は競技プログラミングに関する記事です。
以前 Prim Jarnik 法に関する記事を公開したのですが、間違えた内容であることが分かったので内容を修正した記事となります。その節はご迷惑をおかけしました。

もうひとつの最小全域木生成アルゴリズムである Kruskal 法の記事はこちら。 katoufujibanana.hatenadiary.jp

表題の Prim Jarnik 法に入ります。計算量は $O(E\ log(V))$ です。
スクリプト的には計算量 $O(E\ log(E))$ なような気もするのですが、 $O(log(V)) = O(log(E))$ みたいなところあるのでたぶん同じです。本当かな？

Prim Jarnik 法では、以下の手順をくりかえして全域木を構成します。

好きなノード１つを選ぶ。このノードは手順開始時に到達済ノードとする。
選んだノードから伸びている辺すべてを heapq に追加する。（優先順位は、辺のコスト）
heapq から辺を pop する。
pop した辺から未到達のノードに到達できる場合、その辺を全域木を構成する辺に追加する。
さらに、先ほど未到達だったノードを到達済ノードに変更し、そのノードから伸びている辺すべてを heapq に追加する。
3～6 を繰り返す。

この手順で構成された全域木は最小全域木となります。不思議。

手順の 2 の heapq の優先順位を「その辺を選んだ場合の、原点ノードから辺の終端ノードへの最短距離」とするとダイクストラ法になります。原点ノードってなんだ。

スクリプトは以下になります。

import heapq

def prim_jarnik(self, graph):
    n = len(graph)
    min_edges = []
    connected = [False for _ in range(n)]
    connected[0] = True
    connected_num = 1
    q = []
    for i in range(n):
        for cost, i in graph[0]:
            heapq.push(q, [cost, 0, i])

    while connected_num < n:
        c, f, t = heapq.pop(q)
        if connected[f] and not connected[t]:
            connected[t] = True
            connected_num += 1
            min_edges.push([c, f, t])
            for cost, i in graph[t]:
                if not connected[i]:
                    heapq.push(q, [cost, t, i])

    return min_edges

引数に渡す graph は、隣接リスト表現のグラフを渡してあげてください。

2022-05-08

AtCoder Grand Contest 057 の B 問題の考察

競技プログラミング（AtCoder Grand Contest）

AGC057 に Unrated 参加してきました。AB 2完（1 WA）で順位は195位とのこと。

B 問題を解いているうちに「あれ、計算量どうやって減らすんだ...？」と十数分悩んだのち、解けたときすごい感動しちゃったので記事残しておきます。
~~解説ではしれっと２行くらいで流されている内容なんですけどね。~~

B 問題のリンクと atcoder.jp

B 問題の解説へのリンクです。 atcoder.jp

解説にもある以下の部分問題に関する記事です。

$a$ 以下の整数列 $(L_{1}, L_{2}, \dots , L_{N})$ および、 $a$ 以上の整数列 $(R_{1}, R_{2}, \dots , R_{N})$ が与えられる。各 $i = 1, 2, \dots, n$ に対し、 $A_{i} = L_{i}$ または $A_{i} = R_{i}$ が成り立つように整数列 $A = (A_{1}, A_{2}, \dots , A_{N})$ を構成する。
このとき $max(A) - min(A)$ がとりうる値の最小値を求めよ。

なにも考えないと $L_{i}$ か $R_{i}$ どちらを採用するかで、計算量 $O(2^{N})$ でこの部分問題が解けることがわかります。 $N \leq 10^{5}$ なので、まあ間に合わないです。

これがなんと計算量 $O(N)$ まで落とせるという。
※ 厳密には、前処理に $O(N log(N))$ かかるので、そちらが律速になります。

これを導出するために、以下の考察を行います。

は、以下のどちらかを満たす。
- $min(A) = L_{i}$ を満たす $i$ が存在する。
- $min(A) = min(R_{1}, R_{2}, \dots, R_{N})$
を満たすが存在する場合、以下が成り立つ。
- について、であるならば、である。
  - を満たすが存在する場合、さらに以下が成り立つ。
    - $max(A) \geq max(\lbrace R_{j} | L_{j} \lt L_{i} \rbrace)$ 　※ 当記事ではここを後で深堀りします
    - 等号成立条件は、 $j = 1, 2, \dots, n$ について、 $L_{j} \lt L_{i} \Leftrightarrow A_{j} = R_{j}$ のとき。
  - を満たすが存在しない場合、さらに以下が成り立つ。
    - $max(A) = max(L_{1}, L_{2}, \dots, L_{N})$ 　
    - また、 $min$ の定義より、 $L_{i} = min(L_{1}, L_{2}, \dots, L_{N})$
が成り立つ場合、以下が成り立つ。
- $max(A) = max(R_{1}, R_{2}, \dots, R_{N})$

この考察から、 $max(A) - min(A)$ の値は以下の３パターンのいずれかになります。

$max(L_{1}, L_{2}, \dots, L_{N}) - min(L_{1}, L_{2}, \dots, L_{N})$
$max(\lbrace R_{j} | L_{j} \lt L_{i} \rbrace) - L_{i}$
$max(R_{1}, R_{2}, \dots, R_{N}) - min(R_{1}, R_{2}, \dots, R_{N})$

事前に $(L_{1}, L_{2}, \dots, L_{N})$ が昇順になるように、 $(L_{1}, L_{2}, \dots, L_{N})$ と $(R_{1}, R_{2}, \dots, R_{N})$ をソートしておけば、 $max(\lbrace R_{j} | L_{j} \lt L_{i} \rbrace) = max(R_{1}, R_{2}, \dots, R_{i-1})$ となり、累積 max を取ることで高速に取得することができます。

前処理のソートの計算量が $O(N log(N))$ 、累積 max を取っていくところの計算量は $O(N)$ となります。

Python で書くとこんな感じ。

l = [l1, l2, ..., ln]
r = [r1, r2, ..., rn]
# l を昇順にソートする。r は l のソートにあわせて並び替える。
l, r = list(zip(*sorted(list((li, ri) for li, ri in zip(l, r)))))

ans = float("inf")

# 全部 l[i] を採用する場合
upper = max(l)
lower = min(l)
ans = min(ans, upper - lower)

# r[1], r[2], ..., r[i], l[i+1], l[i+2], ...., l[n] を採用する場合
for i in range(n-1):
  upper = max(upper, ri)
  lower = l[i+1]
  ans = min(ans, upper - lower)

# 全部 r[i] を採用する場合
upper = max(r)
lower = min(r)
ans = min(ans, upper - lower)

print(ans)

さて、考察にあった $max(A) \geq max(\lbrace R_{j} | L_{j} \lt L_{i} \rbrace)$ の深堀りの時間です。
この不等式にたどり着くために、まず以下の事実を挙げておきます。

関数 $max \colon 2^{\mathbb{R}} \rightarrow \mathbb{R}$ について、以下が成り立つ。
$P \subseteq Q \in 2^{\mathbb{R}}$ となる $P, Q$ について、 $max(P) \leq max(Q)$

また、同様に
関数 $min \colon 2^{\mathbb{R}} \rightarrow \mathbb{R}$ について、以下が成り立つ。
$P \subseteq Q \in 2^{\mathbb{R}}$ となる $P, Q$ について、 $min (P) \geq min (Q)$

このことから、考察の $max(A) \geq max(\lbrace R_{j} | L_{j} \lt L_{i} \rbrace)$ が
$L_{j} \lt L_{i} \Rightarrow A_{j} = R_{j}$ より $A \supseteq \lbrace R_{j} | L_{j} \lt L_{i} \rbrace$ であることから導出できます。
※ しれっと $A$ を集合にしているのにはご容赦。

この性質によって、max や min の上界・下界を求めることができました。

他の関数や、集合でも似た議論ができます。先ほどの max や min の性質を少し抽象化して、以下のような性質を考えてみます。

集合 $S$ と順序構造 $(P, \preceq )$ が存在し、ある関数 $f \colon 2^{S} \rightarrow P$ について、以下が成り立つ。
$A \subseteq B \in 2^{S}$ となる $A, B$ について、 $f(A) \preceq f(B)$

順序構造にもいろいろ強さがありますが、 $A \subseteq B \in 2^{S}$ であるときに $f(A)$ と $f(B)$ の順序関係が保証されるような $\prec$ であれば、どんな $\prec$ でもよいかと思います。

具体例としては、こんな感じですかね。

例１
- 集合 $S$ は何でも OK
- 順序構造は $(\mathbb{N}, \leq)$
- 関数 $f$ は、集合の要素数を返す関数
例２
- 集合 $S$ は有向木上のノード
- 順序構造はで、ノード間に親子関係が成り立つとき、子ノード親ノード。
  - ２ノード間に親子関係がないこともあるので、これは半順序構造です。
- 関数 $f$ は、最近共通祖先を返す関数

他にも、意外な例があるかもしれないです。誰か閃いた方教えてください。

この性質を使うことで、 $f$ の値域の上界・下界を賢くもとめることができました。
既に名前がついている性質だったり？　ご存じの方はコメントか、Twitter の方にでも投げていただけると嬉しいです。

（2022年6月28日追記）
単調性でよさそうでした。

2022-04-24

Tips：群とか環とか体とか

競プロのTipsまとめ

とあるご縁で掛け算とか足し算のあたりの話を読む機会があり「そういえば定義なんだっけ...？」となり見返したものを整理した記事です。
しかし出来上がったのは、掛け算や足し算を定義する一歩手前の記事になってしまいました。なぜでしょう。

競プロでも、モノイドや剰余環は頻出なので、競プロ Tips ということに。~~遅延セグ木に登場する作用素のあたりをカバーしきれていないのはご愛敬。~~
=> 遅延セグ木に関しての記事はこちら（コードのみ）

	演算の数	ひとつ目の二項演算				ふたつ目の二項演算				分配法則
	演算の数	結合則	単位元の存在	逆元の存在	交換法則	結合則	単位元の存在	零元以外に対する逆元の存在	交換法則	分配法則
マグマ	1個	ー	ー	ー	ー
半群	1個	〇	ー	ー	ー
モノイド	1個	〇	〇	ー	ー
可換モノイド	1個	〇	〇	ー	〇
群	1個	〇	〇	〇	ー
アーベル群（可換群）	1個	〇	〇	〇	〇
半環	２個	〇	〇	ー	〇	〇	〇	ー	ー	〇
環	２個	〇	〇	〇	〇	〇	〇	ー	ー	〇
可換環	２個	〇	〇	〇	〇	〇	〇	ー	〇	〇
斜体	２個	〇	〇	〇	〇	〇	〇	〇	ー	〇
可換体（体）	２個	〇	〇	〇	〇	〇	〇	〇	〇	〇

こうして整理してみますと、半群と群の関係と、半環と環の関係って微妙に対応していなさそうですね。可換XXX系は、ある程度法則が成り立っているように見えます。

表中に表現できていないこととして、

すべての二項演算は、代数的構造に紐づけられた集合の中に閉じています。
分配法則は以下を指します。
- ひとつ目の演算を $f$ , ふたつ目の演算を $g$ としたとき、 $g(a, f(b, c)) = f(g(a, b), g(a, c))$ および $g(f(b, c), a) = f(g(b, a), g(c, a))$ が成り立つこと。

あとは、分配法則が成り立つことから、ふたつ目の演算に関する零元が存在することと、それがひとつ目の演算に関する単位元と等しいことが示せます。

2022-03-20

組み合わせ：Lucas の定理

競プロのアルゴリズムまとめ

競プロのアルゴリズムです。

契機としてはこちら。 atcoder.jp

定理本体の説明や、数学的証明はこちら参照。
manabitimes.jp algo-logic.info

ざっくりいうと、 $_{n}C_{k} (mod\ p)$ を前計算 $O(p^{2})$ 、クエリ $O(log_{p}(n))$ で計算することができるアルゴリズムです。ただし $p$ は素数。

素朴に実装すると、 $O(min(n, n-m) \times log(p))$ 程度はかかってしまうので $p$ が小さい場合は極めて高速に計算することができます。

$_{10^{100}}C_{10^{99}} (mod\ 7)$ とかであれば実用的な速度で計算可能です。 $p = 10^{9} + 7$ といった、大きめの素数の場合は使えないのでその点はご容赦を。

python スクリプトとしてはこんな感じで。
前処理で逆元を求める必要もないので、その点でも有利ですね。

class LucasTheorem:

    def __init__(self, p): 
        self.p = p
        self.dp = [[0 for j in range(p+1)] for i in range(p+1)]
        # nCk = dp[k][n] なことに注意
        for i in range(p+1): 
            self.dp[0][i] = 1

        for i in range(p):
            for j in range(p):
                self.dp[i+1][j+1] = (self.dp[i][j] + self.dp[i+1][j]) % p

    def get_nCk(self, n, k):
        ans = 1
        while n > 0 or k > 0:
            ans *= self.dp[k % self.p][n % self.p]
            ans %= self.p
            n //= self.p
            k //= self.p
        return ans

使い方はこんな感じ。 $_{10^{100}}C_{10^{99}} (mod\ 7)$ を求めてみます。

lt = LucasTheorem(7)
lt.get_nCk(10 ** 100, 10 ** 99)

2022-02-27

お勉強：マクロ経済の入門本読んで思ったこと

与太話

掲題の通り。
ここ気になるな―という点のメモです。
正しい用語回しできていなかったら恐縮です。フィーリングで読んでくれ。

家計消費の効用関数

消費額 $C$ に対する効用 $U(C)$ について、 $\frac{\delta U}{\delta C} \gt 0,\ \frac{\delta^{2} U}{\delta C^{2}} \lt 0$ を置くの、結構強い仮定を置いているような気がする。
それどころか具体的な式の形（例： $U(C) = ln(C)$ ）を与えるのは、めちゃくちゃ強い仮定です。

$U(C)$ は広義単調増加、という仮定のみならまあ自然かなとも思いました。
個人的には財の購入に関する仮定

家計は自身が購入可能なすべての財の価格がわかっており
ある購入計画は一定以上の消費を行えば実現可能である条件下で、
家計は最適な財の購入計画を立てる

を置いて、 $U(C)$ が広義単調増加であることを導出するのが一番きれいかと思いますが、まあそこは人の好みということで。

２期間消費モデル

変数が、

現時点の可処分所得
将来所得
運用利回り

だけなんだけれども、

財価格上昇（に伴う効用関数の変化）を表すインフレ率

も加えてほしいなと思ったり。それぞれ独立に動かしたときの、貯蓄額（個人的には第一期の消費額が本当は欲しいパラメータ）の分析をしたいなと。

効用関数もあまり制約を置かずに分析して、汎的に成り立つことを何か言えないかなーと。

GDP の増加と家計の効用増加は同値か？

これ自体はご存じの方も多いですが偽です。
GDP に投資額と政府支出と輸出額が含まれるので。

ちなみに、家計の総消費額の増加と、家計の効用増加が同値かというと、

すべての家計の効用が増加する、は偽
少なくとも一つの家計の効用が増加する、は真

ですね。パレート改善が保証されなくて悲しいねぇ。

金利コントロールはインフレを制御できるか？

ご存じの通り、弊国では日本銀行が介入することで日本国債の利回りをいじることができますが

国債利回りを上げると、インフレが止まる
国債利回りを下げると、インフレが起きる

らしいです。
金融政策は景気や物価にどのように影響を及ぼすのですか？ : 日本銀行 Bank of Japan

あと、通貨流通量も制御可能ですがいったんそれはおいておいて。

国債利回りを下げた場合は、以下は言ってよさそうです。

市中金利の低下
銀行から企業への総融資額の増加
企業の設備投資額の増加

ただし、以下のステップがおそらく非自明です。

設備投資増加に伴う企業収益性の改善
企業収益性改善に伴う、家計の収入額の増加
家計の収入額の増加に伴う、物価の上昇

ちなみに利回りを上げた場合は上記の増える減るが逆になる感じなのですが、それだと非自明な箇所が利回り低下時と比べて現実化しやすい印象があります。

なんでだろうね。なんででしょうね。