読者です 読者をやめる 読者になる 読者になる

ctyl's problem solving

競技プログラミングが主な話題です。

Codeforces AIM Tech Round Div.2 C Graph and String

本番はSCCに固執しすぎて実装が間に合わず.その後冷静に考えたらもっと単純な方法があった.

解法

まず気づきそうなこと:実線は辺,点線はそうでないとする.次のようなグラフの場合,bは一意に決定する.

f:id:ctylim:20160206160557p:plain:w250

そこで点線を辺とする(完全グラフから与えられるグラフを引いた)グラフに着目する.このグラフが下のように2つ(以上)に独立していると仮定する.

f:id:ctylim:20160206160600p:plain:w250

点線の両端は(a,c)で一意に決定する.

f:id:ctylim:20160206160603p:plain:w250

上と下のa,c同士は必ず結ばれる.

f:id:ctylim:20160206160604p:plain:w250

よってそのようなグラフの仮定は間違っていて,点線で構成されるグラフは連結である.それを確認した上で,(a,c)は辺で結ばれ,(a,a),(c,c)は結ばれないような判定をすればよい.幅優先探索などで深さの順番にa,c,a,c,...とメモして行って,最後に全ての頂点の組み合わせで前述の判定をすると上手くいく.

AIM Tech Round 2C

二部グラフの判定方があればそれを使えばよさそうですが,自分はあるかどうかすら知らないです.もっといい方法があれば教えて下さい). 時間内に解けたら美味しかっただけに悔しい回でした.