2-SAT
問題 問題概要 指定された場所にマッチを置く. マッチの置き方は上下の2通りの選択肢がある. 置き方を工夫して, 頭薬の部分が重ならないようにおけるかを判断せよ. 解法 単純にやるには, すべてのマッチ棒を上下試してやればいいが, 2nかかるため無理. そこ…
問題 問題概要 ブロックを縦に並べる。ブロックは、180度回転をすることができる。ブロックをすべて縦に並べた時に、同じ列にブロックが1つのみになる並べ方があるかを求める問題。 解法 愚直に考えると、1つのブロックに対して、落とす方法が2通りなので、2…
問題 問題概要 3つの文字でできている文字列があたえられる.それらを前後で分けて、すべての文字列が相異なるように分けられるなら分けろ。 解法 考察として、文字を分けるのは1-2または2-1の2通りしかないので、2n通りすべてを調べれば答えが求まることがわ…