SHIINBLOG

AtCoder Beginner Contest 149

はい. AtCoder Beginner Contest 149 です
本当は ABC146,147 を先に書かないといけないんですけど,このままだと永遠にスタックされていきそうなので,とりあえず ABC149 について書きます.
ABC148の記事 のときにも言ってた気がする…

Unrated になってしまって残念ですが,一応 ABCDの4完でした.
そんなに難しくなかったかな?
参考までに順位表を

f:id:zeronosu77108:20191229215713p:plain

A 問題を勘違いして 1度  S ~ T の順で提出してしまったのが辛いですね.


A - Strings

問題文

文字列を連結して出力するだけです.
※順番は間違えないように

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;


int main() {
    string s,t;
    cin >> s >> t;
    cout << t << s << endl;
}



B - Greedy Takahashi

問題文

高橋君のクッキーを食べられるだけ食べて,次に青木君のクッキーを食べられるだけ食べる.

高橋君の食べるクッキーが  A - K枚で,青木君が食べるクッキーが  B - (K-A) 枚です.
そんな感じです.

 0max 取ってるのは, 負数になったときの対応です.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;


int main() {
    int64 a,b,k;
    cin >> a >> b >> k;
    cout << max(0LL, a - k) << " ";
    cout << max(0LL, b - max(0LL, k-a)) << endl;
}



C - Next Prime

問題文

 X 以上の素数のうち最小のものを出力してくださいというシンプルな問題.
エラストテネスのふるい で素数列挙して求めました.

 2X まで探索すれば  X 以上の素数は見つかるだろうと思ってましたが,
どれくらい探索したら良いのかよく分かっていません.

素数列挙出来たら,素数vector から lower_bound するだけです.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;

vector<int64> Eratosthenes(  int64 N )
{
    N *= 2;
    vector<int64> p;
    vector<bool> is_prime(N+1, true);
    for( int i = 2; i <= N; i++ )
    {
        if( is_prime[ i ] )
        {
            for( int j = 2 * i; j <= N; j += i )
            {
                is_prime[ j ] = false;
            }
            p.emplace_back( i );
        }
    }
    return p;
}

int main() {
    int64 x;
    cin >> x;
    vector<int64> ans = Eratosthenes(x);
    cout << *lower_bound(ans.begin(), ans.end(), x) << endl;
}



D - Prediction and Restriction

問題文

感覚的に,rrr とかになったときに奇数番目を勝つように選んでいけば良さそうと思って実装しました(  K=1 以外でも).
通りました.

実装に関しては.もう少しましな方法があった気もしますが,map<char, int> で,
win['r'] みたいな感じでアクセスできるようにしました.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;



int main() {
    int n,k,r,s,p;
    int64 ans = 0;
    string t;

    cin >> n >> k;
    cin >> r >> s >> p;
    cin >> t;

    map<char, int64> win;
    win['r'] = p;
    win['p'] = s;
    win['s'] = r;


    vector<vector<int64>> dp(n+1, vector<int64> (3, 0));

    for (int i=0; i<n; i++) {
        if (i < k) ans += win[t[i]];
        else if (t[i-k] != t[i]) ans += win[t[i]];
        else t[i] = '-';
    }

    cout << ans << endl;
}



E - Handshake

問題文

なんか二分探索っぽい雰囲気を感じたんですけど,その他の実装が 1ミリも思い浮かばなかったので実装出来ませんでした.

最近,レート下がりすぎて悔しいので,近いうち勉強してプログラムと解説載せます.

まとめ

Unrated になったのが悲しかったです.
次までに精進します.