AtCoder Beginner Contest 108(ABC108)

ABC

正月もABC埋めを進めていきます。

A – Pair

A – Pair (atcoder.jp)

ちょっと難しめ、計算でも奇数偶数個の個数は求められそうだけど、WAが怖いのでfor文で愚直にカウントしました。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    int K;
    cin>>K;

    int g=0,k=0;
    for(int i=1;i<=K;i++){
        if(i%2==0) g++;
        else k++;
    }
    cout<<g*k<<endl;
}

B – Ruined Square

B – Ruined Square (atcoder.jp)

ちょっと難しめ。行列とかベクトルに詳しいと簡単に解けそうです。
初めの二点は、下から上、右から左、上から下、左から右の4パターンです。
この4パターンのどれかによって、3点目4点目の位置関係が変わってきます。この辺りを丁寧に場合分けします。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;

    int dx=abs(x1-x2);
    int dy=abs(y1-y2);

    int pat=0;
    if(x1<=x2&&y1<=y2) pat=0;
    if(x1>=x2&&y1<=y2) pat=1;
    if(x1>=x2&&y1>=y2) pat=2;
    if(x1<=x2&&y1>=y2) pat=3;

    int c=2;
    while(c-->0){
        swap(dx,dy);
        if(pat==0) x2-=dx,y2+=dy;
        if(pat==1) x2-=dx,y2-=dy;
        if(pat==2) x2+=dx,y2-=dy;
        if(pat==3) x2+=dx,y2+=dy;
        cout<<x2<<" "<<y2<<(c==0?"\n":" ");
        pat=(pat+1)%4;
    }
}

計算式は紙に、三平方の定理の証明で使われる、三角形4つと四角形1つの図を書いて調べました。

C – Triangular Relationship

C – Triangular Relationship (atcoder.jp)

a+bがKの倍数は、a+b=0 mod Kと言い換えられます。
a+c=b+c mod Kから、a=b mod Kと言えます。
上記2つから、a,bで考えられるパターンは、
a=b=0 mod K
a=b=K/2 mod K
のどちらかであると言えます。
これらは、a,cやb,cにも言えるため

N mod Kが0となるような数の個数の3乗
N mod KがK/2となるような数の個数の3乗 (a,b,cも整数のため、K/2が割り切れないなら0)

の2つを足し合わせた数が答えとなります。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    long long N,K;
    cin>>N>>K;

    long long ans=0;

    //K/2+K/2
    if(K%2==0){
        long long n=N-K/2;
        if(n>=0){
            long long c=n/K+1;
            ans+=c*c*c;
        }
    }

    //0+0
    long long c2=N/K;
    ans+=c2*c2*c2;

    cout<<ans<<endl;
}

D – All Your Paths are Different Lengths 

D – All Your Paths are Different Lengths (atcoder.jp)

制約から、log10^6が20くらいになるので、2進とか二分木とかで見ていきたい気持ちになります。
この気持ちは正解で、二進数を基準に考えると正解になります。
例えば13の場合、
1→2 0
1→2 1
2→3 0
2→3 2
3→4 0
3→4 4
と張り、0~7の8個を満たすグラフを作ります。
次に9~を作ることを考えると、1+8=9,2+8=10.1+2+8=11なので2->4に8を張ると9~11が一気にできそうです。
次に12を作ることを考えると、1+11=12なので1->4に11を張ると作れそう…と、次の数字をたくさん作れる位置に辺を張るということを、L-1のルートができるまで繰り返しました。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    int L;
    cin>>L;

    vector<int> vi,vj,vk;

    int keta=0;
    while(pow(2,keta)<=L) keta++;
    keta--;

    for(int i=1;i<=keta;i++){
        vi.push_back(i);
        vj.push_back(i+1);
        vk.push_back(0);
        vi.push_back(i);
        vj.push_back(i+1);
        vk.push_back(pow(2,i-1));
    }

    int nx=pow(2,keta);
    for(int i=keta;i>=1;i--){
        int n=nx+pow(2,i-1)-1;
        if(n<L){
            vi.push_back(i);
            vj.push_back(keta+1);
            vk.push_back(nx);
            nx=n+1;
        }
    }
    cout<<keta+1<<" "<<vi.size()<<endl;
    for(int i=0;i<(int)vi.size();i++){
        cout<<vi[i]<<" "<<vj[i]<<" "<<vk[i]<<endl;
    }

}

めちゃくちゃ難しいと思ったら700点問題だったのですね…。ABCで700とか怖い。

コメント

タイトルとURLをコピーしました