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

Codeforces Round #167 (Div. 2)

今日は鉄緑会という塾の校内模試がありました.
鬱になったので出れなかった回のを解きました.

solved5outof5になると緑になるらしくて達成感が少し
a. やる

int n, s, ret;

int main(){
    cin >> n;
    rep(i, n){ int tmp; cin >> tmp; s += tmp; }
    FOR(i, 1, 6) if((s + i) % (n + 1) != 1) ++ret;
    cout << ret << endl;
}

b. 眺めるとbitcountだ!!!となって適当に処理.

int n, seq[100010];
ll ans;
int de[50];

int main(){
    cin >> n;
    rep(i, n) cin >> seq[i];
    rep(i, n) ++de[__builtin_popcount(seq[i])];
    rep(i, 50) if(de[i]) ans += (ll)(de[i]) * (ll)(de[i] - 1) / 2LL;
    cout << ans << endl;
    return 0;
}

c. 図を見る. 劣化テトリスやん. 要らないのになぜかsegtreeを書く

#define sz (1 << 17)
int n, m;
int a[100010];

struct segtree{
    ll dat[1 << 18];

    void init(){
	rep(i, sz * 2 - 1) dat[i] = 0;
    }

    void update(int k, ll x){
	k += sz - 1;
	dat[k] = x;
	while(k > 0){
	    k = (k - 1) / 2;
	    dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
	}
    }

    ll query(int a, int b, int k = 0, int l = 0, int r = sz){
	if(r <= a || b <= l) return 0;
	if(a <= l && r <= b) return dat[k];
	return max(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
    }
}seg;

int main(){
    cin >> n;
    seg.init();
    rep(i, n){
	cin >> a[i];
	seg.update(i, (ll)a[i]);
    }
    cin >> m;
    rep(i, m){
	int w, h;
	cin >> w >> h;
	ll mi = seg.query(0, w);
	cout << mi << endl;
	seg.update(0, mi + (ll)h);
    }

    return 0;
}

d. Cです. 見るとx座標はsortされた状態になるので、適当に組み合わせを計算

int n;
P a[200010];
ll comb[200010][3];
ll m;
ll ret = 1LL;
vector<int> xs;
map<int, int> una;
map<int, int> cnt[200010];

int main(){
    cin >> n;
    rep(i, n) a[i].se = a[n + i].se = i;
    rep(i, n){
	cin >> a[i].fi;
	xs.pb(a[i].fi);
    }
    rep(i, n){
	cin >> a[n + i].fi;
	xs.pb(a[n + i].fi);
    }
    cin >> m;
    sort(ALL(xs));
    xs.erase(unique(ALL(xs)), xs.end());
    rep(i, xs.size()) una[xs[i]] = i;
    rep(i, n * 2) cnt[una[a[i].fi]][a[i].se]++;
    rep(i, 200010){
	comb[i][0] = 1LL;
	comb[i][1] = (ll)i % m;
	comb[i+1][2] = (comb[i][2] + comb[i][1]) % m;
    }
    rep(i, xs.size()){
	int sum = 0;
	foreach(cnt[i], itr) sum += itr->second;
	foreach(cnt[i], itr){
	    ret = ret * comb[sum][itr->second] % m;
	    sum -= itr->second;
	}
    }
    cout << ret << endl;
    return 0;
}

e. アカン頂点を順番に処理すればそのうち完成. -1実はならないんだよね

int n, m;
vector<int> g[300010];
bool col[300010];
vector<int> que;

inline bool ct(int v){
    int ret = 0;
    rep(i, g[v].size()) if(col[v] == col[g[v][i]]) ++ret;
    return ret >= 2;
}

int main(){
    cin >> n >> m;
    rep(i, m){
	int a, b;
	cin >> a >> b;
	--a; --b;
	g[a].pb(b); g[b].pb(a);
    }
    while(true){
	bool flag = false;
	rep(i, n){
	    if(ct(i)){
		col[i] ^= 1;
		flag = true;
	    }
	}
	if(!flag){
	    rep(i, n) cout << col[i] ? '0' : '1';
	    cout << endl;
	    return 0;
	}
    }
    return 0;
}