AGC027-C ABland-Yard

初AGC2完記念(今更？)＆初900AC記念＆初黄パフォ記念。

問題概要

N頂点M辺のグラフがある(単純とも連結とも限らない)。各頂点にはAまたはBと書かれている。好きな頂点を始点とし，好きな回数隣接する頂点の移動をしたときに，訪れた頂点に書いてある文字を訪問順に並べることでAとBからなる文字列を作る。このとき，AとBからなる任意の文字列を作ることができるか判定せよ。
C - ABland Yard

考察過程

まず，問題の条件を次のように言い換えた。

与えられたグラフの連結な部分グラフHであって「Hの任意の頂点について，Aと書かれた頂点にもBと書かれた頂点にも移動できる」ようなものが存在する。

もとのグラフはGとして，Gの頂点のうちAにもBにも移動できるものを良い頂点，できないものを悪い頂点と呼ぶことにしよう。Gのうち連結な良い頂点の集合を探せばいいのだから，Gの各頂点が良いか悪いかを判定して，良い頂点の連結成分(大きさ2以上)があるかを判定すればいいと思ったのだが，サンプルさえ通らず考え直す。

よく考えると，目標は上のような部分グラフHがあるか判定することであったから，一番最初の時点で悪い頂点はHを構成する頂点になり得ない。だから，悪い頂点はないものと考えてよい。

さらによく考えると，悪い頂点をないものと考えたことによって，最初は良かったはずの頂点が悪くなっていしまう可能性があることに気付く。悪は伝搬するのである。この伝搬を素直に見ていって，すべての頂点が悪くなったらNo，良い頂点が生き残ればYesっぽいということがわかった。

そうすると，これをシミュレートする方法を考えればよい。頂点vの，隣接する頂点でAが書かれているものの数をa_v，Bが書かれているものの数をb_vとする。a_v,b_vの一方が0であればvは悪い頂点である。これはBFSでできる。
まとめると

  1. 最初に，すべての頂点vについてa_v,b_vを数えて，この時点で悪い時点をqueueに入れる。
  2. queueから頂点vを取り出し，隣接する頂点にvが悪いことを伝える。つまりvに書かれた文字がAなら，vに隣接する頂点uについて，a_uを1減らす。Bの場合も同様である。
  3. 2によって悪くなった頂点があればqueueに入れる。
  4. 2~3をqueueが空になるまで繰り返す。
  5. 悪くなった頂点の数をカウントし，N個ならNo，そうでないならYesである。

計算量はO(N+M)であり，間に合う。実はコンテスト中はTLEするかもと思っていた。

提出

コンテスト中に出したものは試行錯誤の残骸が多く汚いので，整理したものを貼る。実装は重くないと思う。
Submission #3206813 - AtCoder Grand Contest 027

雑談

  • うまく頂点を増やして辺を張って閉路検出という方法もあるらしいが，それよりは比較的自然に出てくる解法だと(個人的には)思う(自分で思いついた方を自然に思うに決まっている)。閉路検出が書けるか怪しいため，後でやってみる。
  • パフォは2143でレートが100くらい上がった。嬉しい。最近の精進の結果が少し出たかもしれない。今解説を見ても天才だな...と思うってしまう問題でも，そのうち自然だなあと思えるようになってくるのかもしれない。
  • この回のAGCはBが100人程度しか正解していないという恐ろしい回だった。Bを10分くらい考えて無理そうと思い，(その時点での正解者数を勘案して)Cに振ったのは正解だった。