ブログ名

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

トップ > AtCoder Beginner Contest 160 解法

AtCoder Beginner Contest 160 解法

結果

f:id:ngtkana:20200329000832p:plain

64:08 5 完 1255 位 です。（はい！？！？）

まさか ABC で冷えるとは思っていませんでした。 F の全方位で詰まったのは、（突然書き方を変えたのもありますが）実力相応で、戦犯は D の制約読み落としです。

✔A - Coffee (00:02:32)

string で受け取って比較です。

遅かったのは、online-judge-tools を初めて AtCoder でためしてうまくいかなかったからですから、良いとしましょう。 コンテスト中は使えないなどあるのでしょうか。

std::string s;std::cin>>s;
std::cout<<(s.at(2)==s.at(3)&&s.at(4)==s.at(5)?"Yes":"No")<<'\n';

✔B - Golden Coins (00:04:00)

500 円を作れるだけ作って、残りで 5 円を作りましょう。 予め入力を 5 で割っておくと良いです。

lint n;std::cin>>n;n/=5;
std::cout<<n*5+n/100*500<<'\n';

✔C - Traveling Salesman around Lake (00:45:29 + (1))

WA になっているのに気づかずです。(1 回目は 00:05:44)

最も長い場所を探しましょう。 vector で受け取って差を見ます。 最初と最後の距離は、最初のものに 1 周分足したと思うと良いです。

lint k,n;std::cin>>k>>n;
std::vector<lint>a(n);
for(lint&x:a)std::cin>>x;
lint max=k+a.front()-a.back();
for(lint i=0;i<n-1;i++){
    lint x=a.at(i+1)-a.at(i);
    if(max<x)max=x;
}
std::cout<<max<<'\n';

✔D - Line++ (00:43:16)

N は 2,000 以下です。（最重要事項）

これがないと地獄場合分けなのですが、焼け野原になっているであろう順位表を覗きに伺ったところ、 傷一つないご様子でしたから、一応、念の為、制約をチェックです。まさか私が制約を読まないなんてそんな…… をしていました（泣）

すべての点対に関して最短距離を定数時間でもとめて、重複度付きチェックリストを作ると良いです。 最短距離は、もとのグラフの最短距離と、X, Y を通るときのものを比較すると良いです。

lint n,x,y;std::cin>>n>>x>>y;
std::vector<lint>a(n);
for(lint i=1;i<=n;i++){
    for(lint j=i+1;j<=n;j++){
        a.at(std::min({
            j-i,
            std::abs(i-x)+1+std::abs(y-j),
            std::abs(i-y)+1+std::abs(x-j)
        }))++;
    }
}
for(lint k=1;k<n;k++){
    std::cout<<a.at(k)<<'\n';
}

✔E - Red and Green Apples (00:59:08)

赤色と緑色は始めから X 個、Y 個しかないとしてよいです。 すると、どう選んでも制約は満たされますから、大き方から X + Y 個選ぶと良いです。

実装は怒涛の標準ライブラリさんです。

lint X,Y,A,B,C;std::cin>>X>>Y>>A>>B>>C;
std::vector<lint>a(A),b(B),c(C);
for(lint&x:a)std::cin>>x;
for(lint&x:b)std::cin>>x;
for(lint&x:c)std::cin>>x;
std::sort(a.begin(),a.end(),std::greater<>{});
std::sort(b.begin(),b.end(),std::greater<>{});
std::sort(c.begin(),c.end(),std::greater<>{});
std::vector<lint>d;
d.insert(d.end(),a.begin(),a.begin()+X);
d.insert(d.end(),b.begin(),b.begin()+Y);
d.insert(d.end(),c.begin(),c.end());
std::sort(d.begin(),d.end(),std::greater<>{});
std::cout<<std::accumulate(d.begin(),d.begin()+X+Y,0ll)<<'\n';

✖F - Distributing Integers

全方位です。

根 x に隣接する各の頂点 y に関して、部分木のサイズ sz[y] と、 部分木の着色順の場合の数 dp[y] が分かっているとしましょう。 すると、根からの着色順の場合の数は、(sz[x] - 1) ! Π dp[y] / sz[y]! です。 これを全方位にするとよいです。

lint n;std::cin>>n;
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);
}
std::vector<lint>ord;
auto dfs=[&](auto&&dfs,lint x,lint p)->void{
    ord.push_back(x);
    auto&&v=g.at(x);
    for(lint y:v)if(p!=y)dfs(dfs,y,x);
    if(x)v.erase(std::find(v.begin(),v.end(),p));
};
dfs(dfs,0,0);
auto rord=std::vector<lint>(ord.rbegin(),ord.rend());
std::vector<lint>sz(n,1);
std::vector<mint>fact(n+1);fact.at(0)=mint{1};
for(lint i=1;i<=n;i++)fact.at(i)=fact.at(i-1)*mint{i};
std::vector<mint>dp(n),ep(n);ep.at(0)=mint{1};
for(lint x:rord){
    for(lint y:g.at(x))sz.at(x)+=sz.at(y);
    dp.at(x)=fact.at(sz.at(x)-1);
    for(lint y:g.at(x))dp.at(x)*=dp.at(y)/fact.at(sz.at(y));
}
for(lint x:ord){
    for(lint y:g.at(x)){
        ep.at(y)=dp.at(x)*ep.at(x)*fact.at(n-sz.at(y)-1)*fact.at(sz.at(y))
            /(dp.at(y)*fact.at(sz.at(x)-1)*fact.at(n-sz.at(x)));
    }
}
for(lint i=0;i<n;i++){
    std::cout<<(dp.at(i)*ep.at(i)*fact.at(n-1)
        /(fact.at(sz.at(i)-1)*fact.at(n-sz.at(i)))).value<<'\n';
}

長いです。

今回の実装では、keymoon さんから教わったこちらを導入してみました。 コンテスト 86 分前に敵に塩を送るなんて、お人好しです。（ところでまったく勝負になっていないのですが、あの……）