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

Codeforces Round #171 (Div. 2)

期末が出来なさすぎて冷えきっています。
Div1復帰。Div1に残れる実力をつけなければ....

A. 初め問題文間違っていてimfだった 適当に実装. なんでAでこんな書いたんだ...

const int dx[] = {1,0,-1,0};
const int dy[] = {0,1,0,-1};
int x, y, k = 1, dir;
int ans;

int main(){
    cin >> x >> y;
    int a = 0, b = 0;
    while(a != x || b != y){
	rep(i, 2){
	    if(a == x && b == y){
		cout << ans << endl;
		return 0;
	    }
	    rep(j, k){
		if(a == x && b == y){
		    cout << ans << endl;
		    return 0;
		}
		a += dx[dir];
		b += dy[dir];
	    }
	    dir = (dir + 1) % 4;
	    if(a == x && b == y){
		cout << ans << endl;
		return 0;
	    }
	    ans++;
	}
	k++;
	rep(i, 2){
	    if(a == x && b == y){
		cout << ans << endl;
		return 0;
	    }
	    rep(j, k){
		if(a == x && b == y){
		    cout << ans << endl;
		    return 0;
		}

		a += dx[dir];
		b += dy[dir];
	    }
	    dir = (dir + 1) % 4;
	    if(a == x && b == y){
		cout << ans << endl;
		return 0;
	    }
	    ans++;
	}
	k++;
    }
    cout << ans << endl;
    return 0;
}

B. しゃくとりやるだけ

int n, t;
int a[100010];
int ans;

int main(){
    cin >> n >> t;
    rep(i, n) cin >> a[i];
    int s = 0, e = 0;
    int sum = 0;
    while(true){
	while(sum <= t - a[e] && e < n){
	    sum += a[e];
	    e++;
	}
	ans = max(ans, e - s);
	sum -= a[s];
	s++;
	if(e == n) break;
    }
    cout << ans << endl;
    return 0;
}

C. 区間の増減性を持つsegtreeを建てて適当に2分探索.

#define SZ (1 << 20)

int n, m;
int a[100010];

struct segtree{
    bool dat[SZ * 2];

    void init(){
	memset(dat, false, sizeof(dat));
    }

    inline void update(int k, bool fl){
	k += SZ - 1;
	dat[k] = fl;
	while(k > 0){
	    k = (k - 1) / 2;
	    dat[k] = dat[k * 2 + 1] && dat[k * 2 + 2];
	}
    }

    bool query(int a, int b, int k = 0, int l = 0, int r = SZ){
	if(r <= a || b <= l) return true;
	if(a <= l && r <= b) return dat[k];
	bool lc = query(a, b, k * 2 + 1, l, (l + r) / 2);
	bool rc = query(a, b, k * 2 + 2, (l + r) / 2, r);
	return lc && rc;
    }

};

segtree inc, de;

int main(){
    cin >> n >> m;
    rep(i, n) cin >> a[i];
    inc.init(); de.init();
    rep(i, n - 1){
	if(a[i] <= a[i + 1]) inc.update(i, true);
	if(a[i] >= a[i + 1]) de.update(i, true);
    }
    rep(i, m){
	int p, q;
	cin >> p >> q;
	--p; --q;
	int lb = p - 1, ub = q + 1;
	while(ub - lb > 1){
	    int mid = (ub + lb) / 2;
	    if(inc.query(p, mid)) lb = mid;
	    else ub = mid;
	}
	if(de.query(lb, q)) cout << "Yes" << endl;
	else cout << "No" << endl;
    }
    /*
    rep(i, n){
	for(int j = i; j < n; ++j){
	    int p = i;
	    int q = j;
	    cout << i  + 1 << " " << j + 1 << " ";
	    int lb = p - 1, ub = q + 1;
	    while(ub - lb > 1){
		int mid = (ub + lb) / 2;
		if(inc.query(p, mid)) lb = mid;
		else ub = mid;
	    }
	    cout << lb << " ";
	    if(de.query(lb, q)) cout << "Yes" << endl;
	    else cout << "No" << endl;
	}
    }
    */
    return 0;
}

D. 見てない。bitDPらしい。こわい
Eは既出らしいけど知らない。greedy