ABC166 解説
Eが簡単すぎてガチで引いて調子が崩れた(言い訳)。Fで大破滅しました…。かなり嫌な気持ちです。結果は96:40 598位。
A - A?C
思考
やるだけオブザイヤー2020ノミネート。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; puts(s=="ABC"?"ARC":"ABC"); }
B - Trick or Treat
思考
一度でも出現したら対象から外れるので、boolの配列を持って出現をチェックします。
実装例
#include<bits/stdc++.h> using namespace std; int main(){int n,k,d,a; cin>>n>>k; vector<bool> v(n,true); for(int i{};i<k;++i){ cin>>d; for(int j{};j<d;++j){ cin>>a; --a; v[a]=false; } } int ans{}; for(int i{};i<n;++i) if(v[i]) ++ans; cout<<ans<<endl; }
C - Peaks
思考
道の両端で、真に高くはない方が対象から外れるというだけでB問題と同じです。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n,m,a,b; cin>>n>>m; vector<int> h(n); vector<bool> g(n,true); for(auto&i:h) cin>>i; for(int i{};i<m;++i){ cin>>a>>b; --a,--b; if(h[a]<=h[b]) g[a]=false; if(h[a]>=h[b]) g[b]=false; } int c{}; for(int i{};i<n;++i) if(g[i]) ++c; cout<<c<<'\n'; }
D - I hate Factorization
思考
が5乗数として非負のものの和か差になっているかを考えればよい。なので、とかだと明らかに差も和も該当しない。なのでなるものだけ考えておけばよい。1000以下の非負整数Cについて連想配列mpでmp[C^5]=Cとしておいて、AかBを固定すれば簡単にチェックできる。
実装例
#include<bits/stdc++.h> using namespace std; using ll=long long; int main(){ ll x; cin>>x; unordered_map<ll,int> mp; for(int i{1000};i--;){ ll c{1}; for(int j{};j<5;++j) c*=i; if(mp[c+x]) return cout<<mp[c+x]<<" "<<i<<endl,0; if(mp[x-c]) return cout<<mp[x-c]<<" "<<-i<<endl,0; mp[c]=i; } }
E - This Message Will Self-Destruct in 5s
思考
とするととなっていればよい。よって連想配列にの個数を保存しながら、配列を右から舐めていって、数えていけばいい。D問題のが100倍むずいだろD問題でちょっとめんどい解法使ってたからDのがむずい気がしたけど、そうでもないかも、でもEのがやっぱ簡単だとは思う。遅刻しなければFAが…って言おうとしたけど、まあ2分切れたかは怪しいな。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> a(n); for(auto&i:a) cin>>i; unordered_map<int,int> mp; ll ans{}; ifr(i,n){ ans+=mp[a[i]+i]; mp[i-a[i]]++; } cout<<ans<<endl; }
F - Three Variables Game
思考
まずのとき、少ない方から多い方に、同じなら適当に移すことで達成できるなら達成できるし、失敗するようなら失敗する。これを示す。
のときはどうやっても無理。
のときは、全ての操作が、選択肢が1つ以下なので、OK。
のとき。もし初期状態で0が2つあって、初手でその2つが選ばれた場合は無理。初手でその2つが選ばれなければ、0は1つになる。よって全て初期状態で0が1つ以下の場合に帰着される。定めた移し方では、0の数は増えることはない増えるとしたら0が0個のときだけなので、常に0は1つ以下となり、必ず失敗しない。
よって示された。
あとはのときを考えればいい。状態は(A,B,C)=(0,1,1),(1,0,1),(1,1,0),(2,0,0),(0,2,0),(0,0,2)の6つしかあり得ないので、どの状態に遷移可能かDPすればいい。実際の操作の復元は、可能な操作をDPの結果から遡っていけばいい。ところでいい感じの実装ありますか??破滅しました。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,A,B,C; cin>>n>>A>>B>>C; string ans; ans.reserve(n); if(A+B+C==2){ auto v=vector(n+1,vector(6,false)); if(!A+!B+!C==1){ if(!A) v[0][0]=true; if(!B) v[0][1]=true; if(!C) v[0][2]=true; } else{ if(A) v[0][3]=true; if(B) v[0][4]=true; if(C) v[0][5]=true; } vector<string> s(n); for(int i{};i<n;++i){ cin>>s[i]; if(s[i]=="AB"){ if(v[i][0]) v[i+1][1]=true; if(v[i][1]) v[i+1][0]=true; if(v[i][2]) v[i+1][3]=v[i+1][4]=true; if(v[i][3] or v[i][4]) v[i+1][2]=true; } if(s[i]=="AC"){ if(v[i][0]) v[i+1][2]=true; if(v[i][2]) v[i+1][0]=true; if(v[i][1]) v[i+1][3]=v[i+1][5]=true; if(v[i][3] or v[i][5]) v[i+1][1]=true; } if(s[i]=="BC"){ if(v[i][1]) v[i+1][2]=true; if(v[i][2]) v[i+1][1]=true; if(v[i][0]) v[i+1][4]=v[i+1][5]=true; if(v[i][4] or v[i][5]) v[i+1][0]=true; } bool F{}; for(int j{};j<6;++j) F=F||v[i+1][j]; if(!F) return puts("No"),0; } for(int j{};j<6;++j) if(v[n][j]){ cout<<"Yes"<<'\n'; int t=j; stack<char> ans; for(int i{n};i--;){ if(s[i]=="AB"){ if(t==0) ans.push('B'),t=1; else if(t==1) ans.push('A'),t=0; else if(t==2){ if(v[i][3]) ans.push('B'),t=3; else ans.push('A'),t=4; } else if(t==3) ans.push('A'),t=2; else if(t==4) ans.push('B'),t=2; } if(s[i]=="AC"){ if(t==0) ans.push('C'),t=2; else if(t==2) ans.push('A'),t=0; else if(t==1){ if(v[i][3]) ans.push('C'),t=3; else ans.push('A'),t=5; } else if(t==3) ans.push('A'),t=1; else if(t==5) ans.push('C'),t=1; } if(s[i]=="BC"){ if(t==1) ans.push('C'),t=2; else if(t==2) ans.push('B'),t=1; else if(t==0){ if(v[i][4]) ans.push('C'),t=4; else ans.push('B'),t=5; } else if(t==4) ans.push('B'),t=0; else if(t==5) ans.push('C'),t=0; } } while(!ans.empty()) cout<<ans.top()<<'\n',ans.pop(); return 0; } assert(false); } for(int i{};i<n;++i) { string s; cin>>s; if(s=="AB"){ if(A<B){ ++A;--B; ans+='A'; } else{ ++B;--A; ans+='B'; } } if(s=="BC"){ if(B<C){ ++B;--C; ans+='B'; } else{ ++C;--B; ans+='C'; } } if(s=="AC"){ if(C<A){ ++C;--A; ans+='C'; } else{ ++A;--C; ans+='A'; } } if(A<0||B<0||C<0) return puts("No"),0; } cout<<"Yes"<<'\n'; for(auto&c:ans) cout<<c<<'\n'; }
終わりに
Fで適当こきすぎて、実装が破滅して終了しました。これどうやったらきれいに書けるの???