読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #395 (Div. 1) C. Timofey and remoduling

http://codeforces.com/contest/763/problem/C

問題概要

n 個の数が与えられる。これを並び替えて mod m 上での等差数列にできるかどうか判定せよ。可能なら初項と公差を示せ。

解法

等差数列の総和は  n\times (a_1+a_n)/2 で計算できる。このことを使うと、初項を決め打ちすれば  a_n が何であるかを求められる。a_n が何であるかが分かれば公差 d も求められる。

このようにすることで初項、公差の候補がたかだか n 個得られる。ある組み合わせに対して正しいかどうかを判定するには、愚直にやると O(n \log n) 程度かかる(set を使えば)。

やりたいことは  \{a_1,a_2,\ldots,a_n\}\{a,a+d,a+2d,\ldots,a+(n-1)d\} が集合の意味で一致するかどうかを判定することである。等価比較であればハッシュは使えないだろうか?

等差数列の長さ・初項・公差の情報だけから高速に計算できるようなものでないと役に立たない。色々考えた結果、等差数列の二乗和はそこそこ良さそうなハッシュだと判断した。実際、これで通る。

n=1,n=m のケースに注意。