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"判定されてしまい、無駄に迷った…。