11/24 PKU - Algorithmer’s note

またまたひさしぶりのPKU

N*3の表があって、各行、列の数字の和が決まっている。それを満たすように各マスに非負整数を入れる方法は何通りあるか。

3つの列の和でDPしたいが、2つの列の和が定まればもう1つもすぐに定まることから2つの列の和でDPして大丈夫。

積んであるカードを配る。「一番上のを配る→P枚下に追いやる」を繰り返して配る。ディーラーの右隣から配って、反時計回りに回っていく。ディーラーはいいカードがほしいらしい。いいカードを何番目に入れたらいいか。

環状双方向リスト組んでやるだけ。