SRM527 Div1 Medium

450

辞書順最小は先頭から決める。
1つ以上の答えがあるそうなので、順に0を割り当てて試す。
ある場所に0を割り当ててマトリックスを作れないのならば、そこに1を入れればいい。
マトリックスになるかどうかは、2部マッチングをすればよい。

SRM527 Div1 Easy

275

dp[グラフの頂点数][葉の数]
解いたの忘れて2度目の挑戦。

LiveArchive4035

4035 - Undetectable Tour

どういう場合に到達不可能になるのかを考える。

センサーのカバーしている領域だけを通って
"領域の上から領域の下まで移動できる"
"領域の上から領域の右まで移動できる"
"領域の左から領域の下まで移動できる"
"領域の左から領域の右まで移動できる"
の4つの条件のうち1つでも満たせば到達不可能になる。

全てのセンサーの位置と各センサー(x, y)から最短で行ける領域の端(x, 0), (0, y), (x, N-1), (N-1, y)の位置を頂点とする様なグラフを作る。
(始点と終点の扱いには注意すること。領域の端を全て頂点にしてしまうとTLEする。)
このグラフ上で4つの条件のどれかを満たす様なパスの最大の辺の重みの最小値がセンサーに捕捉されずに到達可能な距離の上限になる。

やりかたは色々あるだろうけど、条件を満たすまで辺の重み順にUnionFindした。

SRM560 Div1 Easy

250

貪欲。

SRM495 Div1 Easy

275

memo[どこまで見た][最後に使った数] = 最後まで作りきれるかどうか
バックトラックしていたら終わらないので、到達可能かどうかをメモ化する。
到達可能と判断できた瞬間にそれまでのパスをなぞる。

SRM559 Div1 Easy

250

SRM430 Div1 Medium

500

最大の次数が３なので、ある頂点に関して状態を2ビットで表せる。
DP[4^20]

SRM430 Div1 Easy

250

xの２進数表現で0のビットを下位から埋めていく。