| 
a b c d ------- 2 1 1 2 2 2 1 1 2 2 2 0
↓あとで (accepted in practice)
class StringGame { public: vector <int> getWinningStrings(vector <string> S) { int N=S.size(); VVI hi(N, VI(26)); REP(i, N) { REP(j, S[i].size()) { hi[i][S[i][j]-'a']++; } } cout<<hi<<endl; vector<int> ans; REP(i, N) { string alpha; VI live(N, 1); live[i]=0; REP(loop, 26) { REP(c, 26) { int lose_char=0; REP(j, N) { if(live[j] && hi[j][c] > hi[i][c]) lose_char=1; } if(lose_char) continue; REP(j, N) { if(live[j] && hi[j][c] < hi[i][c]) { live[j]=0; // アルファベットの順番（のうち確定したものだけ）も出すようにしてみる if(alpha.find(c+'a')==string::npos) alpha.PB(c+'a'); } } } } //cout<<live<<endl; cout<<i<<" "<<(accumulate(ALL(live), 0LL)==0 ? "OK":"NG")<<" Alphabet: "<<alpha<<endl; if(accumulate(ALL(live), 0LL)==0) ans.PB(i); } return ans; } };
"aabcdd", "aabbcd", "aabbcc" の場合 0 OK Alphabet: d 1 OK Alphabet: bd 2 OK Alphabet: bc
| 
↓あとで (accepted in practice)
VI make_primes(int N) { // return all prime numbers less than N memory: O(N) time: O(N^2)? VI p(N, 1), out; for(int i=2;i<N;i++) if(p[i]) { out.push_back(i); for(int j=i*2;j<N;j+=i) p[j]=0; } return out; } VI primes; pair<ll, ll> f(int n) { ll out = 0LL; REP(ii, primes.size()) { int i=primes.size()-1-ii; int odd = 0; while(n % primes[i] == 0) { n/=primes[i]; odd = 1 - odd; } out = (out << 1) | odd; } return MP(n, out); } class TheSquareRootDilemma { public: int countPairs(int N, int M) { primes = make_primes(290); map<pair<ll, ll>, ll> ms; RANGE(i, 1, M+1) { ms[f(i)]++; } ll ans = 0; RANGE(i, 1, N+1) { ans += ms[f(i)]; } return ans; } };
| 
↓あとで (accepted in practice)
class FoxAndHandle { public: string lexSmallestName(string S) { int N=S.size(); VVI hi(N+1, VI(256)); REP(i, N) { hi[N-1-i] = hi[N-1-i +1]; hi[N-1-i][S[N-1-i]]++; } string Hs; { VI w(256); REP(i, N) w[S[i]]++; REP(i, 256) { while(w[i]) { Hs.PB((char)i); w[i]-=2; } } } string H; int Si = 0; while(Hs.size()) { VI lhi(256); REP(j, Hs.size()) lhi[Hs[j]]++; REP(k, Hs.size()) { int idx=0; RANGE(i, Si, N) if(S[i]==Hs[k]) {idx=i;break;} int ok=1; REP(j, 256) if(hi[idx][j]<lhi[j]) ok=0; if(ok) { H.PB(Hs[k]); string nHs; int removed=0; REP(z, Hs.size()) { if(!removed && Hs[k]==Hs[z]) removed=1; else nHs.PB(Hs[z]); } Hs=nHs; //Si=idx; // だめ Si=idx+1; // OK break; } } } return H; } };
| 
int main() { //ios::sync_with_stdio(false); ll N, D; while(cin>>N>>D) { VI w(N); REP(i, N) { cin>>w[i]; } sort(ALL(w)); ll ans=0; REP(i, N-2) { // binary search [i+1, N-1] int idx = (upper_bound(&w[i+1], &w[N], w[i]+D) - &w[0])-1; //cout<<i<<" "<<idx<<endl; ll mid = idx-i-1; if(mid>=0) ans += mid*(mid+1)/2; } cout<<ans<<endl; } return 0; }
| 
ll N, K; VI Q, S, P, W; VI Same; // idx [-K K] [0 2K] int apply(int sign) { if(sign==1) { REP(i, N) W[i]=P[Q[i]-1]; } else { REP(i, N) W[Q[i]-1]=P[i]; } REP(i, N) P[i]=W[i]; return 1; } int main() { //ios::sync_with_stdio(false); while(cin>>N>>K) { Q=VI(N); S=VI(N); P=VI(N); W=VI(N); Same=VI(2*K+1); REP(i, N) { cin>>Q[i]; } REP(i, N) { cin>>S[i]; } for(int sign=-1;sign<=1;sign+=2) { REP(i, N) P[i]=i+1; REP(i, K+1) { int same=1; REP(j, N) if(P[j]!=S[j]) same=0; //cout<<P<<endl; Same[i*sign + K] = same; apply(sign); } } //cout<<Same<<endl; //break; deque<int> q; q.PB(0); int OK=0; REP(loop, K+1) { deque<int> nq; VI vis(2*K+1); while(q.size()) { int idx = q.front();q.pop_front(); //cout<<"loop "<<loop<<" pop "<<idx<<endl; if(loop==K && Same[idx+K]) { //cout<<" same at Kth"<<endl; OK=1;break; } if(loop<K && !Same[idx+K]) { //cout<<" not same"<<endl; if(!vis[idx-1+K]) {vis[idx-1+K]=1; nq.PB(idx-1); } if(!vis[idx+1+K]) {vis[idx+1+K]=1; nq.PB(idx+1); } } } //cout<<"NQ "<<nq<<endl; q = nq; if(q.size()==0) break; } cout<<(OK?"YES":"NO")<<endl; //break; } return 0; }
| 
