568.1

問題悪くないのに結果だけ見るとダメなセット。

250

3色のボールが混じった箱がいくつかある。それぞれの箱に複数の色のボールが入っていないように移動させるとき、最小で何個移動させる必要があるか答えよ、という問題。

テンプレやるだけ。

500

一部穴の開いた行列が与えられるんで、各行各列から一個ずつ要素を選んだ時の合計が常に一致するような行列に完成させたい。何通り可能か答えよ、という問題。各要素は非負。

行ごとに見ると隣の行との差分は一定だし、列ごとでも同様。となると自由度は行数+列数になる。更に、出てくる値が非負であったり、初期値が小さかったりを使うと探索が割といけるのかも。

(i,j)+(k,l)=(i,l)+(k,j)が常に成り立つので、このうち1個欠けている状況なら決定可能。1個も欠けていない状況なら、この式を満たすかチェックしておく必要がある。ただし、決定した値が負になるケースはダメ。伝搬にも注意。

以上を踏まえると、各行について、同じ要素が埋まってる行が他にあるか、全然違う要素が埋まっている行が他にある。(後者は答えが決定できるという性質から。)で、同じ要素が埋まってる行については、各要素の差分が一定。なので、それらの行で一番小さい要素にだけ着目してやれば良い。それを(i,j)だと思って、別の行から(k,l)を拾ってくる。(こいつも最小のを拾っておく。)で、(i,l)を全パターンチェックしてやる。このときに、i行目とk行目について、全部の要素が埋められる。(最小のペアでやっているので、他の組で負の要素は絶対に出てこない。)これを繰り返していくと、全部の行と列が埋まる。

これだけだと重たいかも知れないので、今の行数と、これまで出てきた最小の値を状態にメモしてやる。

ちなみに、同じ要素が埋まっている行がたくさんあって、後からもっと小さいのが出てくるとめんどくさいので、最初に一番小さい要素が上に来るようにソートしてやるなり、重複する行を削っておくなりしておくと便利。

1000

一列に並んでいる2N個の点を二つずつペアにして半円で結んでやりたい。いくつかペアはできているので、残りのペアを適当に作ったときに半円が重ならないようにできるか答えよ、という問題。

二部グラフではないけれど、最大マッチングで解けるんじゃないの？と思ったのでライブラリないから諦めた。