FFTはどうかと思う。代替案があればいいのだが。
250
等間隔に並んだ棒の高さが配列で与えられる。棒の頂点から見える他の棒の頂点の数の最大値を答えよ、という問題。
intが溢れるので、longで計算しましょうという問題。割り算は怖いから掛け算にして解くようにしている。
500
500x500程度の盤面が与えられるので、左上から右下まで移動するときに、必要な90度回転回数を答えよという問題。
単純にBFSするだけ。同じ点を二度計算しないように注意すれば何の問題もない。
1000
二つのベクトルが与えられる。それぞれ任意にrotateして得られる内積のうち、最大値を答えよ、という問題。
一方のベクトルを二つくっつけて、他方のベクトルを反転して、みたいにすると乗算の筆算を縦にみると、内積が出てくるので、うまいこと高速に計算してくれる方法を適用すればいいらしい。どっちもダメだ。
