AOJ 0270 モジュロ・クエリ
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270
解法
去年のパソコン甲子園の問題。去年の本選のとき解けなかった。
解説にのっているやり方とはちょっと違うやり方でやった。
アルゴリズムは解説のものより log N 倍ぐらい遅いはずだが通った。
二分探索であまりの区切りを見つけて最大のものを見つける。
#include <cstdio> #include <algorithm> using namespace std; int N, Q; int c[300000]; int main(){ scanf("%d %d", &N, &Q); for(int i = 0; i < N; i++) scanf("%d", &c[i]); sort(c, c + N); for(int i = 0; i < Q; i++){ int q; int ans = -1; scanf("%d", &q); for(int j = 0; j <= 300000; j += q){ int idx = distance(c, lower_bound(c, c + N, j)) - 1; if(idx < 0) continue; if(j - q <= c[idx]){ ans = max(ans, c[idx] - (j - q)); } } printf("%d\n", ans); } return 0; }