299.1

簡単な550と論理パズルな1000の組み合わせ。(1000はマイクロソフトが大好きな問題。)

250

booleanの二次元配列について、ある行ないし列を見たときにどれか一つでもtrueならtrueで、そうでなければfalseという値がすべての行と列について与えられる。このとき配列全体におけるtrueの数の最大値と最小値を答えよ、という問題。

trueが存在している(存在できる)行の数と列の数が分かるので、少なくともmax(行,列)個は存在しないといけないし、高々行x列個しか置けない。

550

文字列を回文の和に分解するときの分解個数の最小値を答えよ、という問題。

A文字目からB文字とったときに回文かどうかをDPで求める。N文字目までにいくつの回文に分解できるかをDPするだけ。効率の良い実装をできるかどうかなだけなので、550はやり過ぎのように思う。

1000

N種類のものがそれぞれいくつあるか分かっている状況で、K人にそれぞれ1個ずつ配る。各人は他人に配られたものは分かるが、自分に配られたものは分からない。自分に配られたものが分かるかどうかを聞き、全員が同時に答えるという処理を行うとき、何回行えば誰かが自分に配られたものを知ることができるか答えよ、という問題。

残っている個数をM個とすると、最初に全員が分からないと答えたら、自分以外に配られたものでN-1種類消費された人がいないと分かる。という推論を繰り返し適用していく。どこかでユニークに求まる人が出るはず。これをちゃんとしたコードにすることができない...。適当にgreedyなのを書いて試してみたいので、明日やる。