ABC137振り返り

ABC137の振り返りをしていきます．今回はC問題も解けず，，，まだまだ使える典型の種類が足りてないなとおもいます．．．

A問題

これはさすがにそのまま書くだけでした．特に何もないです．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    int A, B; cin >> A >> B;
    int p = A + B, s = A - B, m = A * B;

    cout << max(p, max(s, m)) << endl;
    return 0;
}

B問題

制約から範囲がはみ出す可能性はないので，これも素直に書きました．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    int K, X; cin >> K >> X;

    for (int i = X - K + 1; i < X + K; i++) {
        cout << i;
        if (i != X + K - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

C問題

解けなかったです．．．

とりあえず，アナグラムを判定する部分と組み合わせを考える部分で分けて考えました．アナグラムの判定は，あらかじめ文字列をソートしておくと定数時間で実行できるので，問題なかったです．

アナグラムになっている文字列をグループ分けしてあげて，同じグループに個の文字列があるときに，の総和を出せばいいことに終了１０分前くらいに気づきました．

グループ分けは，文字列の配列をソートしてO(NlogN)，前から順にO(N)でみていけばよかったので，あとはの総和をとって提出！！したのですが，最後のテストケースだけWAでした．後から考えてみると，組み合わせをで割った余りを出してしまっていたのでそれが原因だと思います．

アナグラムである文字列の個数の数え方も，単純に足して行って，違う文字列がでてきたらリセットでよかったんですが，配列やらフラグやらをこねくり回してわかりにくくなってます．

解説によれば，同じ文字列の個数を数える際は，ハッシュを使うと高速にできるみたいです（検索も追加も平均O(1) ??全てのデータが衝突したとしてO(N)）．C++ではunordered_mapで使えます．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;
    vector<string> s(N);

    for (int i = 0; i < N; i++) {
        string st; cin >> st;
        sort(st.begin(), st.end());
        s[i] = st;
    }

    sort(s.begin(), s.end());

    bool prev = false;
    vector<int> res;
    for (int i = 0; i < N-1; i++) {
        bool flag = true;
        for (int j = 0; j < 10; j++) {
            if (s[i][j] != s[i+1][j]) flag = false;
        }
        if (flag) {
            if (prev) {
                res[int(res.size())-1] += 1;
            } else {
                res.push_back(2);
            }

            prev = true;
        } else {
            prev = false;
        }
    }
    ll ans = 0;
    for (int i = 0; i < res.size(); i++) {
        ans += ll(res[i]) * (res[i] - 1) / 2;
    }

    cout << ans << endl;
    return 0;
}

D問題

C問題が解けそうで解けなかったのでこっちも目を通しましたが，こっちも解けなかったです．．．

時間がたつにつれてできる仕事の選択肢は減っていく（制約が厳しくなっていく）ので，こういう場合は制約が厳しい方から考えるのが定石みたいです．例えば時刻tのときを考えると，選べる仕事はM - t以内に報酬が振り込まれるものになるので，その中で報酬が最大のバイトを選べば良いみたいです．

これに気づいても，愚直に最大値を調べるとO(N^2)かかると思うのですが，毎回選ぶのは最大値なのでpriority_queueを使うと，要素の追加がO(N)，最大値を取り出すのがO(M)，それぞれの操作はO(logN)かかるのでO((M+N)logN)で計算できます．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <queue>

using namespace std;

typedef long long ll;

int main() {
    int N, M; cin >> N >> M;
    vector<pair<int, int>> v(N);

    for (int i = 0; i < N; i++) {
        int a, b; cin >> a >> b;
        v[i].first = a;
        v[i].second = b;
    }
    sort(v.begin(), v.end());

    priority_queue<int> q;

    int idx = 0;
    int ans = 0;
    for (int t = 0; t <= M; t++) {
        while (idx != N && v[idx].first <= t) {
            q.push(v[idx].second);
            idx++;
        }

        if (!q.empty()) {
            ans += q.top();
            q.pop();
        }
    }

    cout << ans << endl;
    return 0;
}

まとめ

まずは最低でもCまでは確実に解けるようにしていきたいです