AtCoder abc398 振り返り

AtCoder Beginner Contest 398 の振り返りです。

AtCoder Beginner Contest 398

ABC398の振り返りです。 今週はBがちょっと意地悪な分250点で、400点問題の代わりに425点問題がDEと2問続くという変則的な配点だった。

コンテスト成績 >

A Doors in the Center: Solved

-と=を使って決められた長さの回文文字列を作る問題。

ちょっとだけ時間をかけてしまったけれど、特に問題なくACできた。

B Full House 3: Solved(1ペナ)

7枚のトランプ(1~13)の数字を使って、フルハウスの役をつくれるか判定するという、テキサスホールデムっぽい課題。

ただし、より強い役ができててもあくまでもフルハウスを満たすかを判定するので、その点で注意が必要だった。 まんまと、その罠にハマって1ペナくらってしまった。別に4枚3枚の組み合わせでもフルハウスを作れるんだよね。

ちゃんと、上記のケースも考慮してACできた。

C Uniqueness: Solved

与えられた数列から、ダブりのない最大値を求めて、その最大値が何番目にあるかを答える問題。 最大値を求めるまでは簡単だが、その最大値が何番目にあるかを求めるところに一捻りある感じ。

pairを使って、数列の値とインデックスをそれぞれ保持しておき、ダブりのない最大値を求めてると同時にインデックスがわかるようにしておいた。 割とスムーズにACできた。

D Bonfire: Solved

風向きと現在地が与えられ、Nステップ後に原点から発生し続ける煙が到達しているかを各ステップで判定していく問題。

問題的にシミュレーションで解くのは難しそうなので、別の方法を考える。 小一時間考えて、座標変換かなと思い、煙ではなく現在地の方を移動させる方針で解くことにした。 煙の座標をSetにpairで座標を入れていくことで、煙の有無の検証時間を短縮できることにも気づけた。

途中、ケアレスミスを犯してしまい、ギリギリまでデバッグにかかってしまったが、なんとかACできた。

int main() {
    int n,r,c;
    cin >> n >> r >> c;
    string s;
    cin >> s;
 
    set<pair<int,int>> st;
    int x=0,y=0;
    st.insert(make_pair(0,0));
    for(int i = 0; i < n; i++){
        if(s[i] == 'N'){
            x++;
            r++;
        } else if(s[i] == 'S'){
            x--;
            r--;
        } else if(s[i] == 'W'){
            y++;
            c++;
        } else if(s[i] == 'E'){
            y--;
            c--;
        }
 
        if(st.count({x,y})==0){
            st.insert(make_pair(x,y));
        }
        if(st.count({r,c}) > 0){
            cout<< 1;
        } else {
            cout<< 0;
        }
    }
    cout << endl;
}

所感

今回の配点だとD問題が425点の配点だったので、これまでで配点上は一番難しい問題を解いたことになる。 ギリギリのACだったこともあるが、正直解けないかと思っていたので素直に嬉しい。

レーティングの方もだいぶ回復してきて、あと少しでベストのレーティングを更新できそうなところまで来ることができた。 来週も頑張って、ぜひレーティングを更新したい。