ARC114-EとAGC049-Aの類似性について
こんにちは，関西（にいた）組合せゲーム理論徒ことCOOH2です．ARC114に参加しました．Bで時間がかかった挙句CDが相性悪くて解けなかったため大幅にレーティングを落とすことになり残念です．本番中は十分な考察の時間を取れませんでしたがEは自力考察で通せたためこちらから取り組んだ方がよかったかもしれません．
さて，そのARC114-EですがTLでも何人か指摘しているとおりAGC049-Aが利用できます．私もその方法で解いたので紹介したいと思います．
問題として与えられる方眼紙を考えます．このうち，黒マスが二つあり，この二つを結ぶ線を対角線とする長方形を考えることができます．ここで，この長方形の内部を通る直線を選択したときに操作は終了します．この長方形のことを便宜上「灰色長方形」と呼びます．（下図，黒色＆灰色の長方形）
ここで，問題の言い換えを考えます．直線を選ぶごとに元の紙の一部が捨てられていきます．言い換えれば，直線を選ぶごとに「選ぶことのできる直線」が減っていく，より突き進めると，「直線を選ぶごとに何本かの直線が削除されていく」ということになります．灰色長方形の内部を通る直線を選択した時，操作が終了するので言い換えればすべての直線が削除されます．また，灰色選択肢の外部を通る直線を選択した場合は，自分自身と，それよりもさらに外側の直線が削除されます．例えば，左から二つ目の直線を選択すると，そこから左側の紙が削除されますが，これは左から一本目と二本目の直線が削除されたと見做せます（下図参照）．
ここで直線の個数だけ頂点を持つグラフを考えます．それぞれの直線に対して頂点を対応付けます．直線Aを選択したとき直線Bが削除されるときに，頂点Aから頂点Bに有向辺を引きます．
このようにすると，有向グラフがあって，操作ごとに頂点を一つ選び，選ばれた頂点と，そこから到達可能な頂点をすべて削除するとき，操作回数の期待値はいくつか，という問題に帰着されます．これはAGC049-Aです．入力データの制約が異なりますが，同じ解法を利用して解くことができます．具体的には以下の通りです．
それぞれの頂点に注目して，その頂点に到達可能な頂点の個数（自分自身を含む）の逆数の総和がAGC049-Aの解でした．元の問題に戻って考えると，それぞれの直線に着目して，その直線を削除するのは，灰色長方形の内部を通るすべての直線（縦向きも横向きも）および，その直線と平行で，灰色長方形とその直線の間にある直線です．この個数は各直線に対して直ちに求められます．直線の本数は(H＋W-2)本しかないので，十分速く解が求められます．
案外綺麗に解が求まったので，コンテスト中にこちらに注力できなかったのは残念でした．最近はARCでもあまりレーティングが伸びなくなってきたので，AGCに特化したいという思いが芽生えていますがさすがに回数が少ないのでもうしばらくはARCも出続けようかと思います．
