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

kmjp's blog

競技プログラミング参加記です

AtCoder ARC #035 : A - 高橋くんと回文、B - アットコーダー王国のコンテスト事情

ARC

ARCに参加。一応全完したがCでしょうもないミスをしてレート微減。
http://arc035.contest.atcoder.jp/tasks/arc035_a
http://arc035.contest.atcoder.jp/tasks/arc035_b

A - 高橋くんと回文

文字列Sが与えられる。
一部の文字は穴が開いている。
このSが回文で有りうるか答えよ。

S[i]!=S[|S|-1-i]かつS[i]もS[|S|-1-i]も穴で無い場合、回文にならない。

string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	bool ok=true;
	cin>>S;
	FOR(i,S.size()) {
		if(S[i]=='*') continue;
		if(S[S.size()-1-i]=='*') continue;
		if(S[i]!=S[S.size()-1-i]) ok=false;
	}
	if(ok) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}

B - アットコーダー王国のコンテスト事情

N問の問題があり、各問題を解くのにかかる時間はT[i]である。
問題は任意の順で1問ずつ解いていくことができる。
問題を解いたとき、そこまでにかかった総時間がペナルティとなる。
各問題の総ペナルティの最小値と、そのペナルティとなる問題の解答順の組み合わせを答えよ。

i番目に解いた問題の時間は(N+1-i)掛けた分が総ペナルティに加算される。
よって問題を解く順は、時間が短い順である。
また、組み合わせは同じ時間の問題がx個あるごとにx!を掛けて求められる。

int N;
ll T[101000],fact[10100];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) cin>>T[i];
	sort(T,T+N);
	
	ll tot=0,S=0;
	FOR(i,N) S+=T[i], tot+=S;
	fact[0]=1;
	FOR(i,N) fact[i+1]=fact[i]*(i+1)%mo;
	ll pat=1,suc=1;
	for(i=1;i<N;i++) {
		if(T[i]!=T[i-1]) {
			pat = pat*fact[suc]%mo;
			suc=0;
		}
		suc++;
	}
	pat = pat*fact[suc]%mo;
	
	cout<<tot<<endl;
	cout<<pat<<endl;

}

まとめ

A問題、ローカルテスト中"***"がシェルでファイル名に置換されて"NO"判定されてしまい、無駄に迷った…。

広告を非表示にする