https://colopl2018-qual.contest.atcoder.jp/
久しぶりの投稿です。いろいろ忙しかった。
やっぱりコンテストだと結構焦ってまともに考えられないなぁ。
C
偶数は一緒に使えないので、すべて奇数or奇数+偶数1つという組み合わせしかありません。
あと、35以上の素数は考えなくて良くて、31までの計11コの素数で互いに素か判定できます。
ll A, B;
ll P[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
void solve() {
cin >> A >> B;
vl even, odd;
for(ll i = A; i <= B; i++) {
if(i % 2 == 0) even.pb(i);
else odd.pb(i);
}
int n = sz(odd);
int ans = 0;
rep(bit, 0, (1 << n)) {
vi cnt(11, 0);
bool found = false;
rep(i, 0, n) {
if(bit & (1 << i)) continue;
rep(j, 0, 11) {
ll p = P[j];
if(odd[i] % p == 0) {
if(cnt[j] != 0) {
found = true;
break;
}
else cnt[j]++;
}
}
if(found) break;
}
if(found) continue;
ans++;
rep(i, 0, sz(even)) {
bool ok = true;
rep(j, 0, 11) {
ll p = P[j];
if(even[i] % p == 0) {
if(cnt[j] != 0) {
ok = false;
break;
}
}
}
if(ok) ans++;
}
}
cout << ans << "\n";
}
D
まず、スタミナを消費するときはすべて消費すると考えていいです。
スタミナを時刻t1,t2...,tkで消費するとすれば、得られる知力はX+Σmax(X, ti-t(i-1))となります。
また、ti,t(i+1),t(i+2)について、t(i+2)-t(i)<=Xを満たす場合、t(i+1)は不要になります。
よってtiの次にスタミナを消費する時間はtl-ti>Xを初めて満たすｌを考えればtlまたはtl-1となります。
なのでO(N^2)でdpできます。
int N, X;
int A[5010];
ll dp[5010][5010];
int to[5010];
void solve() {
cin >> N >> X;
rep(i, 0, N) {
cin >> A[i];
}
rep(i, 0, N - 1) {
int ub = i;
while(A[ub + 1] - A[i] < X) {
ub++;
if(ub == N - 1) break;
}
to[i] = ub;
}
dp[0][1] = X;
rep(i, 0, N - 1) {
rep(k, 0, N) {
if(!dp[i][k]) continue;
MAX(dp[to[i]][k + 1], (dp[i][k] + A[to[i]] - A[i]));
if(to[i] != N - 1) {
MAX(dp[to[i] + 1][k + 1], (dp[i][k] + X));
}
}
}
ll ans = 0;
rep(k, 1, N + 1) {
rep(i, 0, N) {
MAX(ans, dp[i][k]);
}
cout << ans << "\n";
}
}
スライド最大値をすれば確かにやるだけなんですが、自信がなかったので考察してAC。
以下はスライド最大値バージョン
struct slidemax {
ll que[MAX_N];
int s, e;
void init() {
s = 0; e = 0;
}
void add(ll x) {
while(s < e && que[e - 1] < x) e--;
que[e++] = x;
}
void remove(ll x) {
if(s < e && que[s] == x) s++;
}
bool empty() {
return s == e;
}
ll get() {
if(s == e) return -linf;
else return que[s];
}
void show() {
debug(vi(que + s, que + e));
}
};
int N, X;
int T[5010];
ll dp[2][5010];
void solve() {
cin >> N >> X;
rep(i, 0, N) cin >> T[i];
rep(i, 0, N) dp[0][i] = X;
cout << X << "\n";
int now = 0, next = 1;
rep(k, 2, N + 1) {
ll ans = 0;
slidemax que;
que.init();
memset(dp[next], 0, sizeof(dp[next]));
int lv = -1;
rep(i, 0, N) {
while(lv + 1 < N && T[i] - T[lv + 1] > X) {
lv++;
que.remove(dp[now][lv] - T[lv]);
}
MAX(dp[next][i], que.get() + T[i]);
if(lv >= 0) MAX(dp[next][i], dp[now][lv] + X);
MAX(ans, dp[next][i]);
que.add(dp[now][i] - T[i]);
}
cout << ans << "\n";
swap(now, next);
}
}
ライブラリ化できちゃうんですね。範囲に新たに入った値をadd,範囲から出た値をremoveすれば区間の最小値が求まります。
E
網目状に線分を引いていきます。
網目の最小単位によって(n*n+2*n+2)コの領域を新たに作ることができます。
使う点も4n+4コになるので、5000コの制限をクリアできます。
最初実装したやつは網目同士が重なってしまってWAになりました。
アイディア自体はコンテスト中に思いついたけどやっぱり通せないですね。
int N;
vector<pi> ans;
void loop(int D, int at) {
int n = 0;
while((n + 2) * (n + 2) + 2 * (n + 2) + 2 <= D) n += 2;
if(n == 0) {
ans.pb(pi(at, at + 1));
ans.pb(pi(at + 2, at + 1));
if(D - 2 != 0) loop(D - 2, at + 2);
else ans.pb(pi(at + 2, at + 2));
ans.pb(pi(at + 1, at + 2));
ans.pb(pi(at + 1, at));
}
else {
rep(i, 0, n / 2) {
ans.pb(pi(at + i * 2, at + n + 1));
ans.pb(pi(at + i * 2 + 1, at + n + 1));
ans.pb(pi(at + i * 2 + 1, at - 1));
ans.pb(pi(at + i * 2 + 2, at - 1));
}
ans.pb(pi(at + n, at + n + 1));
ans.pb(pi(at + n + 2, at + n + 1));
int L = n * n + 2 * n + 2;
if(D - L != 0) loop(D - L, at + n + 2);
else ans.pb(pi(at + n + 2, at + n + 2));
ans.pb(pi(at + n + 1, at + n + 2));
ans.pb(pi(at + n + 1, at + n));
rer(i, (n / 2), 0) {
ans.pb(pi(at - 1, at + i * 2 + 2));
ans.pb(pi(at - 1, at + i * 2 + 1));
ans.pb(pi(at + n + 1, at + i * 2 + 1));
ans.pb(pi(at + n + 1, at + i * 2));
}
}
}
void solve() {
cin >> N;
if(N == 2) {
cout << 4 << "\n";
cout << 0 << " " << 0 << "\n";
cout << 0 << " " << 1 << "\n";
cout << 1 << " " << 1 << "\n";
cout << 1 << " " << 0 << "\n";
return;
}
if((N - 1) % 2 == 0) {
ans.pb(pi(0, 0));
loop(N - 1, 0);
}
else {
ans.pb(pi(0, 0));
ans.pb(pi(1, 0));
loop(N - 2, 1);
ans.pb(pi(0, 1));
}
cout << sz(ans) << "\n";
rep(i, 0, sz(ans)) {
cout << ans[i].fst << " " << ans[i].sec << "\n";
}
}
ジャッジはオイラーの多面体定理を使っているらしいですね。
想定解のほうがシンプルでいいですね。
