| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
40 分 6 ペナ → 148位。答が合わず提出デバッグしていましたｗ
kenkoooo さんの企画？ABC トーナメントは、参加していない認識だった（自分で参加登録する形だと思っていた）のですが、参加者だったようです。惨敗、かなしー。
問題 E まで 5 問合わせて 6:20 は、私としては速い方です。Aに行く前に、1分ほど問題Fを読んでいると思います。
問題 F も、判定方法までは 1 分とかからず分かったのですが。
構築アルゴリズムで結構詰まりました。できそうな方針の概略はすぐに分かったのですが、どう実装しようかなーと悩み。あまり上手な方法が思い浮かばず、雑な方法で書きながら修正しく方針で進めたところ、バグらせてしまいました。（ソートするの実装した覚えがあるのにいつ消したっけ…ひどい）
問題C – Ubiquity
包除原理の基本という感じです。
dp による方法もあります。N 項の数列を、各時点で 0, 9 が現れたかの 4 種に分類して個数を計算すればよいです。
この漸化式を解くことでも、答の式 $10^n – 2\cdot 9^n + 8^n$ は得られますし、漸化式さえ立てられていれば、明示公式が作れなくても、多項式や行列により $O(\log n)$ 時間での計算は可能です。
問題D – Redistribution
形式的べき級数を用いた考察を紹介します。
$n$ 項の $3$ 以上の整数からなる数列のうち、総和が $S$ であるものの個数は、$$f = x^3 + x^4 + x^5 + \cdots$$ とすると $[x^S]f^n$ と表すことができます。項数を動かすことで、この問題の答は $[x^S]\sum_{n=0}^{\infty} f^n$ と表せます。
$f$ の定数項は $0$ なので、この式は $[x^S]\frac{1}{1-f}$ と変形できて、さらに $\frac{1}{1-f} = \frac{1}{1-\frac{x^3}{1-x}} = \frac{1-x}{1-x-x^3}$ より答は
$$[x^S]\frac{1-x}{1-x-x^3}$$
であることが分かります。
- 答を $a_S$ とすると漸化式 $a_{n+3} = a_{n+2} + a_n$ を満たすことが分かるので、順に計算して $\Theta(S)$ 時間で答が求められる。
- 多項式剰余（Fiduccia’s algorithm）や行列などを用いて、$\Theta(\log S)$ 時間で答が求められる。
といった方法があります。
問題F – Contrast
完全マッチングの存在判定・構築を問う問題であることはすぐに分かります。$A$, $B$ を $N$ 元集合と見なしておきます。
マッチ可能なペアに全て辺を貼ったグラフを陽に構成しようとすると、辺の個数が $\Theta(N^2)$ までありうるので、グラフを作る時点でTLE, MLEとなります。もちろん、最大マッチングの計算（例えば Dinic 法で $O(E\sqrt{V}) = O(N^{2.5})$ 時間）も間に合いません。
二部グラフの完全マッチングの存在判定では、Hall の定理 が基本的で、過去問でもしばしば考察の道具となっています。私はここから考察を進めました。
$A$ の部分集合 $S$ をとって、$S$ のいずれかの元とマッチ可能な $B$ の元全体 $N(S)$ を考えます。任意の $S$ に対して $|S| \leq |N(S)|$ となっていることが Hall 条件です。
$$N(S) = \{b\in B\mid \exists a \in S, a\neq b\}$$
となりますが、$S$ が $2$ 種以上の数からなるときには $N(S)$ は $B$ 全体になることがすぐに分かります。したがって、完全マッチングの存在条件は、$S$ が $1$ 種類の数からなる場合のそれがすべて満たされることと同値です。これは、
(★) 任意の $x$ に対して、$x$ の $A$ での出現回数、$B$ での出現回数の総和が $N$ 以下
という条件と同値です。必要性は明らかですが、十分性を Hall の定理が保証します。
あとは構築です。「ひとつのペアをマッチングとして確定させても、条件 (★) が維持できている」ようにペアを確定させていきます。
残り $N$ 数の時点で Hall 条件 (★) が満たされている場合、ひとペア確定させた後も (★) が維持されることは、「A, Bでの出現回数の合計が $N$ に等しいものは、必ずペアのどちらかに使う」(★★) という条件と同値です。この条件が常に満たされるように、ペアを作っていけばよいです。
はじめ、「要するに出現回数の合計が最多の 2 数を使っていけばいいなー」という構築アルゴリズムを考えました。これは誤りで、A = [1,1,1,2,2,2], B = [3,3,4,4,5,5] とかだと最頻値の上位 2 種をマッチできません。ということに実装途中で気づいて、「A･B 両方に出現している数のうち上位 2 種をマッチ」という戦略に切り替えて実装しました。
(★★) を満たしてさえいればどういう戦略でペアを作っていってもよいので、いろんな構築手順がありうると思います。