ABC163 解説
今回割と難しかったっと思うんですが、めちゃくちゃすんなり考察できて、なんか最強になってました。結果は44:00 4位!!。ところでunratedになったらから、人々がTwitterに戻ったという説もあるし、単純に鯖が崩壊してて遅い人もいるかもで、4位は額面通りではなさそう。でも私も3分くらい問題見れなかったし、まあ感覚的にも成功なので、まあ喜んでいいんじゃないかな。
A - Circle Pond
思考
周長は半径に比例するので、サンプル1の答えに半径をかければ良いです。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ double r; cin>>r; cout<<setprecision(20)<<r*6.28318530717958623200<<endl; }
B - Homework
思考
宿題をやる日以外全部遊べばいいです。宿題だけで夏休みが
実装例
#include<bits/stdc++.h> using namespace std; using ll=long long; int main(){ int n,m,a; ll s{}; cin>>n>>m; for(int i{};i<m;++i){ cin>>a; s+=a; } cout<<max(n-s,-1)<<'\n'; }
C - management
思考
A_iでの出現回数が、部下の数です。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n,x; cin>>n; vector<int> c(n); for(int i{1};i<n;++i){ cin>>x; --x; c[x]++; } for(auto&i:c) cout<<i<<'\n';
D - Sum of Large Numbers
思考
ベースの数が大きすぎて、足す個数が異なれば、必ず和は異なります。そんでもって、足す個数をLとするとからの間の数は全て作れます*1。よってK<=L<=N+1について、を足し合わせればいいです*2。
実装例
#include<bits/stdc++.h> using namespace std; struct modint{}; //いつもの int main(){ int n,k; cin>>n>>k; modint ans; for(int j=k;j<=n+1;++j){ ans+=modint(j)*(2*n+1-j)/2-modint(j)*(j-1)/2+1; } cout<<ans<<endl; }
E - Active Infants
思考
原則として、でかい方から貪欲に一番遠いところに置くのが良いです。貪欲に詰めてないやつが最適だとすると、でかい方から置いていって、一番遠くじゃないところに置いた初めてのやつを、一番遠いところとswapすると、悪くはならないことからわかります。ですが、遠いところは2通りある場合があり、両方試してると、最悪みたいななります*3。なので、条件を緩和すると、左右の余ってるどっちかの端に置くと言うことは言えています。なのでdp_i,jを「大きい方からi+j個を左からi個, 右からj個詰めたときの最大のうれしさ」と定義すると、簡単にDPが回ってで解けて、うれしさが最大になります。
実装例
#include<bits/stdc++.h> using namespace std; using ll=long long; inline bool chmax(ll&x,ll y); ll dp[2001][2001]={}; int main(){ int n; cin>>n; vector<pair<ll,int>> a(n); fr(i,n){ cin>>a[i].first; a[i].second=i; } sort(a.rbegin(),a.rend()); ll ans{}; for(int i{};I<=n;++i) for(int j{};i+j<=n;++j){ if(i==0&&j==0) continue; if(i) chmax(dp[i][j],dp[i-1][j]+a[i+j-1].first*abs(a[i+j-1].second-i+1)); if(j) chmax(dp[i][j],dp[i][j-1]+a[i+j-1].first*(n-j-a[i+j-1].second)); if(i+j==n) chmax(ans,dp[i][j]); } cout<<ans<<'\n'; }
F - path pass i
思考
単純パス全体の数は、で簡単にわかるので、色kが塗られている頂点を通らない単純パスの数を求めれば良い。これは色kが塗られている頂点を除いたときの連結成分上のパス全体が該当する。よって各連結成分の要素数がわかれば良い。ただ、各色ごとに愚直にそれを計算すると、になってしまい、普通に間に合いません。
よって、木DPしながらなんやかんやしたいなぁとなる。適当に根付き木にして、DFSをしていくことを考える。例えばある色kの頂点を根とする部分木に、根以外の頂点が色kで塗られていないとする。このとき、子の部分木は考えたい連結成分になっている。この時は、子のサイズをもってきて、なんやかんやすればいい。
もし根以外にも頂点が色kで塗られていたとすると、その部分木は連結成分から除いておきたい。これを達成するにはDFS中に、部分木の色kの除くべき連結成分の合計個数を常に覚えておけば良い。
これ以上は説明が難しいので、あとはコードを読んで理解してください(は?)。
実装例
#include<bits/stdc++.h> using namespace std; using ll = long long; struct tree{ size_t n,r,md; vector<vector<int>> e; vector<int> c,sz; vector<ll> ans,C; explicit tree(int n):n(n),e(n),c(n),C(n),ans(n, ll(n)*(n+1)/2){} void built(){ static int a,b; for(auto&i:c) cin>>i,--i; for(int i{1};i<n;++i){ cin>>a>>b; --a,--b; e[a].emplace_back(b); e[b].emplace_back(a); } } void dfs(int i=0,int p=-1){ ll tmp = C[c[i]]; for(auto j:e[i]) if(j!=p){ C[c[i]]=0; dfs(j,i); sz[i]+=sz[j]; ans[c[i]]-=(sz[j]-C[c[i]])*(sz[j]-C[c[i]]+1)/2; } C[c[i]] = tmp+sz[i]; } void solve(){ sz.assign(n,1); dfs(); for(int i{};i<n;++i) cout<<ans[i]-(n-C[i])*(n-C[i]+1)/2<<'\n'; } }; int main(){ int n; cin>>n; tree t(n); t.built(); t.solve(); }
終わりに
F問題くそ面白かったけど、この思考をうまく言語化できないため、カス。EもFも簡単ではないと思うんだけど、すんなり解けて成長を感じましたね。ゴタゴタはあったけど、4位!!1桁順位は公式コンテストでは初めてです!嬉しい!