AtCoder Grand Contest 025
Updated:
ペンディング。 D の実装だけまだ。 E も解説を聞いて解けそうなら解く。
Source codes
Solutions
A - Digits Sum
コンテスト中に思いついた解法
$B = N - A$ として、指定通りにするだけ。コンテスト中はこれが良いそうです。
模範解答
例えば $4514 + 6033 = 10547$ の各桁の和を計算すると $14 + 12 \geq 17$ である。繰り上がりがある分、前者の方が大きい。求める値は下から $N$ の digit sum で押さえられる。繰り上がりがないように適当に $2$ つに分けることができればそれが答えである。つまり $N = 10^k$ の形でなければ、答えは $N$ の digit sum である。 $N = 10^k$ の形はどのように分解しても繰り上がりは起こる。最適は $10^k = 9 \cdot 10^{k-1} + 10^{k-1}$ 。よって $10$ が答えである。
B - RGB Coloring
赤色と青色を独立に塗っていく。両方塗られたブロックを緑色に塗ったと解釈して得点計算すればよい。
赤色を塗ったブロックの個数を $k$ 個とし、青色を塗ったブロックの個数を $l$ 個とする。すると $A k + B l = K$ が成立する。この方程式が整数解 $(k, l) \in \mathbb{Z}^2$ を持つための必要十分条件は $g = \mathrm{gcd}(k, l)$ について $g | K$ であることである。まずこれが成立していなければ答えは $0$ である。あとは $0 \leq k, l \leq N$ を充たす $(k, l)$ の解を全部求めれば良いが、これは素直に $k = 0, \dots, N$ についてループを回して求めて十分である。その解の全体集合を $S$ とおけば、求めるものは、 \[ \sum_{(k, l) \in S} \begin{pmatrix} N \\ k \end{pmatrix} \begin{pmatrix} N \\ l \end{pmatrix} \] である。実装はすこぶる簡単である。
ポイント
数学色が強いからすぐに求めることができた。最近の高校の数学のカリキュラムには、我々の時代と違って不定方程式の整数解があるらしいから、若ければ若いほど有利である。
C - Interval Game
高橋君の最適戦略は明らかである。 $[L_i, R_i]$ が与えられたときに、区間の左側にいたら $L_i$ まで動く、右側にいたら $R_i$ まで動く、区間の中にいたら動かない。
全部置いていくのが条件だが、 全部置かないことにしてもよい ことにする。次の置き方はしないことにする。
- 高橋君を右に動かした後、さらに右に動かす。左も類比的。
- 高橋君がすでにいる区間を指定する。
どちらも無駄であるのは明らかであろう。さらにいうと、これらをしても距離はさらに長くなることもないことに注意されたい。すると、できる動作は次のものに限られる。
- 最初に右に動かす。次に左に動かす。次に右に動かす。これを繰り返す。ただし (右, 左) を swap したものも類比的。
すると移動距離の最大値は以下の通り。 \[ \max_{\sigma, \sigma’ \in \mathfrak{S}(N)} \max_{k, k’ \in \mathbb{N}, \lvert k - k’ \rvert \leq 1, k + k’ \leq N} \sum_{i = 0}^k 2L_{\sigma(i)} - \sum_{i’ = 0}^{k’} 2R_{\sigma’(i’)} \tag{C.1} \] ここで次の補題を示す。
補題：(C.1) 式で最大値を達成する $\sigma, \sigma’, k, k’$ において、「$0 \leq i \leq k, 0 \leq i’ \leq k’$ が存在し $\sigma(i) = \sigma’(i’)$ である」ということはない。
証明は背理法による。もし存在するとすると、 $x = \sigma(i) = \sigma’(i’)$ とすると $2L_x - 2R_x < 0$ であるから、これを取り除いたほうが、より大きくなる。これは最大性に反する。よって補題が示された。
この補題は $\{ L_i \}$ と $\{ R_i \}$ は 独立にソートして貪欲に 選んで良いことを示している。 imos 法を用いれば、前準備 $O(N \log N + N)$ で、 $O(3N)$ 個の各 $(k, k’)$ クエリには $O(1)$ で応答できる。よって時間計算量は $O(N \log N)$ である。
ポイント
わかってしまえば単純だが、いくつか次に繋がるポイントがある。
- 求めるものが $\max_{x \in S} A_x$ であるとき、 $S’ \supset S$ を見出し $\max_{x \in S} A_x \geq \max_{x \in S’} A_x$ であることを確認して、前者の代わりに後者を考えることで簡単に解ける可能性がある。日本語で書くならば 最大値・最小値を求める際に、条件を緩めても(考慮する場合を追加しても)同じ値になることが保証されているならば、緩めてから考察する が大事である。
- 今回の場合は、「全部選ぶ」から「使わないものがあっても良い」に緩めている。これによって最大値が変わらないのは今回の場合明白である。しかし緩めることにより (C.1) 式にたどり着く。
- ARC100 E - Or Plus Max も同様である。
- 複数の値を最適化する際に、 関係性があるように見えても、実は独立に選んで良い場合がある 。ゆえに貪欲法で良い場合がある。
- 今回の場合、「両方選ぶと損をする」を見出すとこれにたどり着く。
- 類題が思いつかない。
D - Choosing Points
考察
$K = N^2$ とする。まず一般化して考えると、以下の問題を解くことになる。
問題：頂点数が $4K$ 個ある。グラフを $2$ つ与えられる。どちらのグラフで見ても独立集合となっているような $K$ 頂点の集合を $1$ つ求めよ。
まず、以下の補題を示す。
補題 1： 2 つのグラフが二部グラフであれば、求める $K$ 頂点は得られる。
証明：具体的に色を塗ることにする。一方のグラフを赤・青で塗り、もう一方のグラフを黄・緑を塗ることにする。もちろん $1$ 頂点からなる連結成分も好きな方の色で塗る。すると頂点は次の $4$ パターンに分かれる： (赤、黄)、(青、黄)、(赤、緑)、(青、緑) である。鳩の巣原理により、このうち $1$ つは $K$ 頂点含まれている。それを $K$ 頂点出力する。
求めるグラフが二部グラフになっていれば解決だが、実際にそうなっている。
補題 2： $2N \times 2N$ 個の格子点の集合 $V = \{ (x, y) \in \mathbb{Z}^2 \mid 0 \leq x, y < 2N \}$ を頂点集合とし、そのうち距離 $\sqrt{D}$ ($D \in \mathbb{N} \setminus \{ 0 \}$) の 2 点を結んだものすべて、そしてそれらのみを辺とするグラフは、二部グラフである。
ここまでわかれば解答はかける。あとは証明を念のため書く。
補題 2 の証明
証明：まず $D$ が奇数の場合を示す。格子点をチェスの盤面に対応させる。チェスの盤面は市松模様に塗られているが、辺が張られている片方の頂点は黒マス、もう片方の頂点は白マスで塗られていることを示せば主張が従う。必要ならば平行移動・色彩反転をすることにより、頂点は $(0, 0)$ と $(x, y)$ としてよく、 $(0, 0)$ は黒であるとして良い。ここで $x^2 + y^2 = D$ が成立するが、 $D$ は奇数であるから、 $x^2$ と $y^2$ の偶奇は異なる。したがって $x, y$ の偶奇は異なる。ゆえに $x + y$ は奇数である。したがって $(x, y)$ は白色で塗られていることが従う。以上により、 $D$ が奇数の場合が示された。
続けて、 $D$ が偶数も含めた一般の場合を示す。 $D = m \cdot 2^n$ とし( $m$ は奇数、 $n$ は自然数)、 $n$ についての数学的帰納法で示す。 $n = 0$ の場合は $D$ が奇数であるので上記の議論に帰着される。以下、 $n$ での成立を仮定し、 $n + 1$ での成立を示す。すなわち $D = m \cdot 2^{n+1}$ である。同様にチェス盤で考える。必要ならば平行移動・色彩反転をすることにより、頂点は $(0, 0)$ と $(x, y)$ としてよい。ここで $x^2 + y^2 = D$ が成立するが、 $D$ は偶数であるから、 $x^2$ と $y^2$ の偶奇は一致する。したがって $x, y$ の偶奇は一致する。ゆえに $x + y$ は偶数である。そこでこのグラフは、黒マス同士を結ぶ辺と白マス同士を結ぶ辺しか当たられていないことがわかる。そこで元のグラフの黒マスを集めてきた部分グラフを $B$ とし、白マスのそれを $W$ とする。これらは完全に分離している、つまり元のグラフはこれの disjoint union であることに注意されたい。
新しい座標 $(X, Y)$ を $X = x + y$, $Y = x - y$ で与えることにする。 $V$ の前の座標の空間を $V_0$ とし新しい座標の空間を $V_1$ と書くことにする。それぞれの標準ユークリッド距離をそれぞれ $d_0, d_1$ とする。すると $d_1 = 2d_0$ である。そこで $V_1$ の部分距離空間 $(B, d_1)$ と $(W, d_1)$ をそれぞれ考察する。どちらも同じなので前者を考察し、同じ記号で $B$ と書くことにする。 $B$ においては、距離 $D/2 = m \cdot 2^n$ 同士の頂点が接続されている。これは帰納法の仮定により二部グラフである。したがって、元のグラフは二部グラフの disjoint union であるから、やはり二部グラフである。よって示された。
なお、途中の議論は $x + y = (x + y)^2 = (x^2 + y^2) + 2xy = x^2 + y^2$ in $\mathbb{Z}/2\mathbb{Z}$ を用いれば即座に従う。
解答
$4K$ 頂点で距離 $\sqrt{D_1}$ の頂点を結んだグラフを $G_1$ とし、 $4K$ 頂点で距離 $\sqrt{D_2}$ の頂点を結んだグラフを $G_2$ とする。それぞれ二部グラフであるから、色を塗る。最多の色の組の頂点を $K$ 個出力する。そのまま実装すると、グラフを作るところで計算量は $O(N^4)$ になり、さすがにこれは通らないことに気づく。
グラフを作るところは次のようにやる。 $k = 0, 1$ とする。まず $-2N < x < 2N$, $-2N < y < 2N$ について $x^2 + y^2 = D_k$ となるペア $(x, y)$ を vector<P> W[k] に入れる。ここで例えば typedef tuple<ll, ll> P にようにする。続けて $q \in V$, $p \in W_k$ に対し、 $q + p \in V$ ならば P を型として取る vector の $q$ を index とするものの中に $q + p$ を入れる。つまり $q$ と $q+p$ をつなぐ。平行移動しても相対的な位置関係が変化ないことを用いている。
最悪計算量を見積もる。 $L = \lvert W_k \rvert$ とする。すると $O(KL)$ である。 $L$ は $x^2 + y^2 = D_k$ を充たす整数解 $(x, y)$ の個数であるが、最悪でも $O(N)$ は超えない。というのも $-2N < x < 2N$ をひとつ決めると、せいぜい $y$ は $2$ 個あるかである。だから $O(N)$ は超えない。ゆえに計算量は $O(N^3)$ で抑えられている。 $N = 300$ だと「ちょうどいい感じです！」 (スクストのほたるちゃん風に)
ポイント
- まずは 与えられたグラフの特徴を考察 する。独立集合は、二部グラフであれば楽勝で取れる。これが「独立集合」と聞いた瞬間に「二部グラフでは」と行かないと辛い。
- SoundHound Inc. Programming Contest 2018 (春) C - 広告 独立集合と二部グラフについてまとめてある。
- 斜め $45^\circ$ 回転 の定跡である。
- 数え上げテクニック集 14.3 節 に示唆的なことが書かれている。
グリッド上を上下左右に点が移動するというのは、競技プログラミングの問題ではよくある設定です。そのような場合に、盤面を $45$ 度回転することで $xy$ 座標を 独立に 扱えるようになる場合があります。 (太字は筆者)
- 数え上げテクニック集 14.3 節 に示唆的なことが書かれている。