AtCoder Beginner Contest 119(ABC119) 解説

ABC

AtCoder Problemsによると、C,Dの2問が水色diffと少し重ためコンテストです。

A – Still TBD

A - Still TBD
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

2019年の実在する日付がyyyy/mm/ddで与えられる。それが4月30またはそれ以前かどうかを出力する問題。
4月30日に次の日は5月1日です。また、入力は2019年であることが決まっています。
上記より、mmの部分が1～4月か、5～12月かを見て判断すればいいです。
C++ならsubstr関数で部分文字列を取得できます。

#include<bits/stdc++.h>

using namespace std;

int main(){
    string S;
    cin>>S;

    int m=stoi(S.substr(5,2));
    if(m<=4) cout<<"Heisei"<<endl;
    else cout<<"TBD"<<endl;
}

B – Digital Gifts

B - Digital Gifts
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

N個のx,uが与えられる、xの総和を求めよ。ただし、uがBTCの時はxに380000を掛けてましょう。
ちょっと誤差が怖いですが、特に気にせずに問題文通りの実装でOKでした。
なお、相対誤差が10^-5以下の時に正解なため、下記のようなコードでも通ります。

#include<bits/stdc++.h>

using namespace std;

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

    double ans=0;
    for(int i=0;i<N;i++){
        double x;
        string u;
        cin>>x>>u;
        if(u=="BTC") x*=380000.0;
        ans+=x;
    }

    printf("%.10f111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\n",ans);
}

だからって何だって話だとは思います。

C – Synthetic Kadomatsu

C - Synthetic Kadomatsu
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

競プロの門松問題は難問が多い気がします。
N本の竹のうち、どれか1本の長さを1増やす(MP1消費)、どれか1本の長さを1減らす(MP1消費)、2本の竹の長さを合わせる(MP10消費)
を好きなだけ行い、A,B,Cの長さを持つ竹を作るとき、MPの消費を最小にする問題。

問題は、どの竹とどの竹を組み合わせて最適にするかだと思います。
N=8と竹の数が少ないです。
すべての竹の組み合わせを試しても、N=8時点で8C2*7C2*6C2*5C2*4C2=529200通りです(多分)
時間的にかなり余裕があるため、全通りの竹の組み合わせを試してみて、その竹の中からA,B,Cを伸ばしたり縮んだりして作成するときの最小を取ればOKです。

#include<bits/stdc++.h>

using namespace std;
int N,A,B,C;
vector<int> ABC;
int ans;

void calc(vector<int> vl,int c,int n,int cnt){
    if(c==ABC.size()){
        ans=min(ans,cnt);
        return;
    }
    for(int i=n;i<vl.size();i++){
        calc(vl,c+1,i+1,cnt+abs(ABC[c]-vl[i]));
    }
}
void dfs(vector<int> vl){
   sort(vl.begin(),vl.end());
   calc(vl,0,0,(N-vl.size())*10);
   if(ABC.size()==vl.size()) return;
   for(int i=0;i<vl.size();i++){
       for(int j=i+1;j<vl.size();j++){
           vector<int> nx;
           nx.push_back(vl[i]+vl[j]);
           for(int k=0;k<vl.size();k++){
               if(k!=i&&k!=j) nx.push_back(vl[k]);
           }
           dfs(nx);
       }
   }
}
int main(){

    vector<int> vl;

    cin>>N>>A>>B>>C;

    ABC.push_back(A);
    ABC.push_back(B);
    ABC.push_back(C);
    sort(ABC.begin(),ABC.end());
    for(int i=0;i<N;i++){
        int l;
        cin>>l;
        vl.push_back(l);
    }
    ans=INT_MAX;

    dfs(vl);

    cout<<ans<<endl;
}

ちなみに想定解はかなり賢いです。
N本の竹をAに使う、Bに使う、Cに使う、使わないの4通りに分けて、全4^8(=65536)通りの最小を取っています。
解答コードがとてもきれいですね。

D – Lazy Faith

D - Lazy Faith
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

