社会人エンジニアがatcoderで茶色を目指す#1

前回

社会人エンジニアがプログラミングコンテストに参加してみたい#2

ABCに一回参加したのでタイトルを変更して記載していきます。

Atcoder Begginers Selectionへ挑戦

前回はコンテストに参加して、ABCの３問回答に終わりました。
まだ１回しか参加していません。
Atcoder Begginers Selectionへ参加してABCの難易度にて自身に問題がないか確認しましょう。

Atcoder Begginers Selection

A〜Bの８問題に関しては何も問題はないと思います。
C問題の以下３問について考えていきます。

ABC085C Otoshidama

問題文はatCoderにて読んでください。

まず考えるのは、

• Y<２＊１０の７乗なのでint型を使用
• ループによる全検索
• N=10000の枚数＋5000の枚数＋1000の枚数
• Y=10000×10000の枚数＋5000×5000の枚数＋1000×1000の枚数
  ここからコーディングをします。

    int N, Y;
    cin >> N >> Y;
    
    for(int i=0; i<=N; i++){
        for(int j=0; j<=(N-i); j++){
            for(int k=0; k<=(N-i-j); k++){
                if(Y==i*10000 + j*5000 + k*1000 && N==i+j+k){
                    cout << i << " " << j << " " << k << endl;
                    goto END;
                }
            }
        }
    }

    cout << -1 << " " << -1 << " " << -1 << endl;
    END:

上記は最初の回答です。C++のパワーならいける！
本回答は、

    int N, Y;
    cin >> N >> Y;
    
    for(int i=0; i<=N; i++){
        for(int j=0; j<=(N-i); j++){
            if(Y==i*10000 + j*5000 + (N-i-j)*1000){
                cout << i << " " << j << " " << (N-i-j) << endl;
                goto END;
            }
        }
    }

    cout << -1 << " " << -1 << " " << -1 << endl;
    END:

Nが固定値であり、他の２種類のお札の枚数が決まれば残り１種類の枚数は決まります。
k=(N-i-j)になります。

ABC049C 白昼夢

問題文はatCoderにて読んでください。
与えられた文字列Sと下記４つの単語を組み合わせて作成するTはS＝Tとなりえるか。
"dream" "dreamer" "erase" "eraser"

単語の後にある"er"が問題ですね。
配列を削除するときと一緒で先頭からTを作成していくとできないです。
この手の問題は最後尾から作成します。
この問題はかなり簡単なのでコードは書きません。

ABC086C Traveling

問題文はatCoderにて読んでください。
私は最初に問題のポイントは、

• int型を使用
• ループによる全検索
• X+Y<=T、X、Y座標の合計が時間より大きい場合は成立しない
• 時間が奇数なら移動距離も奇数、偶数なら移動距離も偶数

を考え実装しました。

    int N, ans=0;
    cin >> N;

    for(int i=0; i<N; i++){
        int x,y,t;
        cin >> t >> x >> y;
        
        if(t%2==(x+y)%2){
            if(t>=(x+y)){
                ans++;
            }
        }
    }
    
    if(ans==N){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
 
    return 0;

上記で提出した場合、ACで通りました。
分かった気になっていました。

しかし、この記事を書いている際に、

2
10 1 9
16 1 1

みたいなテスト入力でもACが出てしまいました。
この問題には通過点があります。
前回の地点からの変化量の絶対値に対して今まで考察した条件を適用しないといけません。

    int N, ans=0;
    cin >> N;
    
    int ox=0,oy=0,ot=0;
    
    for(int i=0; i<N; i++){
        int x,y,t;
        cin >> t >> x >> y;
        
        if((t-ot)%2==(abs(x-ox)+abs(y-oy))%2){
            if((t-ot)>=abs(x-ox)+abs(y-oy)){
                ans++;
            }
        }
        ot=t;
        ox=x;
        oy=y;
    }
    
    if(ans==N){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
 
    return 0;

ACにて通りました。
これでAtcoder Begginers Selectionを理解したのではないかと思います。

C問題に求められるものとは

４つの変化する値は、３つ決まれば残り１つは決定する。奇数、偶数に関する理解。最初からではなく最後から処理するなどを咄嗟に見つけることだと思います。
次回はD問題について記載したいと思います。