ABC150解説 - Motsu_xe 競プロのhogeやfuga

さて、今回から本格的にABCの解説記事を書いていきたいと思います。結果は70:09 (2ペナ) 26位でした。まあそれなりにむずかしかったし、悪くはないですがよくはないです。

A - 500 Yen Coins

思考

500円玉が $K$ 枚あると、 $500K$ 円になる。500円玉100枚ほしい人生だった。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int k,x;
    cin>>k>>x;
    cout<<(k*500>=x?"Yes":"No")<<endl;
}

コンテスト中のACコード

B - Count ABC

思考

$N$ が小さいので、 $1\leq i \leq n-2$ 番目の文字から $3$ 文字見てABCになっているか確認するだけで良い。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    string s;
    cin>>n>>s;
    int c{};
    for(int i=0;i<n-2;++i) if(s.substr(i,3)=="ABC") ++c;
    cout<<c<<endl;
}

コンテスト中のACコード

C - Count Order

思考

$N$ が小さいので、順列全部見ても8!=40320通りしかない。全ての順列を確認してP,Qと一致する奴が何番目か調べれば良い。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> p(n),q(n),r(n);
    for(auto&i:p) cin>>i,--i;
    for(auto&i:q) cin>>i,--i;
    for(int i=0;i<n;++i) r[i]=i;
    int a{},b{},c{};
    do{
        bool f=true,g=true;
        fr(i,n){
            if(p[i]!=r[i]) f=false;
            if(q[i]!=r[i]) g=false;
        }
        if(f) a=c;
        if(g) b=c;
        ++c;
    }while(next_permutation(r.begin(),r.end()));
    cout<<abs(a-b)<<endl;
}

コンテスト中のACコード

D - Semi Common Multiple

思考

$x$ が $2a$ の半倍数というのは、 $x\equiv a \ \mathrm{mod}\ 2a$ であるということである。よって $X$ が $A$ の半公倍数であることは、中国剰余定理からなんか $y$ があって、 $x\equiv y\ \mathrm{mod} \ \mathrm{lca}(A)$ である(これは嘘で後で訂正します)。この時の $y$ が何かと考えると、 $A/2$ で良いことがわかる(これは $mathrm{mod} a_i$ で考えたとき、2倍すると0になることからわかる)。よって $\mathrm{lca}(A)$ さえ求めれば良い。

さてここから私はWAとTLEを1回ずつくらいます。まず先ほど嘘と言った話ですが、例えば $2\ mathrm{mod}\ 4$ と $4\ mathrm{mod}\ 8$ は両立しません。ちょっと考えると自分の2倍のmodが定まっていると、存在しません。それをいい感じにチェックします(詳しくは実装例を)(追記するかも)。

またこれはlcaを考えるならいつも気をつけなきゃいけないことですが、オーバーフローして色々やばいです(負の数のlcaを想定していなかった影響で無限ループとかしてTLEを食らったと思う)。なのでいい感じにチェックします(あまりに大きい時は、M以下で存在しないので打ち切ることができます)。

実装例

#include<bits/stdc++.h>
using namespace std;

template<class T>
T gcd(T n,T m);

int main(){
    int n,m;
    cin>>n>>m;
    vector<ll> A(n);
    for(auto&i:A) cin>>i;
    sort(A.rbegin(),A.rend());
    unsigned long long a,x=1,d;
    fr(i,n){
        a=A[i];
        if(x%a==0&&(x/a)%2==0) return cout<<0<<endl,0;
        d=gcd(a,x);
        if(x>2*m/(a/d)+1) return cout<<0<<endl,0;
        x*=a/d;
    }
    cout<<(m+x/2)/x<<endl;
}

コンテスト中のACコード

E - Change a Little Bit

思考

