Facebook Hacker Cup 2013 Qualification Round
Beautiful strings
やるだけ
void lower(string &s){ REP(i,s.size()){ if('A'<=s[i]&&s[i]<='Z')s[i] += 'a'-'A'; } } int main(){ int m; cin>>m; cin.ignore(); REP(i,m){ string s; getline(cin,s); lower(s); map<char,int> c; map<char,int>::reverse_iterator it; REP(j,s.size()){ if(s[j]<'a'||'z'<s[j])continue; ++c[s[j]]; } vector<int> v; for(it=c.rbegin();it!=c.rend();++it){ v.push_back(it->second); } sort(v.begin(),v.end(),greater<int>()); int ans=0,b=26; REP(j,v.size()){ ans += b*v[j]; b--; } cout<<"Case #"<<i+1<<": "<<ans<<endl; } return 0; }
Balanced Smileys
DPするだけ
bool dp[101][101]; int main(){ int m; cin>>m; cin.ignore(); REP(i,m){ memset(dp,false,sizeof(dp)); dp[0][0]=true; string s; bool colon=false; getline(cin,s); REP(j,s.size()){ if(s[j]=='('){//+1 for(int k=0;k<100;k++){ dp[j+1][k+1] = dp[j][k]; } }else if(s[j]==')'){//-1 for(int k=1;k<=100;k++){ dp[j+1][k-1] = dp[j][k]; } } if(s[j]!='('&&s[j]!=')'||colon){//0 for(int k=0;k<=100;k++){ dp[j+1][k] |= dp[j][k]; } } colon = s[j]==':'; } char *ans = dp[s.size()][0]?"YES":"NO"; cout<<"Case #"<<i+1<<": "<<ans<<endl; } return 0; }
Find the Min
最初のk個の後はk+1周期で同じのが続くのでそれらを計算。
setだと最初のk個で重複があると死ねるからk個前までに使われてるやつをmapで持っといた。
基本は0,1,2,・・・ってな風に小さい値から割り当てていくけど
添え字が進むことによって今見ている値よりも小さい値が使用可能になったらそっちを使う。
int main(){ int T; cin>>T; REP(i,T){ map<ull,int> m; vector<ull> v; vector<ull> cycle; ull n,k; ull a,b,c,r; cin>>n>>k; cin>>a>>b>>c>>r; ull val=a; REP(j,k){ v.push_back(val); ++m[val]; val =(b*val+c)%r; } ull cur=0; while(m.find(cur)!=m.end())cur++; REP(j,k+1){ if(0<j && --m[v[j-1]]==0){ m.erase(v[j-1]); if(v[j-1]<cur){ cycle.push_back(v[j-1]); }else{ cycle.push_back(cur); while(m.find(++cur)!=m.end()); } }else{ cycle.push_back(cur); while(m.find(++cur)!=m.end()); } } cout<<"Case #"<<i+1<<": "<<cycle[(n-k-1)%(k+1)]<<endl; } return 0; }