AtCoder ARC #022 : A - スーパーICT高校生、B - 細長いお菓子

ARC022に参加。
AはFirst Answerを取るなど好調な出だし。
ABCをノーミスで突破し、Dの30ptをさっさと取ってそこそこの順位で終わった。
Dは60ptまで頑張りたかったが、これは思いつかなかったのでしょうがないな。
http://arc022.contest.atcoder.jp/tasks/arc022_1
http://arc022.contest.atcoder.jp/tasks/arc022_2

A - スーパーICT高校生

N文字の文字列が与えられる。
これらの一部の文字を取り除き、"ICT"という文字列を生成できるか。
ただし大文字小文字は区別しない。

状態遷移をI→C→T→Goalの順で進めるだけ。O(N)で処理できる。
他に3重ループで総当たりしたり、正規表現を使う手もある。

void solve() {
	int f,i,j,k,l,x,y;
	string S;
	cin>>S;
	x=0;
	ITR(it,S) {
		if(x==0 && (*it=='i' || *it=='I')) x++;
		if(x==1 && (*it=='c' || *it=='C')) x++;
		if(x==2 && (*it=='t' || *it=='T')) x++;
	}
	if(x==3) _P("YES\n");
	else _P("NO\n");

}

B - 細長いお菓子

N要素の数列A[i]が与えられる。
この数列から、得られる連続した部分列のうち、同じ値を複数含まない部分列の最長の長さを答えよ。

数列要素を端から見ていく。
A[j]を答えの部分列に入れようとした場合、同じ値が出てくる前の位置i以前の要素は含めることはできない。
この事実から、各要素について直前に出てきた位置を覚えておき「これより以前の要素は含められない」という位置の最大値を更新して行けばよい。

int N;
int A[100001];
int pre[100001];
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	int ret=0;
	MINUS(pre);
	x=-1;
	FOR(i,N) {
		x=max(pre[A[i]]+1,x);
		pre[A[i]]=i;
		ret=max(ret,i-x+1);
	}
	cout << ret << endl;
}

まとめ

Bは1ずれそうで怖かったけど、何とか1発正解できた。