ブログ名

競技プログラミングやお歌のお話をする高菜です。

トップ > AtCoder Beginner Contest 163 解法

AtCoder Beginner Contest 163 解法

結果

91:47 全完です。

今回はかなり安定を取った上に、比較的難し目な回でしたから、全完できれば良しとしましょうか。

解法

A - Circle Pond (00:03:43)

サンプルの 6.28318530717958623200 をコピーして掛け算がよいです。

ld x;std::cin>>x;
std::cout<<x*6.28318530717958623200<<'\n';

ld は私の定義している long double のエイリアスです。

B - Homework (00:04:45)

負になってもお構いなしですべて引いてしまって、あとで確認です。

lint n,m;std::cin>>n>>m;
while(m--){
    lint x;std::cin>>x;
    n-=x;
}
std::cout<<(n<0?-1:n)<<'\n';

C - management (00:06:46)

各ボスの出現回数をカウントすると良いです。

lint n;std::cin>>n;
std::vector<lint>a(n);
for(lint i=1;i<n;i++){
    lint x;std::cin>>x;x--;
    a.at(x)++;
}
for(lint i=0;i<n;i++){
    std::cout<<a.at(i)<<'\n';
}

D - Sum of Large Numbers (00:13:21)

10 のなんとか乗は無視して、「個数と合計のペア」が何通りであるかをカウントです。

ところで 各 K に対して、集合 { 0, 1, 2, 3, ..., N } の大きさ K の部分集合の中の総和全体の集合は 区間になることが知られています。（ヒント：帰○法） ですから、最大と最小を求めるとよいです。

lint n,k;std::cin>>n>>k;
std::vector<lint>min(n+2),max(n+2);
for(lint i=0;i<=n;i++)min.at(i+1)=min.at(i)+i;
for(lint i=0;i<=n;i++)max.at(i+1)=max.at(i)+n-i;
mint ans=0;
for(lint i=k;i<=n+1;i++)ans+=max.at(i)-min.at(i)+1;
std::cout<<ans<<'\n';

E - Active Infants (00:27:52)

少し安定をとりすぎたでしょうか。 大きめなサンプルの手計算をしてしまいました。 とはいえ、思ったほどロスしている様子はありませんし、リスクヘッジな戦略としては良かったかもしれません。

左に動くか右に動くかで 2 グループに分けると、それぞれのグループのなかで最も元気な子が端っこに行くのが良いです。 そこで、元気順に幼児をイテレートして、左右どちらになるかで場合分けです。 状態は、左右にどれくらいずつ幼児溜まりができているのかを管理すればよいですから、区間 DP です。

lint n;std::cin>>n;
std::vector<std::pair<lint,lint>>ai(n);
for(lint i=0;i<n;i++){
    lint x;std::cin>>x;
    ai.at(i)={x,i};
}
std::sort(ALL(ai));
auto a=project<0>(ai);
auto ord=project<1>(ai);
std::vector<std::vector<lint>>dp(n+1,std::vector<lint>(n+1,0));
for(lint d=n;d>=1;d--){
    for(lint l=0;l<=n-d;l++){
        lint r=l+d;
        lint x=dp.at(l).at(r),y=a.at(d-1),j=ord.at(d-1);
        cmx(dp.at(l+1).at(r),x+y*std::abs(l-j));
        cmx(dp.at(l).at(r-1),x+y*std::abs(r-1-j));
    }
}
lint ans=0;
for(lint i=0;i<=n;i++)cmx(ans,dp.at(i).at(i));
std::cout<<ans<<'\n';

実装はこのように、区間がどんどん小さくなっていく DP をするとよいです。

project<Idx> は全要素を第 Idx 成分に射影した vector をつくる、私の定義した関数です。

F - path pass i (01:31:47)

サンプルが、弱すぎるぞぉぉぉぉおおおお！！！！（火事）

なんで変なサンプルしか置かないんですかぁぁああ（泣）

はい、気を取り直してですね。

なかなか実装の厳しい問題で、ハズレ方針かなと思ってかなり粘ったのですが、
結局他に思いつかず、このまま突き進みました。

考察パートです。

色 k について考えましょう。補集合をカウントです！

色 k を通らないパスは、もとのグラフから色 k の頂点をすべて消したグラフの連結成分に収まっているものです。 ですから、このサイズを求めればよいですね。

これは間に合うのでしょうか。
一つの頂点を消したことで、連結成分がどっと増えることもありますね。

しかし、心配はありません。
そう、iPhone ならね（キリッ）（Android ユーザー）

このようにしてできる連結成分はもとのグラフの辺に向きをつけたものと一対一対応します。

間に合います。

追記 2020-04-20

向き付きの辺と一対一対応するのは嘘でした。

根を含まないようなものが、向きなしの辺と一対一対応し、根を含むものは色と一対一対応します。

実装パート 1 〜 これがわかるとなにがうれしいですか？ 〜

木 DP です。 根以外の各頂点 x について、dp[ x ] = (

x の部分木から x の親の色の頂点をすべて消します。
その連結成分のうち、x の入っているもののサイズを考えましょう。
x も消えてしまうならば、0 です。

ところがどっこいこれではありません。
これを x の部分木のサイズから引いたものが dp[x] です。かなしいですね。

引き算は分かりづらいです。
別の言い方をすると、x の入って「いない」部分木の連結成分について、
連結成分の大きさ + 1 を足し合わせたものです。
DP ではこちらを求めると考えると遷移が楽です。

return dp[x];

) を求めましょう。

