｢AtCoder Beginner Contest 149｣に出た

tags: 競技プログラミング

コンテストへのリンク

https://atcoder.jp/contests/abc149/tasks

感想

• Unrated
• 意味なし

A問題

https://atcoder.jp/contests/abc149/tasks/abc149_a

• SとTを入力してTとSを出力する

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
#define all(obj) (obj).begin(), (obj).end()
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

signed main()
{
    string S, T;
    cin >> S >> T;
    cout << T << S << endl;
    return 0;
}

B問題

https://atcoder.jp/contests/abc149/tasks/abc149_b

• 何故かこの問題でミスった...
• 2回も間違えてしまった
• 順番に考えると普通に答えが出るはずです

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
#define all(obj) (obj).begin(), (obj).end()
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

signed main()
{
    ll A, B, K;
    cin >> A >> B >> K;
    if (K < A) {
        cout << A - K << " " << B << endl;
    } else if (B - (K - A) > 0) {
        cout << 0 << " " << B - (K - A) << endl;
    } else {
        cout << 0 << " " << 0 << endl;
    }
    return 0;
}

C問題

https://atcoder.jp/contests/abc149/tasks/abc149_c

• 素数判定をします
• これをXからやれば良いだけです

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
#define all(obj) (obj).begin(), (obj).end()
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

bool isPrime(int num)
{
    if (num < 2)
        return false;
    else if (num == 2)
        return true;
    else if (num % 2 == 0)
        return false;

    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

signed main()
{
    ll X;
    cin >> X;
    while (true) {
        if (isPrime(X)) {
            cout << X << endl;
            return 0;
        }
        ++X;
    }
    return 0;
}

D問題

• これには無駄に時間を使ってしまった
• 答え自体はすぐに出たがそれを証明するのに時間がかかりました
• $i = [K, N)$で考えます
  • K文字ごとに同じ文字があるとして貪欲にT[i-K]==T[i]となるようなT[i]で負けるかあいこになるようにすれば良いです
  • あいこか負けのときは得られる点数が0になり,どちらでも点数的には同じです
  • なので次のK文字後の文字と同じにならないような手にすれば良いだけです`
• こう考えると全部勝ったときに得られる得点から変更する文字の分だけ引けば良いです
  • 僕は最後に変更していない部分で足すようにしました(そこら辺は好みで)

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
#define all(obj) (obj).begin(), (obj).end()
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;
ll N, K;
ll R, S, P;
string T;

signed main()
{
    cin >> N >> K;
    cin >> R >> S >> P;
    cin >> T;
    ll res = 0;
    string str = "";
    rep(i, N)
    {
        if (T[i] == 'r') { // P
            str += "p";
        } else if (T[i] == 's') { // R
            str += "r";
        } else { // S
            str += "s";
        }
    }
    for (int i = K; i < N; ++i) {
        if (str[i - K] == str[i]) {
            str[i] = '*';
        }
    }
    rep(i, N)
    {
        if (str[i] == 'p') {
            res += P;
        } else if (str[i] == 'r') {
            res += R;
        } else if (str[i] == 's') {
            res += S;
        }
    }
    cout << res << endl;
    return 0;
}

次回への反省

• 今回の反省はB問題でWAしたのとD問題が20分で解けなかったこと
• B問題に関しては簡単な問題は丁寧に解くということを心がけるようします
• D問題に関してはもっとノートを使って考察をするべきでした
  • 音楽聞きながらするのはやめる