Hackerrank 101 Hack Jan 2016 Average Modulo
本番では解けず。簡単ではないが、解けるべき問題。
Average Modulo
問題
数列$a$がある。整数$p,k$が指定される。長さ$k$以上の区間$[l,r)$で、$\frac{\Sigma_{l \le i \lt r} a_i \pmod{p}}{r - l}$を考え、この最大値を有理数として出力せよ。
解法
区間の長さが$2k$未満と分かるので、これを全部試して$O(nk)$。
区間$I$の長さが$2k$であるとする。長さ$k$の区間$I_x,I_y$に分割できる。 $s(I) = \Sigma_{i \in I} a_i$として、$\frac{s(I)}{2k} = \frac{s(I_x) + s(I_y)}{k + k} \le {\rm max} \{ \frac{s(I_x)}{k}, \frac{s(I_y)}{k} \}$となる。$s$を$s’(I) = s(I) \bmod p$で置き換えてもこれは変わらないため、区間の長さは$2k$未満となる。
実装
#include <iostream>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
typedef long long ll;
using namespace std;
ll gcd(ll a, ll b) {
if (b <= a) swap(a,b);
while (a) { ll c = a; a = b % c; b = c; }
return b;
}
void solve() {
ll n, mod, k; cin >> n >> mod >> k;
vector<ll> a(n); repeat (i,n) cin >> a[i];
ll p = 0, q = 1;
vector<ll> dp(2*k);
repeat (i,n) {
repeat_reverse (j,2*k-1) dp[j+1] = (dp[j] + a[i]) % mod;
repeat_from (j,k,2*k) {
if (p*(j) < dp[j]*q) {
p = dp[j];
q = j;
ll t = gcd(p,q);
p /= t;
q /= t;
}
}
}
cout << p << ' ' << q << endl;
}
int main() {
int t; cin >> t;
repeat (i,t) solve();
return 0;
}