izumo’s diary

主に競プロの精進記録

AtCoder Beginner Contest 098

だいぶ間が空きましたが今回はABC098の参加記です。結果はA, B, Cの3完で緑パフォでした。ちなみに前回のAGCはno-submissionで逃げました。(は?)
使用言語: C++

A - Add Sub Mul

問題

A-B, A\times{B}の大きい方とA+Bを比較すれば3つの中で最大のものが分かる。

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b;
	cin>>a>>b;
        // 実はmax({a+b, a-b, a*b})でもよい
	cout<<max(a+b, max(a-b, a*b))<<'\n';
	return 0;
}

B - Cut and Count

問題

N\leq{100}なので1\leq{|X|}\leq{N-1}X, Yについて全探索して十分間に合う。
X, Yを固定したとき共通する文字を調べるために、X, Yにそれぞれどのアルファベットが含まれるかを配列a, bに入れる。そしてa, bを調べることで共通する文字の種類数を数える。

配列の添え字ミスでかなりの時間を浪費してしまった。注意しているつもりなのだが……

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)

bool a[30], b[30];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	string s;
	cin>>n>>s;
	int ans=0;
	REP(i, n-1){
		REP(j, 26){
			a[j]=false;
			b[j]=false;
		}
		int tmp=0;
                // アルファベットを数値に置き換えつつ含まれる文字を配列に入力する
                // 例:'b'-'a'=1, 'z'-'a'=25
		REP(j, i+1) a[s[j]-'a']=true;
		FOR(j, i+1, n) b[s[j]-'a']=true;
		REP(j, 26){
			if(a[j] && b[j]) ++tmp;
		}
		ans=max(ans, tmp);
	}
	cout<<ans<<'\n';
	return 0;
}

C - Attention

問題

愚直にi番目の人をリーダーに選びそれぞれについて向く方向を変える人数を数えるのはO(N^2)となり間に合わない。
累積和を使う方法を思いついたのでそれを実装した。i番目までの人のうち東を向いている人数をa_{i+1}, 西を向いている人数をb_{i+1}とすると、i番目の人をリーダーに選んだとき向きを変える人数はb_i+a_N-a_{i+1}で求められる。

実は累積和を使わずにi番目がEなら-1, Wなら+1し、最小となるiをリーダーにすればよい。これは気付くべきだった。

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0; i<(n); ++i)

int a[364364], b[364364];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	string s;
	cin>>n>>s;
	REP(i, n){
		if(s[i]=='E'){
			a[i+1]=a[i]+1;
			b[i+1]=b[i];
		}
		else{
			a[i+1]=a[i];
			b[i+1]=b[i]+1;
		}
	}
	int ans=1<<30;
	REP(i, n){
		int e=a[n]-a[i+1];
		ans=min(ans, e+b[i]);
	}
	cout<<ans<<'\n';
	return 0;
}

D - Xor Sum 2

問題

まずコンテスト中に考えたことを書く。
当然のことながら愚直にl, rを全探索しても間に合わない。少し考えるとXORに桁上がりがないため、a_i xor a_j\leq{a_i+a_j}と分かる。よって二進数表記したときにa_lからa_rはどの桁についてもビットが重なっていないことが条件になる。
この条件を満たすl, rrを一つずつ増やしlを二分探索するとO(N\log N)で求められる(はず)。が、実装終わらず。

コンテスト後に尺取り法なるものを知る。蟻本に載っているようなのでそれを見つつ実装した。
lを一つずつ増やし条件を満たすrを見つける。rlごとに初期化するわけではないのでO(N)で求められる。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(int i=0; i<(n); ++i)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, a[252525];
	cin>>n;
	REP(i, n) cin>>a[i];
	ll ans=0;
	for(int l=0, r=0, bit=0; l<n; ++l){
		while(r<n && (bit&a[r])==0) bit|=a[r++];
		ans+=r-l;
		bit^=a[l];
	}
	cout<<ans<<'\n';
	return 0;
}



早く緑になりたい。
f:id:izumo27:20180529171607p:plain