神社の座標A個、寺の座標B個が与えられる。
神社1社と寺1軒訪れる際の最小の移動距離を求めよ。
スタート地点はxでQ個与えられるので、それぞれのケースでの最小を求めよ。

神社1社と寺1軒と、両方1つしか訪れる必要がありません。
そのため、以下の8パターンのうちの最小を取ればいいです。

  1. 左にある神社→左にある寺の順に訪れる
  2. 左にある神社→右にある寺の順に訪れる
  3. 右にある神社→左にある寺の順に訪れる
  4. 右にある神社→右にある寺の順に訪れる
  5. 左にある寺→左にある神社の順に訪れる
  6. 左にある寺→右にある神社の順に訪れる
  7. 右にある寺→左にある神社の順に訪れる
  8. 右にある寺→右にある神社の順に訪れる

Q=10^5、A,B=10^5なので、線形探索はTLEします。
左や右にある寺や神社を探す際は2分探索しましょう。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int A,B,Q;
    cin>>A>>B>>Q;

    long long s[A];
    long long t[B];

    for(int i=0;i<A;i++){
        cin>>s[i];
    }
    for(int i=0;i<B;i++){
        cin>>t[i];
    }


    for(int i=0;i<Q;i++){
        long long ans=LLONG_MAX;
        long long x;
        cin>>x;

        auto lb=lower_bound(s,s+A,x);
        int idx=lb-s;
        if(idx!=A){
            auto lb2=lower_bound(t,t+B,s[idx]);
            int idx2=lb2-t;
            if(idx2!=B){
                ans=min(ans,abs(x-s[idx])+abs(s[idx]-t[idx2]));
            }
            if(idx2!=0){
                idx2--;
                ans=min(ans,abs(x-s[idx])+abs(s[idx]-t[idx2]));
            }
        }
        if(idx!=0){
            idx--;
            auto lb2=lower_bound(t,t+B,s[idx]);
            int idx2=lb2-t;
            if(idx2!=B){
                ans=min(ans,abs(x-s[idx])+abs(s[idx]-t[idx2]));
            }
            if(idx2!=0){
                idx2--;
                ans=min(ans,abs(x-s[idx])+abs(s[idx]-t[idx2]));
            }
        }

        lb=lower_bound(t,t+B,x);
        idx=lb-t;
        if(idx!=B){
            auto lb2=lower_bound(s,s+A,t[idx]);
            int idx2=lb2-s;
            if(idx2!=A){
                ans=min(ans,abs(x-t[idx])+abs(t[idx]-s[idx2]));
            }
            if(idx2!=0){
                idx2--;
                ans=min(ans,abs(x-t[idx])+abs(t[idx]-s[idx2]));
            }
        }
        if(idx!=0){
            idx--;
            auto lb2=lower_bound(s,s+A,t[idx]);
            int idx2=lb2-s;
            if(idx2!=A){
                ans=min(ans,abs(x-t[idx])+abs(t[idx]-s[idx2]));
            }
            if(idx2!=0){
                idx2--;
                ans=min(ans,abs(x-t[idx])+abs(t[idx]-s[idx2]));
            }
        }
        cout<<ans<<endl;
    }

}

実務というかアプリを作る際は共通処理は関数化するのですが、競プロだと迷うことがあります。
この問題も66行目の

auto lb2=lower_bound(s,s+A,t[idx]);

が

auto lb2=lower_bound(s,s+B,t[idx]);

になってWAとREを量産していました。
(困ったことにローカル環境ではサンプルがACになったため、気づきませんでした…)

関数化すれば、こういったミスも減らせるのですが、
関数化するにしてもしっかりと設計しないと逆にバグの温床になったり、作るのに手間取ったりします。
競プロの場合は、しっかりと見極めが必要ですね…。
(ちなみに想定解法はfor文を使って上手いことやっていました。賢い＞ ＜)

おわりに

競プロをやるうえで、バグが少なく早く書くコードは大事です。
マクロは抵抗があるので使いたくはないのですが….。
C問題のように、考え方で楽に実装できるケース
D問題のように、for文等を適切に使って楽に実装できるケース
この辺りは頑張っていきたいですね…。

コメント

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