読者です 読者をやめる 読者になる 読者になる

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すら通らなかった...のでソース省略します。
前に動いたのを状態で持つらしい。。

とりあえず結果を待ちます。