433.1

500に1時間かかったので、250に逃げたら15分ギリギリだった。かなり手強いセット。

250

文字列が複数与えられるので、それをPermutateして結合した文字列のうち、Rotateした時に自身に一致するインデックスの数がちょうどK個のものの数を求めよ、という問題。

全部試してKMPサーチとかいうのを使うと終わるらしい。そんなのは知らないので、先頭の文字列を固定してもいいことを利用して、文字列の数だけ高速化したのと、最初に一致したRotateが分かれば、それは再帰的に適用可能なのを利用してそこそこに高速化したので間に合ったっぽい。

500

NxMの矩形において、すべての頂点が格子点になるひし形はいくつあるか、という問題。

長さiのベクトルのうち、[0,PI)の角度をなすものの任意のペアについて、それを含む最小の矩形を求めてやれば、そのひし形がいくつあるか分かる。iは高々max(N,M)くらい。

1000

開いたら眠れなくなりそうなので、開いていない。