とりあえず

PKU
  1. PKU 2738 Two Ends
  2. PKU 2734 Queens, Knights and Pawns
  3. PKU 2737 Swamp Things

37問。

PKU 2738 Two Ends

先手に最適な取り方を、後手に貪欲な取り方をさせてスコアの差を答にする。

最適な取り方は、ある範囲 p..q の中での最高スコアをメモしてメモ化探索する。カードに書かれた数列をCとして、ある範囲中の最高スコアを求める関数をmax_scoreとすると、p..qの中での最高スコアは Cp+1 >= Cqならば l0 = p+2, r0 = q と、そうでないなら l0 = p+1, r0 = q-1 とおいて、また Cp >= Cq-1ならば l1 = p+1, r1 = q-1 と、そうでないなら l1 = p, r1 = q-2 とおいたとき、 max(max_score(l0, r0) + Cp, max_score(l1, r1) + Cq) である。これはつまり、左からとった場合と右からとった場合、どちらが高いうスコアをとれるかということを計算している。

PKU 2734 Queens, Knights and Pawns

やるだけ。

PKU 2737 Swamp Things

点A, B, Cについて、ABを通る直線の傾きとACを通る直線の傾きが等しければ3点は同一直線上にあるということを利用する。

ある点iについて、iとi以外の点間の傾きをすべて計算し、等しい値の数を調べる。これを全てのiに対して行えばよい。

ある点iについてi以外の点との傾きの計算にO(N)時間かかり、等しい値の数を調べるためにソートするのでO(NlogN)時間必要である。実際に等しい値の数を調べるのは線形時間でできるので、あるひとつの点の乗っている直線の中でもっとも多くの点が乗っているものを調べるのにはO(NlogN)時間かかることになる。

これを全ての点に対して行うので最終的な計算量は O(N2logN) である。