8/1 PKU
3419 Difference Is Beautiful
予め、perfect sequenceの左端を固定したときに右端をどこまで伸ばせるかを配列に持っておく。この操作はだいたいO(N)でできる。
各クエリーについて、ある点を境に「クエリーの右端まで達しない」「クエリーの右端で右端でつっかえる」が分かれるはずである。これは二分探索で求められる。
前者の場合の最長の長さは、Segment Treeを使うと求められる。後者の場合は、境界からクエリーの右端までである。これらのうち長い方を出力すればよい。
2858 Crabbles
ハッシュ法やるだけ
3400 Dropping the stones
DFSやるだけでTLEぎりぎりで通った
ショートコーディングやった。287バイト
2496 Military Recruit
Warshall-Floydやるだけ