319.1

比較的順当なセット。良くできている気がする。

250

2列に並んでいる全部で20個の席のうち、座れるかどうかが与えられる。3人で座るとき、距離の和の最小値を答えよ、という問題。

探索するだけ。

500

1からNまでの相異なる値を挿入してできた二分探索木の形状が与えられる。このとき、考えられる挿入順は何通りか答えよ、という問題。

あるノードについて、左側の部分木と右側の部分木の挿入順は任意に混合できる。つまり左の木にLノード、右の木にRノードあれば、L+RからL個を選ぶのと同じだけ並び替えが可能。また、それに加えて、各木の内部での並び替えが可能なので、これを再帰的にやる。つまり、各ノードについて、LとRを計算して、コンビネーションを積算していけば良い。

1000

マンハッタン距離が最長になる二点を選択せよ、という問題。

点数が大きいので全探索は無理。マンハッタン距離の式はabs(Xi-Xj)+abs(Yi-Yj)で、これを良く考えると、max(abs(Xi-Xj+Yi-Yj),abs(Xi-Xj-Yi+Yj))になる。つまりXi+YiまたはXi-Yiについて考えれば良い。Xi+Yiでソートして最小値と最大値になる二点と、Xi-Yiでソートして最小値と最大値になる二点のうち、値が大きい方がマンハッタン距離で最大になる。(実際には同じ値になるものを一通り調べる必要があるが、既にソートされているので、すべての点を順番に調べるだけで良い。)

最大値と最小値が欲しいだけなので、ソートする必要もないし、更にいうと、一番小さいインデックスが必要で順番に調べるので、ますますソートする必要がない感じ...。