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

  A B C D E F
問題文
自分の提出
結果 AC AC AC

スポンサーリンク

全体感想

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

実例を触りながら考える。まず、3手目でやるべきことは明白です。さらに、3手目開始時点で、行ごとに集合として完成していればよいことが分かります。したがって、2手目でやるのは列ごとのソートです。結局2手目以降は操作が確定するので、1手目で

・列ごとに、完成図における1行目、2行目、3行目、…に並ぶ数をひとつずつ入った状態

にしたいという問題だと分かります。特に、数値は目的行だけを見て盤面を簡略化します。
各列ごとに、目的行が 0,1,…,N-1 行目であるような数を1度ずつ持ってこないといけません。これは、二部グラフの完全マッチングと言い換えられました。
結局のところ、次の問題が本質です:
$G = (V_1,V_2)$ を全ての頂点の次数が $M$ であるような二部グラフとする.
これを完全マッチング$M$個へと分解せよ.ただし,この条件下で解の存在が保証される.

問題文に存在の保証が書かれているので(Hallの定理などの理解が不要で)少し易しいです。ひとつマッチングを取り去った残りのグラフも同じ条件を満たすので、「マッチングを見つける→取り去る」を逐次的にやっていけばよいことになります。
ここで、計算量について考えた結果、この方針をいったん捨てます。

・マッチングひとつあたり、$O(VE) = O(N^2M)$。
・マッチングを$M$個つくるので、$O(N^2M^2)$。

(本番中は全然足りないと思ってしまいましたが、実際には分母の多い$O(10^8)$なので安易に捨てたのは良くなかったかもしれない…。)

そして、この計算量評価、間違っていました。

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

ところで、完全マッチング $M$ 個への分割は、$M$ 辺彩色とも言い換えられます。辺を $M$ 種に分類していると思えば、そのまま彩色になりますね。

1 4 7 10
2 5 8 11
3 6 9 12

0 0 1 2
0 1 1 2
0 1 2 2

0 0 1 2
1 2 0 1
2 1 2 0

全ての頂点の次数が $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の定理による辺彩色を初めて実装!
★二部グラフの最大マッチングの計算量の誤解を解消!

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

タイトルとURLをコピーしました