これがわかると何が嬉しいかというとですですね……（これはミームをいいたいだけの人です。）

色 k の頂点で分かれた連結成分のリスト = (

まず色 k の頂点をすべて考えましょう。
これの下側に直接くっついているものがこの子の担当です。
さて、ひとつの頂点はこんなにたくさんの情報を持っていません。
そうです、この情報は、子の情報です。（うまい！）

ですから、親の色が k であるような（根でない）頂点をすべて列挙して、
それに対する DP の値を列挙すると良いです。

あら、なにか忘れているような...

するどいです。
根を含む連結成分がありません。
これは、個数とそれぞれのサイズが分かっていますから、引き算でわかりますね。

列挙完了です。
実装次第ではサイズ 0 もいくつか紛れ込んでしまいますが、知りません。良いです。
さて、そろそろスコープを抜けましょうか。

return なにか;

)

というふうに、求めたかったものを求めることができます。

さて、次のステップです。

実装パート 2 〜 これはどのように求めますか？ 遷移です。 〜

木 DP をしましょう。親の色を見て、自分の部分木内にあるその色のあれを探します。
あれというのは、その色の頂点をすべて消したときの、自分の属さない連結成分に関して、
その大きさ + 1 の和でした。

しかし、この情報はどこから取ってくるのでしょう。
この情報は、子の情報から集約して得ることができます。
（ナイーブに実装すると遅いですが、）各頂点が、自分の部分木の中のどの色がどれだけあれ（←あれです。）かを知っているとしましょう。
つまり、ep[ 頂点 x ][ 色 k ] = (部分木の中で色 k で分けたとの x の属さない成分の大きさ +1 の和) を求めればよいです。

これは、およそ次のように遷移します。

ep[ x ][ k ] = sum( ep[ y ][ k ] for y は子です。)

ただし、k が x の色に一致する場合は、x の部分木のサイズで上書きです。

はーい、めでたしめでたし。解けました！

解けないんですよね……

実装パート 3 〜 † 高速化パート † 〜

ここが地獄なのですが、もうすこし良いやり方があるのでしょうか。

マージテクです。

まずすぐに分かることとして、小さい部分木にはあまり色がありませんから、map にするとよいです。
すると、最大頂点のもつ map を使い回すことで、マージテク的な計算量になります。

説明はすぐでしたね。

ソースコード

1

グラフの構築です。

lint n;std::cin>>n;
std::vector<lint>c(n);
for(lint&x:c){std::cin>>x;x--;}
std::vector<std::vector<lint>>g(n);
for(lint i=0;i<n-1;i++){
    lint u,v;std::cin>>u>>v;u--,v--;
    g.at(u).push_back(v);
    g.at(v).push_back(u);
}

2

複雑になりそうな気配がしましたから、DFS を 2 回に分けて実装しました。
本来は分けなくてもよさそうです。

ここでは、部分木のサイズ sz を求めます。

せっかくですから、いろいろとプリプロセスをしてしまいましょう。
親を消して、prt に入れます。
さらに、HL 分解の要領で、最大の子を初めに持ってきましょう。

std::vector<lint>sz(n,1),prt(n);
auto dfs=[&](auto&&f,lint x,lint p)->void{
    auto&&v=g.at(x);
    if(x!=p)v.erase(std::find(ALL(v),p));
    for(lint&y:v){
        f(f,y,x);
        prt.at(y)=x;
        sz.at(x)+=sz.at(y);
        if(sz.at(v.front())<sz.at(y))std::swap(v.front(),y);
    }
};
dfs(dfs,0,0);

3

本計算です。

くだんの map は戻り値にします。
葉の場合だけ場合分けで早期リターンをします。

葉でない場合には、先頭の子の戻り値を使いまわして、そこに追加をしていきます。
そして自分の色は上書きです。
すると DP 配列が更新できますから、ダイイングメッセージです。
僕を再帰呼出ししてくれてありがとう…… return;

std::vector<lint>dp(n);
auto efs=[&](auto&&f,lint x)->std::map<lint,lint>{
    auto&&v=g.at(x);
    if(v.empty()){
        dp.at(x)=c.at(x)!=c.at(prt.at(x));
        return {{c.at(x),1}};
    }
    lint head=v.front();
    auto ans=f(f,head);
    for(lint y:g.at(x)){
        if(head==y)continue;
        auto now=f(f,y);
        for(auto[key,val]:now)ans[key]+=val;
    }
    ans[c.at(x)]=sz.at(x);
    dp.at(x)=sz.at(x)-ans[c.at(prt.at(x))];
    return ans;
};
efs(efs,0);

4

連結成分の大きさを色ごとに分類して、計算して出来上がりです。あたたかいうちにどうぞです。

std::vector<std::vector<lint>>cmp(n);
std::vector<lint>count(n);
for(lint i=0;i<n;i++){
    count.at(c.at(i))++;
    if(i==0)continue;
    lint k=c.at(prt.at(i));
    cmp.at(k).push_back(dp.at(i));
}
for(lint i=0;i<n;i++){
    lint sum=std::accumulate(ALL(cmp.at(i)),0ll);
    cmp.at(i).push_back(n-count.at(i)-sum);
}
for(auto&&v:cmp){
    lint ans=n*(n+1)/2;
    for(lint x:v){
        ans-=x*(x+1)/2;
    }
    std::cout<<ans<<'\n';
}