ABC 108(9/1) A,B,C問題の思考過程

AtCoder

なんか３完で５８位を取れたので思考過程を書きます。珍しくA→C→Bで解きました。

A問題

簡単な掛け算で解けそうでしたが、その式を考える時間で愚直ループ解を実装できそうだったのでそっちにしました。偶数の個数と奇数の個数を数えて掛け算します。

int main(){
    int k;
    cin>>k;
    int even=0,odd=0;
 
    rep(i,1,k+1){
        if(i%2==0)even++;
        else odd++;
    }
    cout<<even*odd<<endl;
}
B問題

正方形の残りの２点の座標を出力する問題です。最初、正方形は辺が方眼紙のせんに沿うような形しか想像していませんでした。ですが斜めに向くパターンもあると気づいてからサンプルをぐっと睨むと、入力のx座標の差分とy座標の差分を利用するだけと気づいたので実装しました。

int main(){
    int x,xx,y,yy;
    cin>>x>>y>>xx>>yy;
    int a,aa,b,bb;
    int diffx=xx-x,diffy=yy-y;
    a=xx-diffy;
    b=yy+diffx;
    aa=a-diffx;
    bb=b-diffy;
    cout<<a<<" "<<b<<" "<<aa<<" "<<bb<<endl;
}
C問題

a,b,cの任意の２つの和がKの倍数になるということで、「和が〜の倍数」という部分に余りの利用を感じました。
まず、a,b,cが全てKの倍数の時、当然任意の２つの和はKの倍数になるなあと思いました。
さらに、２つの数を足すということから、Kの剰余がK/2になる数も答えになると思いました。ここで、Kが偶数の時には成り立ちますが、奇数の時には成り立たない気がしました。試しにK=5を考えた時、5=2+3とすればa=2(mod K)、b=3(mod K) と仮定できますが、cにはaとの対では3、bとの対では2を当てるべきで、これは同時に満たせません。この例で、Kが奇数の時にはKの剰余がK/2になる値は使えないと結論づけました。

一般化（？）すれば、a,b,cをKでの剰余とし、K=a+bと分割した時、残りのcはK=a+c、K=b+cの両方を満たさねばならず、つまりa=b=cにならないといけません。このような時、a,b,cは0(mod K、つまりKの倍数)、またはK/2(mod K、ただしKは偶数)の時だけなのではー、と思ったわけです。

最後に、a,b,cの順番を入れ替えたものも違う組みとして考えることから、個数を数えて単に３乗すれば良いと気づきました。

int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> v(k,0);
    rep(i,1,n+1){
        v[i%k]++;
    }
    ll ans=0;
    ans+=(v[0]*v[0]*v[0]);
    
    if(k%2==0){
        ans+=(v[k/2]*v[k/2]*v[k/2]);
    }
    cout<<ans<<endl;