ARC111

ABDの3完。難しい問題はあとにいくらでも控えてるのに、スピードだけの勝負しかできない。最近のコンテストで難問が復習対象(解けなかった1問)になってないのが不満。

A - Simple Math 2

一見してとっかかりがないけど、Mで割って切り捨てるのは10進法で123を12にするようなものだと気づいて解けた。M進法での下から2番目の桁が答えなので、下2桁がわかればよく、これは繰り返し2乗法をmod M^2でやれば求まる。M=1の場合も最後にmod MとるのでOK。

B - Reversible Cards

これもさっぱりわからない。Aと違って全然わからない。とにかく確定できるものだけでもどんどん書き出していく。他の問題も考えていたのでそこに出てきたグラフが頭をよぎる。400000頂点N辺のグラフがあって、各辺について片方の頂点だけを黒く塗れる、最大でいくつ塗れるか。いやあこういうのはやったことある。既出の考え方だ。めちゃくちゃ時間かかってしまった。しかも、これから実装をしないといけない。

連結成分毎に考える。それがK頂点の木であればK-1辺なので多くてもK-1個しか塗れないし、根付き木にして子を塗ることにすれば達成できるのでK-1。そうでないとき、全域木をとってあまった辺が付いてる頂点の一つを根としてそこをさっきのあまった辺で塗れば全部の頂点が塗れる。グラフを構築しようかとも思ってけっこう迷ったけど、UnionFindで頑張った(連結成分内の辺の個数も管理させる)。400000とNを取り違えたり、頂点数と辺数を取り違えたりして、サンプルを通すのにも少し時間をかけた。

(解説を読んで)黒く塗るんじゃなくて光らせてる~w(僕の場合は紙で白丸の頂点を描いていたのでこうなった)

C - Too Heavy

なにもわからない。人は重いほどいいし荷物は軽いほどいい。荷物の立場だと可能な移動元(人)が決まっている。人を軽い順にソートしておけばよさそう。で、荷物がどう渡り歩くか。人と荷物を入れ替えても解きやすくはならなそう。疲れるのは荷物としていいかな。swap回数の最小化って、荷物が十分軽かったら貪欲でいいのかな。置換の話だよね。重いほう軽いほうどっちかから貪欲できそうな気もする。動けない荷物は除外して、一番重いやつは誰とでも気がねなくswapできる(自分は疲れて動けなくなるかもしれないけど)。といった辺りで時間切れ。

D - Orientation

これも自由度が高すぎて困る。まず次数1の頂点に付いてる辺から考えると、これは1かどうかで確定する。グラフが木なら全部確定しそうだ。解が存在する入力しか与えられないというのを生かそうと考える(そのくらいしかとっかかりがない)。木でないなら閉路がある。答えの有向グラフで閉路があるなら行ける頂点数はみんな同じはずだ。絵を描いてみると、そもそも辺がつなぐ2頂点のc_iが異なるなら小さいほうへ向けて有向辺を張るしかないと気づいた。これで残るは同じやつだけ。同じやつが連結であればループにする(相互に行き来可能にする)しかない。

あとは閉路を作るだけ。DFS木で既出の頂点に当たったときも順方向へ辺を張ればループになる。DFS木の根も次数2以上なので必ずどこかから帰ってくる。これ、コンテスト中ちゃんとわかってたか?なんだかんだコンテスト中の自分のほうがしっかり考えてることは多いけど、これはさすがにがっつり考え抜けしてそう。根からはどこでも行けて、あるループの中にあるけど、他の頂点もそうなっていることまで保証してない気がする。いや難しいな。DFSでループは見つかるし、見つかった時点でそのループに属さない探索済みの頂点はないってことで、どの2頂点間も行き来できるグラフなんだからいつかはそこへ併合されるってことかな。木以外のDFSの理解が全然だった。

実装というかデバッグもかなり大変だった。e[j]の逆辺がe[j ^ 1]になってるのを久しぶりに使った(もう全然思い出さなかった)。無向辺は有向辺*2として登録してあるけど、DFSでは1回ずつしか使わないようにする。残り9分になってようやく提出。

(解説を見て)ひええ、解が存在するかの判定までやると計算量変わるんだ。