AGC004
AtCoder Grand Contest 004 - AtCoder Grand Contest 004 | AtCoder
A,Bはすぐ解けたんですが、結局その後一問も解けず……。
公式の解説があるコンテストなのでメモ書き程度に。
A
図を見てるとなんかわかる。
#include <bits/stdc++.h> using namespace std; const int INF = 1000000000; #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i) #define rep(i,n) REP(i, 0, n) typedef long long int i64; typedef pair<int, int> pint; int main() { i64 a[3]; rep(i, 3) cin >> a[i]; rep(i, 3) { if(a[i] % 2 == 0) { cout << 0 << endl; return 0; } } i64 mi = 1.0e18 + 1LL; rep(i, 3) rep(j, 3) { if(i == j) continue; mi = min(mi, a[i] * a[j]); } cout << mi << endl; return 0; }
B
dp[i][j] := j回移動させたときのiまでの合計の最小 で解きました。
以下テンプレ略。
i64 dp[2001][2001]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; i64 x; cin >> N >> x; vector<i64> a(N); rep(i, N) cin >> a[i]; i64 sum = 0; rep(j, N) { dp[0][j] += sum; sum += x; } rep(i, N) { i64 mi = 1.0e16; rep(j, N) { mi = min(mi, a[(i + j) % N]); dp[i + 1][j] = dp[i][j] + mi; } } i64 ans = 1.0e16; rep(j, N) ans = min(ans, dp[N][j]); cout << ans << endl; return 0; }
C
これは……
無理。
int main() { cin.tie(0); ios::sync_with_stdio(false); int H, W; cin >> H >> W; vector<string> fld(H); rep(i, H) cin >> fld[i]; auto red = fld, blue = fld; { string k = string(W - 1, '#') + '.'; rep(i, H) { red[i][0] = '#'; if(i % 2 == 0) red[i] = k; } } { string k = '.' + string(W - 1, '#'); rep(i, H) { blue[i][W - 1] = '#'; if(i % 2) blue[i] = k; } } rep(i, H) cout << red[i] << '\n'; cout << '\n'; rep(i, H) cout << blue[i] << '\n'; return 0; }
面白いとは思うんですけどどうやっても思いつく気がしません……。
D
Kより長くなりそうなら先頭に繋ぎ変えればいいんですけど、このとき「なるべく前で(根に近い方で)切りたい」というのがなかなか実装できず。
int N, K; vector<int> G[100000]; int ans; int dfs(int cur_v, int p) { int res = 0; for(int nv : G[cur_v]) res = max(res, dfs(nv, cur_v) + 1); if(res == K - 1 && p != 0) { ++ans; res = -1; } return res; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> K; ans = 0; rep(i, N) { int p; cin >> p; --p; if(i == 0) { if(p != 0) ++ans; continue; } G[p].emplace_back(i); } dfs(0, 0); cout << ans << endl; return 0; }