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;
}

コンテスト中のACコード

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;
}

コンテスト中のACコード

C - Low Elements

思考

「任意のhogeより小さい」は「hogeのminimumより小さい」と同値。よって前から見ていきながらi番目までの最小が何かを管理していけばおk。最小の初期値は+infにしておくと楽。

実装例

#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;
}

コンテスト中のACコード

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;
}

コンテスト中のACコード

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)

コンテスト中のACコード

追記(2020/01/19/23:21)

これは落ちる想定だったそうです。でも再帰で書いたカス実装でこれだし、多分もっと良い感じに書けばもうちょい余裕持って通った気もします。
良い解法は素因数分解して、各因数について、指数の最大を求める形でLCMを求めます。

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;
}

コンテスト中のACコード

終わりに

今回は余裕を持って解説が書きあがりました。ご精読、ありがとうございました。また見ていただけると幸いです。

*1:boost？知らない子ですね(誰か教えて)

*2:簡単ならバグらせんなや