2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-05-11

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

解説に飛ぶ方はこちら

#当日の解答結果
今回もB問題しか解けませんでした。。。(泣)
スクリーンショット 2020-05-11 10.15.05.png

#パフォーマンスについて
今回はB問題しか解けていなかったにもかかわらず、思ったよりもパフォーマンスが高かったです。
スクリーンショット 2020-05-11 10.30.39.png

#振り返りと反省
#####1.解法を考えるまでの時間とコーディング時間が短縮
 現在ABCの過去問をバーチャルコンテストで何個かやっているお陰か、前回よりも解答をコーディングするまでの時間が飛躍的に短くなった気がしてます。
 解ってたけど、毎日やってるとちょっとずつ慣れてくる感覚をしっかり感じることができました。
#####2.計算量を意識して解法を考えるようになった
 与えられた条件から実行時間超過エラーになりそうな解法を頭の中から切り捨てることができるようになってきました。だいたい10の9乗以上ループを回すことになりそうだと間に合わないなって思えるようになりました。
#####3.なんとなく解法は解るけど、コーディングできない
 今回C問題はこうやったら良いのかなと思っていたものの、実際にコーディングできないことで結局時間が溶けてしまいました。。
再帰やらDFSやらのページを見てアルゴリズムは理解できたのですが、それを自身で問題に合わせて書くことがまだまだできないなと感じました。

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

問題文抜粋 スクリーンショット 2020-05-11 11.27.42.png
###解説 問題を読むと、「入力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

問題文抜粋 スクリーンショット 2020-05-11 11.27.32.png
###解説 問題を読むとこんなイメージです。 スクリーンショット 2020-05-11 11.53.40.png この中からK枚のカードを選んで合計値が最大になるように選びます。 当然、A枚→B枚→C枚と選んで行った方が合計値が最大になります。 ただし、K枚という枚数がわからないので以下のようにパターンを考える必要あります。 スクリーンショット 2020-05-11 11.53.45.png - **条件1:KA+Bのとき**  この場合はKがA+Bよりも大きいため「−1」のカードを選択することになります。「−1」のカードの枚数は「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) //条件1のとき
      ans = K;
    else if(K=>A && K<=A+B) //条件2のとき
      ans = A;
    else if(K>A+B) //条件3のとき
      ans = A+(-1)*(K-A-B); //-1のカードは{K-(A+B)}枚

    cout << ans << endl;

    return 0;
}

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

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

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?