AtCoder Grand Contest 025 - 情報妖精の競プロ日記

AtCoder Grand Contest 025に参加しました！
AGC025 旧版:
agc025.contest.atcoder.jp
AGC025 beta:
https://beta.atcoder.jp/contests/agc025/beta.atcoder.jp

解けた問題だけ解説をしていきますー

要項

AtCoder Grand Contest 025
rated
6/3(日) 21:00 ～ 23:10 (130分)
200-700-700-800-1500-2400 (6問)
ペナルティ: 5分

方針

4完を目標に、解ける問題から順に解いていく
配点にそこまで差はないから、多分問題ジャンルが大きく異なるセットと予想

A - Digits Sum

まず、 $A$ と $B$ に対し $A+B=N$ と分かっているから、 $A$ を固定すると $B$ は一意に定まります。
この時桁の和は $O(\log N)$ で求まるので全体で $O(N \log N)$ で求めることができます。
なおちゃんと考察すれば $N = 10^k$ なら $10$ 、そうでないなら $N$ の各桁の和に等しいので $O(\log N)$ で求まることが分かりますが今回は不要ですかね。
ちなみに、各桁の……と言われた時はstring型とかにして各桁を取り出すと楽らしいです。
この方法の時、答えが $1$ になるなら代わりに $10$ を出力する形式で上の条件分けも達成できます。

B - RGB Coloring

変数が複数ある時は、幾つかを固定して考えてみましょう。
まず、入出力例1から分かるように各色の個数を考える必要があります。
そこで、美しさが $K$ になるような色の個数を考えましょう。
これは $Ax + By = K$ かつ $0 \leq x, y \leq N$ を満たす $x, y$ を求めれば良いので、 $x$ を固定すると $y$ は一意に定まることから $O(N)$ で求められます。

次に、 $x, y$ が求まっているときのタワーの塗り方を考えます。
これは、 $N$ 個の中から $x$ 個を塗る方法と $N$ 個の中から $y$ 個を塗る方法の積に等しいですね。
何故なら、緑を忘れて考えると赤色と青色を $x, y$ 個のブロックに塗り、緑色は両方で塗られた場合と考えることができるからです。
さて、 $N$ 個の中から $x$ 個を塗る方法は ${}_N C_{x}$ 通りです。

ここでこれがコンビネーションの導出であること、また $998244353$ で割った余り……つまり $P=998244353$ とすると $P$ は素数なので素数で割った余りなことに注目しましょう。
${}_N C_{x} = \frac{N!}{x! (N-x)!} = N! \cdot (x!)^{-1} \cdot ((N-x)!)^{-1}$ であり、前もって $1!$ から $N!$ を求めておくと計算しやすいです。
$N! = N \cdot (N - 1)!$ であることを利用すればこれは下準備 $O(N)$ で導出できます。
フェルマーの小定理より $A^{-1} \equiv A^{P-2} \mod P$ ( $P$ は素数)であることを利用し、 $N!$ から $(N!)^{-1}$ は $O(\log P)$ で導出できます。
次に $((N - 1)!)^{-1} = N \cdot (N!)^{-1}$ を利用して $(1!)^{-1}$ から $(N!)^{-1}$ も下準備 $O(N)$ で導出できます。
これら下準備 $O(N + \log P)$ をすることで、 ${}_NC_{x} \cdot {}_NC_{y}$ を $O(1)$ で導出できることから、全体で $O(N + \log P)$ で解くことができます。
競プロでは $\mod 998244353$ や $\mod 1000000007$ のような素数は頻繁に使うことを考えると、逆元とコンビネーションに関するライブラリは作っておいて損はないでしょう。

C - Interval Game

先に問題文を整理しましょう。
高橋君の移動は、必ず指定された区間の左端か右端の内近い方に移動する、あるいは(既に区間内なので)移動しないの3通りしかあり得ません。
ということは、最小値の最大化問題とかではなく、単に最大のパターンを出す問題であることが分かります。

まず、ある方向に2回連続で動くことはないことを考えます(最初に使った区間が無駄になるだけです！)
ということは毎回移動方向が切り替わるので、2回の移動を1セットとして考えましょう。
また、移動距離が0の区間を抽出することも無駄なので、移動しないパターンは無視するようにします。
次に、この1セットではなるべく移動したいと考えられるので、移動区間が最も長くなるような配置を考えます。
左側の移動位置を $R_1, R_2, \cdots ,R_x$ 、右側の移動位置を $L_1, L_2, \cdots, L_x$ とします。
また、 $1 \leq i \leq x$ において $R_i < L_i$ とします。
この時、移動距離を計算すると $(L_1 - 0) + (-R_1 + L_1) + (L_2 - R_1) + (-R_2 - L_2) + \cdots + (-R_x - L_x) + (0 - R_x) = \sum_{i=1}^{x} 2 (L_i - R_i)$ となります。
0の場合分けを外すためにあえて区間 $(0, 0)$ を追加することで、簡単な総和で解くことができます。
また、条件を鑑みると $L$ を降順に、 $R$ を昇順にしておけば順番に $R_i < L_i$ を満たすものを取っていくだけで求められることが分かります。
同じ区間を2回取る問題に関しては区間 $(L_i, R_i)$ では $L_i < R_i$ より不適なので場合分けせずとも弾かれます。

結果

ooxxxx 2完(900点) 29:34(1WA)
316位パフォーマンス: 2022
レート: 1826→ 1847(+21)

感想

えーC問題は解くべき問題でしたね、考察不足で反省。
また、D問題ですが条件が2つ、範囲が $4N^2$ なので各条件で半分以上を残す……つまり二部マッチングの多い方を残すという発想に至らなかった点は反省です。
Dに関しては二部マッチングを避けていたのが悪いので精進します。
ただ、二部マッチングを使わずともこれは構築ゲーなのでシンプルな解答があると考えられます。
Dに関しては、 $D_i = 2^x \cdot$ 奇数の形に持ち込むことで各マスについて点の存在を $O(1)$ で数学的に解ける気がするので挑み直したいなー