壁打ちAtCoder

AtCoderの問題をひたすら解いてくブログです。思考やコードの書き方の私的備忘録として

AtCoder Beginner Contest 184 by C

AtCoder Beginner Contest 184 について
C言語での回答です

atcoder.jp

できたもの
A
B

できなかったもの
C
D以降

問題A

#include <stdio.h>

int main(void){
    int a,b,c,d;
    scanf("%d %d", &a,&b);
    scanf("%d %d", &c,&d);

    printf("%d\n", a*d-b*c);

    return 0;
}
方針

行列式の計算式が問題文中に書かれているのでそのまま計算してその結果を出力。

問題B

#include <stdio.h>
#include <string.h>

int main(void){
    int n,x,i;
    char s[200001];
    scanf("%d %d", &n,&x);
    scanf("%s", s);
    int size = strlen(s);

    long long total = x;
    for(i=0;i<size;i++){
        if(s[i]=='o'){
            total++;
        }
        else if(s[i]=='x'&&total!=0){
            total--;
        }
    }

    printf("%lld\n", total);

    
    return 0;
}
方針

得点を計算する変数の初期値をXとし、oなら+1、xなら-1を文字列の最後まで繰り返します。
ただし点数が0の場合にxがきても減らないのでそこは分岐の条件に注意。

問題C

#include <stdio.h>

int abs(int a){
    return a < 0 ? -a : a;
}

int main(void){
    int r1,c1,r2,c2,vr,vc,i;
    scanf("%d %d", &r1,&c1);
    scanf("%d %d", &r2,&c2);

    vr = r2-r1;
    vc = c2-c1;

    int ans = 3;
    if(vr==0&&vc==0){
        ans = 0;
    }
    else if(vr+vc==0||vr-vc==0||abs(vr)+abs(vc)<=3){
        ans = 1;
    }
    //斜め2回移動
    else if((vr+vc)%2==0){
        ans = 2;
    }
    //ブロック2回移動。マンハッタン距離3以下×2->6以下
    else if(abs(vr)+abs(vc)<=6){
        ans = 2;
    }
    //斜め右上+ブロック
    else if(abs(vr-vc)<=3){  
        ans = 2;
    }
    //斜め右下+ブロック
    else if(abs(vr+vc)<=3){
        ans = 2;
    }

    printf("%d\n", ans);

    return 0;
}
方針

f:id:Rgrayjourney:20210610201811j:plain

a+b=c+dという条件で現在のマスの右上がり(傾き正)方向のマスに移動ができ、
a-b=c-dという条件で右下がり(傾き負)方向のマスに移動ができます。(画像上部)
よってそれらを2回組み合わせることで元の座標と偶奇性が一致するすべてのマスに移動ができます。

偶奇性が異なるマスであっても、隣あうマスに移動すればマンハッタン距離は1となり、これは|a-c|+|b-d|≦3(マンハッタン距離が3以下)を満たすので全てのマスに3回以内に移動できます。

・移動が0回
移動先のマスと現在のマスが同じとき

・移動が1回
移動先のマスが、
a+b=c+d   右下がり直線上のマス
a-b=c-d    右上がり直線上のマス
|a-c|+|b-d|≦3  マンハッタン距離が3以下のマス

・移動が2回
右下がりと右上がり1回ずつ
右下がりとマンハッタン距離が3以下
右上がりとマンハッタン距離が3以下
マンハッタン距離が3以下が2回

・移動が3回
上記以外

なおマスの移動については、座標の差が大事なため、最初と最後のマス自体にそんなに意味はない。
vr = r2-r1, vc = c2-c1とすると、(0, 0)から(vr, vc)へ移動するとみなすこともできる。
(今回はそんなに関係なかったけど)

解けなかった原因

移動できる条件から移動できるマスを正確に把握できず、条件わけができなかった。

問題D

まだ