ARC103-E:Tr/ee(700)

グラフ 構築

問題

長さ n の文字列 s が与えられる。以下の条件を満たす n 頂点の木を構築することができるかどうか。

  • 頂点 s_i の文字が 1 であれば、木から辺を 1 つ取り除いて、長さ i の連結成分を作ることができる
  • 頂点 s_i の文字が 0 であれば、木から辺を 1 つ取り除いて、長さ i の連結成分を作ることができない

※ i は 1-indexed

考え方

まず、木を構築するための必要条件を整理する。以下の条件を満たす場合は目的の木を構築することはできない。

  • s_n が 1 (サイズ n の木は作ることはできない)
  • s_1 が 0 (1 本切ることで必ずサイズ 1 の木は作るカットが存在する)
  • s_i \neq s_{n - i} (あるカットでサイズ i の連結成分を作るとき、もう片方のサイズは n - i になっているため)

逆に上記の条件を満たさなければ、目的の木を構築することができる。放送解説の通りだが、以下がその一例の木である。

f:id:d_tutuz:20180930085454p:plain

ポイント

  • 必要条件で絞り込む
  • 対になる条件を考える

類題