https://beta.atcoder.jp/contests/arc091/tasks/arc091_a
速さが足りない。
C
はい。
ll N, M; void solve() { cin >> N >> M; if(N > M) swap(N, M); if(N == 1) { if(M == 1) cout << "1\n"; else if(M == 2) cout << "0\n"; else cout << M - 2 << "\n"; } else if(N == 2) { cout << "0\n"; } else cout << (N - 2) * (M - 2) << "\n"; }
D
こういうの速くかけないとなぁ。
ll N, K; void solve() { cin >> N >> K; if(K == 0) { cout << N * N << "\n"; return; } ll res = 0; rep(b, K + 1, N + 1) { ll to = N / b; int a = 0; res += to * (b - K); a += to * (b - K); res += max(0LL, N - (to * b + K - 1)); a += max(0LL, N - (to * b + K - 1)); // debug(b, a, to); } cout << res << "\n"; }
E
いい感じの必要条件が思いつかなかったので発見的にときました。証明もしてないですけどまあ通るだろうということで。
なんでこれ爆速で解けるんだ…
int N, A, B; int ans[MAX_N]; void solve() { cin >> N >> A >> B; if(N == 1) { if(A == 1 && B == 1) { cout << 1 << "\n"; } else cout << "-1\n"; return; } bool swaped = false; if(A < B) { swap(A, B); swaped = true; } vector<int> cnt(B, 1); int n = N; if((N + A - 1) / A > B) { cout << "-1\n"; return; } rep(i, 0, (N + A - 1) / A) { cnt[i] = min(A, n); n -= A; } int r = B - (N + A - 1) / A; rep(i, 1, (N + A - 1) / A) { if(cnt[i] - 1 >= r) { cnt[i] -= r; r = 0; } else { cnt[i] = 1; r -= (cnt[i] - 1); } } if(r != 0) { cout << "-1\n"; return; } int at = 0; int from = N - 1; rep(i, 0, B) { rep(j, 0, cnt[i]) { ans[at] = from - cnt[i] + j + 1; at++; } from -= cnt[i]; } if(swaped) reverse(ans, ans + N); rep(i, 0, N) { cout << ans[i] + 1 << " "; } cout << "\n"; }
F
grundyの高速化って眺めることしかないし、適当にプログラム書いて眺めたんですけどよくわかんなかったです。でも手で書いたらわかったので、計算量大丈夫か勘定してACしました。
int grundy1(ll A, ll K) { if(A < K) return 0; if(A % K == 0) return A / K; else return grundy1(A - A / K - 1, K); } int grundy2(ll A, ll K) { if(A < K) return 0; if(A % K == 0) return A / K; else { ll m = A / K; ll to = m * K; return grundy2(A - ((A - to + m) / (m + 1)) * (m + 1), K); } } void solve() { ll N; cin >> N; ll res = 0; rep(i, 0, N) { ll A, K; cin >> A >> K; if(K <= 10000) res ^= grundy1(A, K); else res ^= grundy2(A, K); } if(res != 0) cout << "Takahashi\n"; else cout << "Aoki\n"; }