ABC152解説
結果は53:08 (1ペナ) 55位でした。今回のセットは割と簡単めだったので、この時間は微妙です。特にFでくだらないミスが多くて最悪でした。
A - AC or WA
思考
全テストケース通るか否かなのでN=M or notで場合分けです。なんで出力ACとWAじゃないんだろうなぁ。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; cout<<(n==m?"Yes":"No")<<endl; }
B - Comparing Strings
思考
桁数が少ない方が小さいので…って辞書順かーい。なら構成文字が小さい方が小さいです。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int a,b; cin>>a>>b; int c{}; for(int i=0;i<max(a,b);++i) cout<<min(a,b); cout<<endl; }
C - Low Elements
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n,c{}; cin>>n; vector<int> p(n); for(auto&i:p) in>>i; int M=1e9; fr(i,n){ if(M>=p[i]){ ++c; M=p[i]; } } cout<<c<<endl; }
D - Handstand 2
思考
i,jを1〜9の整数として、iで始まり、jで終わるN以下の整数の数がわかれば、Aがi..j、Bがj..iなる場合は、それぞれの通り数を掛け合わせることで分かる。あとは実際に1〜Nの整数に対し、何で始まって何で終わるのかを調べれば良いだけ(Nが準線形間に合わないと思って、桁DPっぽく高度算数しようとしてinf時間使ってしまった)。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int v[10][10]={}; for(int i-1;i<=n;++i){ int a=i%10,b=i; while(b>=10) b/=10; v[a][b]++; } ll ans{}; Fr(i,9) Fr(j,9) ans+=v[i][j]*v[j][i]; cout<<ans<<endl; }
E - Flatten
思考
「どのi,jについても」とかふざけた書き方しやがって、これは「任意のiについて
が一定値をとる」と同値です(どう見ても
なんだよなぁ、カス)。その一定値は任意のiについて
の倍数になっているので、
が最小になるようなとき、一定値は
の最小公倍数となる。考察簡単すぎるwwこれがE問題とは笑止千万w。とか思ってましたが、普通にクソでかくなるので、mod P上でlcmみたいなことを考えないといけない？だるいわね、Pythonの多倍長整数で常勝！w*1ということでめっちゃ久しぶりにPython書いてlcmくらいあるやろーーとかググったりして見つけられなくて、自前実装したりしてたら時間食いました。1964ms〜東京オリンピック〜ｗｗｗ。
実装例
Python3での実装です(は？)
def gcd(n,m): if n>m: return gcd(m,n); if n==0: return m; return gcd(m-n*(m//n),n) def lcm(x, y): return (x * y) // gcd(x, y) n=int(input()) a=list(map(int,input().split())) s=1 for i in a: s=lcm(s,i) ans=0 for i in a: ans+=s//i print(ans % 1000000007)
F - Tree and Constraints
思考
えー指数は解けません、本当にありがとうございました。
…とか言っててもしょうがないので考えます。Mが異様に小さいので、多分どっかでくらいの処理をかけるんだろうなぁと思いつつ、思考が停止。
しばらくののち、数え上げだし排反事象！とか思って考えていると、1つ以上存在は、否定したら1つも無いなので扱い安いじゃんと気付く(遅すぎ)。じゃあ包除原理で終わりですわー。
M個の条件のうち、いくつかを選んで、を結ぶパスを構成する辺は全て白い、というような場合を考える。これは簡単*2で、実際にパスを動いて通った辺をboolの配列とかで覚えておいて、通らなかった辺の個数をc個とすると、
通りである。パスを動くのは、あらかじめ木を根つきにしておいて、深さが揃うまで登って、深さが揃ったら、同じ頂点に行き着くまで登れば良い。辺のindexは覚えておかなくても、根以外の子と辺が1:1対応するので、そっちで考えるとわかりやすい。
あとはなんやかんやで足し引きすれば答えが求まる。
あらかじめ用意しておく2の累乗の配列のサイズを間違ってMくらいまでしか用意せずに破滅、1WA。
実装例
#include<bits/stdc++.h> using namespace std; struct tree{ size_t n,r; vector<vector<int>> e; vector<int> pa,d; explicit tree(int n_){ n=n_; e.resize(n); } void add(int a,int b){ e[a].emplace_back(b); e[b].emplace_back(a); } void r_dfs(int i,int p=-1,int D=0){ pa[i]=p;d[i]=D;++D; for(auto j:e[i]) if(j!=p) r_dfs(j,i,D); } void r_i(int r_){ pa.resize(n);d.resize(n);r=r_; r_dfs(r); } void f(vector<bool>&vis,int u,int v){ if(d[u]<d[v]) swap(u,v); while(d[u]>d[v]){ vis[u]=true; u=pa[u]; } while(u!=v){ vis[u]=true; vis[v]=true; u=pa[u]; v=pa[v]; } } }; int main(){ vector<ll> p2(50,1); fr(i,49) p2[i+1]=p2[i]*2; int n,m,a,b; cin>>n; tree t(n); for(int i=0;i<n-1;++i){ cin>>a>>b; t.add(--a,--b); } in>>m; vector<int> u(m),v(m); fr(i,m) in>>u[i]>>v[i],--u[i],--v[i]; ll ans{}; t.r_i(0); fr(d,(1<<m)){ int c{}; vector<bool> vis(n); fr(i,m) if((d>>i)&1){ ++c; t.f(vis,u[i],v[i]); } int cnt{}; for(int i=1;i<=n-1;++i) if(!vis[i]) ++cnt; if(c%2) ans-=p2[cnt]; else ans+=p2[cnt]; } cout<<ans<<endl; }
終わりに
今回は余裕を持って解説が書きあがりました。ご精読、ありがとうございました。また見ていただけると幸いです。
