[AtCoder 参加感想] 2019/08/17:AGC 037

全体感想

143分で、ABDの3完 + 8ペナルティ。121位でした。

過去の参加回では、「ABCしか解けない人 / D以上が解ける人」で限界値が大きく異なるイメージがあったので、D以上に解けそうなものがあれば頑張るぞという気持ちでした。

Dを100分かけてACできました。やったぜ！スーパー高順位とれちゃうぞー！と思いましたが、3桁順位止まりでした(^^;)

Dは、考察の末に、有名定理に帰着できたのですが、それの実装に1時間以上かかる。初実装するアルゴリズムなんてそんなもんですよね、仕方ない。いい感じに実装経験値が増える良いコンテストでした。

問題A – Dividing a String

だいたい長さ1で取っちゃえば良い気持ちになる。greedyに長さ1,2を並べれば終わりそう？？と考えていると
 ‘aaaaa’
という実例でつまづく。左からgreedyにとると、「’a’, ‘aa’」を取った時点で詰むのだ。

しばらく、greedyを改良する方針で考えたけど分からず。「ここを長さ2にするとここを長さ1にできて……」と考えているうちに、「長さ1で取った場合・長さ2で取った場合」の2つともを並行して調べていけばよいという発想になった。

・dp_1[n] = （S[n]までぴったり作って、最後が長さ1）のときの最大項数
・dp_2[n] = （S[n]までぴったり作って、最後が長さ2）のときの最大項数

と置けば、$n$ の場合の値が $n-1$ とか $n-2$ から計算できます。

300点といえど、ABCコンテストのD～Eくらいあったように思います。

問題C – Numbers on a Circle

これは最近のAGC-Cの中ではかなり易しめ？問題Aよりも方針がすぐに立ちました。たまたま上手くはまったのかな？

$B$ の最大値は、最初から完成している場合を除けば、足し算で作られます。さらにこの値が両側より大きい間は、「足す側」にまわることはありません。したがって、$x,y,z$ という並びを、$x,y%(x+z),z$に取り換えることができます（$A$ 以上である範囲を保ったまま）。

・[9817, 1108, 6890, 4343, 8704]・[5, 1108, 6890, 4343, 8704]・[5, 1108, 6890, 4343, 8]・[5, 1108, 1439, 4343, 8]・[5, 1108, 1439, 2, 8]・[5, 1108, 329, 2, 8]・[5, 106, 329, 2, 8]・[5, 106, 5, 2, 8]・[5, 6, 5, 2, 8]・[5, 6, 5, 2, 1]

まだAと一致させられていないもののうち最大のものを順次着目していけばよく、pythonだとheapqを用いて実装できます。

はじめPyPyでTLEしたのですが、よく見るとTLEしているのは1例だけだったので、細かい高速化を数か所ほどこしてACを得ました。

問題D – Sorting a Grid

というわけで、私もこれから勉強してきますが、二部グラフの完全マッチングは$O(\sqrt{V}E)$とのこと。完全マッチングを作って引いていけば解けるので、D問題にしては結構簡単な部類だったのかもしれません。

全ての頂点の次数が $M$ の二部グラフは、$M$ 辺彩色可能で、このことは Konig の定理の一部となります。私はこの定理を用いて計算量を削減しました。

定理（Vizing）：グラフ$G$の最大次数$\Delta(G)$、辺彩色数$\chi'(G)$について$\Delta(G)\leqq \chi'(G)\leqq \Delta(G)+1$が成り立つ．

定理（Konig）：$G$を二部グラフとするとき、$\chi'(G) = \Delta(G)$ が成り立つ．

参考文献として、 @catupper さんのスライドを挙げておきます．
https://www.slideshare.net/catupper/ss-25736611

Konigの定理の証明は構成的で、 $G\setminus{e}$ の彩色から適当な2色をたどって交互道を作ることで、$G$ の彩色が構成できるという易しい証明です。交互道は $O(V)$ で構成できて、彩色全体の構成が$O(VE)$で行えます。（Vizingの定理は交互道に加えて回転のような操作も必要で結構複雑だったはず。）

個人的には、

★Konigの定理による辺彩色を初めて実装！
★二部グラフの最大マッチングの計算量の誤解を解消！

ということで、経験値の多く得られたコンテストでした。