2012-02-25

Codeforces 109 Div2

12:09 |

ooox-

Rank 109

Rate 1594→1671

C. Hometask

12:09 |

文字列Sと、隣り合ってはいけない２つの文字(Ai,Bi)が何セットか与えられる。各Ai,Biで同じ文字は１回しか出てこない。

Sから最低何文字消せばいいか。

禁止文字が高々１回なので、ある (Ai,Bi) に関する制約を満たす操作をした後に新たに別の制約が破られるようにはならない。

たとえば (a,b)が禁止という条件で (ab以外) aかbの並び (ab以外) を処理する場合、(?,a), (?,b)という禁止セットはないことがわかっているので、

aかbの並びからどういう消し方をしても (ab以外)とaまたはbが隣接することになるので、この部分に関してはほかの条件を満たしている。

ということで連鎖しないことがわかったので、禁止文字セットは１回ずつ処理するだけでいい。

(ab以外) aかbの並び (ab以外) を処理するには、aかbの並びを全てaかbにするしかないので、aとbで文字数の少ない方を消せばいい。（実際には消さないで数えるだけでOK）

というわけで O(Sの長さ*制約の数) で処理できる。

int main() {
	string s;
	cin>>s;
	int N;
	cin>>N;
	int ans=0;
	REP(i, N) {
		string ng;
		cin>>ng;
		char a=ng[0];
		char b=ng[1];
		
		REP(i, s.size()) {
			int ca=0, cb=0;
			for(;i<s.size();i++) {
				if(s[i]!=a && s[i]!=b) break;
				ca+=s[i]==a;
				cb+=s[i]==b;
			}
			ans += min(ca, cb);
		}
	}
	cout<<ans<<endl;
	
	return 0;
}

D. Colliders

12:09 |

1〜N(in [1, 10**5]) を ON か OFF にする依頼が最大 10**5 個来るので、ON になっている全ての数字が互いに素（最大公約数が１）になるように依頼を処理する問題。

すでにONまたはOFFになってたら Already on/off, ONにできないときは Conflict with ?(これがONだからONにできないという数字), 処理した場合は Success と出す。

普通にやると O(N**2) になってだめなので、ON になってる約数を map なり vector なりで管理する。Nの約数の数は(ループがsqrtN回なので) N**0.5 のオーダーなので O(N**1.5) になる。

（約数としたけどほんとは素因数で書くべきだったか。）

「約数 1 は ON になっていても conflict にしない」という処理の一部が抜けてて40分ほどずっと pretest wrong answer の原因がわからず、TLEを疑って cinをscanfに変えたりしながら７回ほど submit したが結局最後まで気づかなかった。。

（そういえばpretestでもかかった時間とメモリ量はわかるのだから、TLEじゃないことはわかったのか）

惜しくないよりはマシだけど、なんか詰めが甘い。

↓ Accepted on practice

int main() {
	int N,M;
	cin>>N>>M;
	//map<int, int> pst;
	vector<int> pst(N+1);
	vector<char> st(N);
	//scanf("\n");
	REP(i, M) {
		char si;
		int k=0;
		//scanf("%c", &si);
		//scanf("%d", &k);
		//scanf("\n");
		cin>>si>>k;
		//cout<<"------ "<<si<<" "<<k<<endl;
		if(si=='-') {
			if(st[k-1]==0) {
				cout<<"Already off"<<endl;
			} else {
				for(int v=1;v*v<=k;v++) {
					if(k%v==0) {
						pst[v]=0;
						pst[k/v]=0;
					}
				}
				cout<<"Success"<<endl;
				st[k-1]=0;
			}
		} else {
			if(st[k-1]==1) {
				cout<<"Already on"<<endl;
			} else {
				int ok=1;
				for(int v=1;v*v<=k;v++) {
					if(k%v==0) {
						if((v!=1 && pst[v]) || (k/v!=1 && pst[k/v])) {
							ok=0;
							//cout<<"Conflict with "<<pst[v]?pst[v]:pst[k/v])<<endl;          // NG
							cout<<"Conflict with "<<((v!=1 && pst[v])?pst[v]:pst[k/v])<<endl; // OK
							break;
						}
					}
				}
				if(ok) {
					for(int v=1;v*v<=k;v++) {
						if(k%v==0) {
							pst[v]=k;
							pst[k/v]=k;
						}
					}
					cout<<"Success"<<endl;
					st[k-1]=1;
				}
			}
		}
	}
	
	return 0;
}

kojingharangの日記

2012-02-25

Codeforces 109 Div2

C. Hometask

D. Colliders