JOI予選 2012-2013
予選敗退。5,6に2時間使ったのに...................5番typo....................................これ落ちたな(確信)
マクロとかあれなので省略します
1.やる
int l, a, b, c, d; int main(){ scanf("%d %d %d %d %d", &l, &a, &b, &c, &d); printf("%d\n", l - max((a + c - 1)/ c, (b + d - 1) / d)); return 0; }
2.やる
int n; int ct[110]; int ans[210]; int m[210][3]; int main(){ scanf("%d", &n); rep(i, n) rep(j, 3) scanf("%d", &m[i][j]); rep(i, 3){ memset(ct, 0, sizeof(ct)); rep(j, n) ct[m[j][i]]++; rep(j, n){ if(ct[m[j][i]] == 1) ans[j] += m[j][i]; } } rep(i, n) printf("%d\n", ans[i]); return 0; }
3.探索頑張る
int n, ans, len; string s; string g[110]; int main(){ scanf("%d", &n); cin >> s; len = (int)s.size(); rep(i, n) cin >> g[i]; rep(i, n){ int k = 0; bool f = false; int gl = (int)g[i].size(); while(true){ int nl = len + k * (len - 1); if(nl > gl) break; rep(j, gl - nl + 1){ bool tmp = true; if(g[i][j] != s[0]) continue; int l = j; for(int pos = 0; pos < len; pos++){ if(s[pos] != g[i][l]){ tmp = false; break; } l += k + 1; } if(tmp){ f = true; break; } } if(f) break; k++; } if(f) ans++; } printf("%d\n", ans); return 0; }
4. DP
int d, n, ans; int t[210]; vector<P> day[210]; int dp[210][210]; int dr[210]; int main(){ scanf("%d %d", &d, &n); rep(i, d) scanf("%d", &t[i]); rep(i, n){ int a, b, c; scanf("%d %d %d", &a, &b, &c); rep(j, d){ if(t[j] >= a && t[j] <= b){ day[j + 1].pb(P(c, i + 1)); } } dr[i + 1] = c; } /* rep(i, d + 1){ rep(j, day[i].size()) printf("%d ", day[i][j].se); printf("\n"); } */ rep(i , d + 1){ rep(j, n + 1){ dp[i][j] = -INT_MAX; } } rep(i, day[1].size()) dp[1][day[1][i].se] = 0; for(int i = 2; i <= d; i++){ for(int j = 0; j < day[i].size(); j++){ int idx = day[i][j].se; int cost = day[i][j].fi; for(int k = 1; k <= n; k++){ int tmp = -INT_MAX; if(dp[i - 1][k] != -INT_MAX){ tmp = dp[i - 1][k] + abs(dr[k] - cost); } dp[i][idx] = max(dp[i][idx], tmp); } } } for(int i = 1; i <= n; i++) ans = max(ans, dp[d][i]); /* for(int i = 1; i <= d; i++){ for(int j = 1; j <= n; j++){ printf("%d ", dp[i][j]); } printf("\n"); } */ printf("%d\n", ans); return 0; }
5.typoに気付かず苦戦。難しくなっている・・・終了後に直したコード
int n, k; ll ans; int x1[60], yy1[60], d1[60], x2[60], y2[60], d2[60]; int nx1[60], ny1[60], nd1[60], nx2[60], ny2[60], nd2[60]; vector<int> x, y, d; map<int, int> xe, ye, de; int s[100][100][100]; int main(){ scanf("%d %d", &n, &k); rep(i, n){ scanf("%d %d %d %d %d %d", &x1[i], &yy1[i], &d1[i], &x2[i], &y2[i], &d2[i]); x.pb(x1[i]); x.pb(x2[i]); y.pb(yy1[i]); y.pb(y2[i]); d.pb(d1[i]); d.pb(d2[i]); } sort(x.begin(), x.end()); sort(y.begin(), y.end()); sort(d.begin(), d.end()); rep(i, (int)x.size()) xe[x[i]] = i; rep(i, (int)y.size()) ye[y[i]] = i; rep(i, (int)d.size()) de[d[i]] = i; rep(i, n){ for(int j = xe[x1[i]]; j < xe[x2[i]]; j++){ for(int l = ye[yy1[i]]; l < ye[y2[i]]; l++){ for(int m = de[d1[i]]; m < de[d2[i]]; m++){ s[j][l][m]++; } } } } rep(i, x.size()){ rep(j, y.size()){ rep(l, d.size()){ if(s[i][j][l] >= k){ ans += (x[i + 1] - x[i]) * (y[j + 1] - y[j]) * (d[l + 1] - d[l]); } } } } printf("%lld\n", ans); return 0; }
6. 部分点取ろうとしたけどsampleすら通らなかった...のでソース省略します。
前に動いたのを状態で持つらしい。。
とりあえず結果を待ちます。