【ABC167へ参加してみた】在宅勤務になったのでマネジメント系SEが競技プログラミング始めてみた。#6 -解説も-

今回の記事

ABC167に参加しましたので共有。
今回もB問題までしか解けず。。(..悔しい)
前回と同じくB問題までなので解説も合わせて記載します。

解説に飛ぶ方はこちら

当日の解答結果

今回もB問題しか解けませんでした。。。(泣)

パフォーマンスについて

今回はB問題しか解けていなかったにもかかわらず、思ったよりもパフォーマンスが高かったです。

振り返りと反省

1.解法を考えるまでの時間とコーディング時間が短縮

　現在ABCの過去問をバーチャルコンテストで何個かやっているお陰か、前回よりも解答をコーディングするまでの時間が飛躍的に短くなった気がしてます。
　解ってたけど、毎日やってるとちょっとずつ慣れてくる感覚をしっかり感じることができました。

2.計算量を意識して解法を考えるようになった

　与えられた条件から実行時間超過エラーになりそうな解法を頭の中から切り捨てることができるようになってきました。だいたい10の9乗以上ループを回すことになりそうだと間に合わないなって思えるようになりました。

3.なんとなく解法は解るけど、コーディングできない

　今回C問題はこうやったら良いのかなと思っていたものの、実際にコーディングできないことで結局時間が溶けてしまいました。。
再帰やらDFSやらのページを見てアルゴリズムは理解できたのですが、それを自身で問題に合わせて書くことがまだまだできないなと感じました。

問題解説

今回も残念ながらB問題までしか解けなかったので、B問題までの解説をのせます。

A問題：Registration

問題文抜粋

解説

問題を読むと、「入力Tは入力Sに英小文字を1文字加えたものかどうか」を判定すれば良いことがわかります。
そのため「入力Tの最後の文字を消した文字列は、入力Sと一致する」と読み替えることができます。
その条件で以下のようなコードとなります。

problemA.cpp

#include<bits/stdc++.h>
using namespace std;

int main(void) {
    string S,T;
    cin >> S >> T;

    bool flag = true; //条件にあっているかの判定フラグ
    for(int i=0; i<S.size(); i++){ //Sの文字列サイズ分ループを回す
        if(S[i] != T[i])　//SとTのi番目の文字列を判定する
          flag = false;　 //SとTのi番目の文字列が一致してないとfalse
    }

    if(flag)
      cout << "Yes" << endl;
    else
      cout<<"No" <<endl;

    return 0;
}

ちなみにAtcoderの解説動画でもあったのですが、
文字列は「pop_back」を使うともう少し簡単に書けることがわかりました。
pop_backは最後尾の文字を抜き取るので、結果的にSとTの文字列を比較するだけで今回の条件にあっているか判定をすることができます。

problemA.cpp　別解

#include<bits/stdc++.h>
using namespace std;

int main(void) {
    string S,T;
    cin >> S >> T;
    T.pop_back(); //文字列Tの最後尾を抜き取る ex)abc →　ab

    if(S==T)
      cout << "Yes" << endl;
    else
      cout<<"No" <<endl;

    return 0;
}

B問題：Easy Linear Programming

問題文抜粋

解説

問題を読むとこんなイメージです。

この中からK枚のカードを選んで合計値が最大になるように選びます。
当然、A枚→B枚→C枚と選んで行った方が合計値が最大になります。
ただし、K枚という枚数がわからないので以下のようにパターンを考える必要あります。

- 条件１：K<Aのとき
　この場合はAよりもKが小さいので、「１」のカードをK枚選ぶこととなります。
- 条件２；A≦K≦A+Bのとき
　この場合はA＋BよりもKが小さいです。そのため「１」のカードと「０」のカードを選ぶこととなります。ただし、「０」のカードはいくら足しても「０」なので、枚数が何枚だろうが関係ありません。
　そのためこの場合は「１」のカードをA枚選ぶことと同じになります。
- 条件３：K>A+Bのとき
　この場合はKがA+Bよりも大きいため「−１」のカードを選択することになります。「−１」のカードの枚数は「K-(A+B)」となります。

それらを元にコードを書くと以下のようになります。

problemB.cpp

#include<bits/stdc++.h>
using namespace std;

int main(void) {
    long long int A,B,C,K;
    long long int ans=0;
    cin >> A >> B >> C >> K;

    if(K<A)　//条件１のとき
      ans = K;
    else if(K=>A && K<=A+B) //条件２のとき
      ans = A;
    else if(K>A+B)　//条件３のとき
      ans = A+(-1)*(K-A-B); //-1のカードは{K-(A+B)}枚

    cout << ans << endl;

    return 0;
}

今後に向けて

C問題が３連続で解けませんでした。。
ただB問題までの解答速度や精度が高くなってきたことを実感してきたので
引き続き過去問を解いていきたいと思います。
そしてそろそろアルゴリズムの実装を勉強せねば。。。

最後に

いかがだったでしょうか？
見ても解らないやもう少しこうすると良いのではないか？といった暖かい言葉ドシドシお待ちしています。