S,Tに対しての最小コストがどんなかを考える。これはどう考えても $C_i$ が小さい方から取っていくのが良い。よって $C_i$ が最小の項は異なっていれば常に最初にとるし、 $C_i$ が最大の項は異なっていれば常に最後にとることがわかる。それぞれの項にを変更する総コストを考えて、最後に足すと良さそう。 $C_i$ を大きい順に並べ替えておく。
i番目の項の変更するコストを考える。i番目の項を最後からj番目に変更するような状況は、i番目の項が異なり、1〜i番目までで異なっているものがj-1個あるというような状況である。これは組み合わせを用いると簡単に計算できて、あとはWolfram Alphaに突っ込むと $O(logN)$ とかで計算できる。あとは全てのiについて考えて足せば良い。

実装例

#include<bits/stdc++.h>
using namespace std;

struct modint{}; //Z/MOD Z
modint pwr(int_fast64_t a,int_fast64_t b); //(a^b)%MOD

int main(){
    int n;
    cin>>n;
    vector<int> c(n);
    for(auto&i:c) cin>>i;
    sort(c.rbegin(),c.rend());
    modint ans{};
    for(int i=0;i<n;++i){
        ans+=pwr(2,2*n-2)*(i+2)*c[i];
    }
    cout<<ans<<endl;
}

コンテスト中のACコード

F - Xor Shift

思考

以下では添字は適当に $\mathrm{mod}\ N$ で考えて下さい。
a'とbが等しくなるような(k,x)のがどのような条件を満たすか考えると、 $a_{i+k}\oplus b_i=x$ を任意のiについて満たすことがわかる(xorは自分自身が逆元になるため)。よって $a_{i+k}\oplus b_i=a_{i+k+1}\oplus b_{i+1}$ を満たすので、 $a_{i+k}\oplus a_{i+k+1}=b_i\oplus b_{i+1}$ を満たすことがわかります。そのため、新たに $A_i=a_i\oplus a_{i+1}$ , $B_i=b_i\oplus b_{i+1}$ とすると、AをシフトさせてBと一致するようなkを考えれば良いことがわかる。kが複数ある場合は、Aが周期を持つので、あらかじめAの周期を調べておいて、kが最小のケースだけ考えれば良い*1。これは約数だけ見ればいいので $O(Nd(N))$ となる(d(N)は約数個数関数)。これは $N\leq 2\cdot 10^5$ なら十分高速。
あとはAをシフトさせてBと一致するようなkを考えればいいが、これは†Z-Algorithm†を使うとよくて、B+[-1]+A+A(ここで+は連結)というような数列についてZ-Algorithmを適用して、接頭辞とN文字共通しているところを探せば終わる*2。

実装例

#include<bits/stdc++.h>
using namespace std;

void zalgo(vector<ll>& s,vector<int>& z) //Z-algorithm

int main(){
    int n;
    cin>>n;
    vector<ll> a(n),b(n),A(n),B(n),c(3*n+1);
    for(auto&i:a) cin>>i;
    for(auto&i:b) cin>>i;
    fr(i,n) A[i]=a[i]^a[(i+1)%n];
    fr(i,n) B[i]=b[i]^b[(i+1)%n];
    vector<int> d;
    int s=n;
    for(int i=0;i<n;++i) c[i]=B[i];
    c[n]=-1;
    for(int i=0;i<n;++i){
        c[n+1+i]=A[i];
        c[2*n+1+i]=A[i];
    }
    vector<int> z;
    zalgo(c,z);
    for(int i=1;i<=n;++i){
        if(n%i==0){
            bool F=true;
            for(int j=0;j<i;++j){
                bool f=true;
                ll C=A[j];
                for(int k=0;k<n/i;++k) if(A[j+k*i]!=C) f=false;
                if(f) continue;
                F=false;
                break;
            }
            if(F){
                s=i;
                break;
            }
        }
    }
    bool f=false;
    for(int i=n+1;i<=3*n;++i){
        if(z[i]==n){
            i-=n+1;
            while(i<n){
                cout<<i<<" "<<(a[i]^b[0])<<endl;
                i+=s;
            }
            return 0;
        }
    }
}