AtCoder Beginner Contest 098

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

A - Add Sub Mul

問題

の大きい方とを比較すれば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

問題

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

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

#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

問題

愚直に番目の人をリーダーに選びそれぞれについて向く方向を変える人数を数えるのはとなり間に合わない。
累積和を使う方法を思いついたのでそれを実装した。番目までの人のうち東を向いている人数を, 西を向いている人数をとすると、番目の人をリーダーに選んだとき向きを変える人数はで求められる。

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

#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

問題

まずコンテスト中に考えたことを書く。
当然のことながら愚直にを全探索しても間に合わない。少し考えるとXORに桁上がりがないため、 と分かる。よって二進数表記したときにからはどの桁についてもビットが重なっていないことが条件になる。
この条件を満たすをを一つずつ増やしを二分探索するとで求められる（はず）。が、実装終わらず。

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

#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;
}

早く緑になりたい。