AtCoder Beginner Contest 149 - zeronosu77108’s blog

はい． 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)$ 枚です．
そんな感じです．

$0$ と max 取ってるのは，負数になったときの対応です．

#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;
}