問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_05） 変数がn, 節の数がm以下の乗法標準形の論理式が与えられる。 （よくある2-SATの(x1 or x2) and (~x3 or x4) and ...みたいな形という意味） この式に対して変数の割り当…

問題 n個のバルブとm個のスイッチがある。 それぞれのスイッチがどのバルブにつながっているかは、switchesにより与えられる。 最初、それぞれのバルブはinitial[]の状態となっている。 スイッチを押すと、つながっているバルブの状態のONとOFFが切り替わる…

問題 同じ大きさをしたn個の正方形を座標平面上に、軸に平行に、かつ重ならないように置きたい。 それぞれの正方形の中心の座標は(xa[i],ya[i])または(xb[i],yb[i])のどちらかでなければならない。 正方形の一辺の長さの最大値を求めよ。 制約条件 n≦50 座標…

蟻本復習中。 問題 N組のカップルが同じ日に結婚式を挙げる。 i番目の結婚式は時刻s[i]からt[i]の間に開かれ、その最初か最後のどちらかのd[i]分間特別な式典を行う必要がある。 （s[i]〜s[i]+d[i]かt[i]-d[i]〜t[i]のどちらか） 式典には司祭の出席が必要で…

問題概要 m枚の扉を順に、なるべく多くの枚数を開けたい。 扉には二つの錠があり、どちらかの錠を開ければ扉は開く。 錠は2*n種類あり、全ての錠にはただ一つの異なる錠が対応している。 錠の鍵を一度使用すると、対応する錠の鍵は消滅して使用不可能になる…