AtCoder Beginner Contest 342 振り返り

ABC342

概要

A - Yay!

考えてたこと
結構悩んだ。あまり良い解法が思いつかなくて1文字目と他の文字を比較して一つだけ違うものがあればそれを出力、無ければ1文字目という感じで強引に解決。

提出したもの

a.cpp

int main() {
    string s;
    cin >> s;
    char first = s[0];
    int ans;
    int cnt = 0;
    for (int i = 0; i < s.size(); i++) {
        if (first != s[i]) {
            ans = i + 1;
            cnt++;
        }
    }
    if (cnt > 1) {
        ans = 1;
    }
    cout << ans << endl;
    return 0;
}

振り返り
解答見たら二重for文で片方の文字を固定して全ての文字と比較するという方法でした。綺麗なやり方で好き。

B - Which is ahead?

考えてたこと
i番目の人がPiというのをmapに保存して後は比較して終わり。
頭の中で整理するのにちょっと時間がかかったけど、最近似たようなmapを使うd問題を解いてたから解けた感じ。

提出したもの

b.cpp

int main() {
    int n;
    cin >> n;

    map<int, int> map;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        map[num] = i;
    }
    int q;
    cin >> q;
    rep(i, 0, q) {
        int a, b;
        cin >> a >> b;
        if (map[a] > map[b]) {
            cout << b << endl;
        } else
            cout << a << endl;
    }
    return 0;
}

振り返り
慣れなのかもしれないけど、こういう項目が複数ある問題頭がごちゃごちゃになっちゃうからもっと早く解けるようになりたい。

C - Many Replacement

考えてたこと
全ての文字を毎回変換したら計算量がNQで410**10でTLEになるので何かしら工夫をする必要があると判断。
サンプルケースみたり少ない文字で考えてみて、この文字はこの文字になる、みたいな情報だけ保持して最後にまとめて判断すれば良いんじゃないか...?と考えて実装したらAC。

提出したもの

c.cpp

int main() {
    int n, q;
    string s;
    cin >> n >> s >> q;

    map<char, char> map;
    rep(i, 0, q) {
        char a, b;
        cin >> a >> b;
        if (!(map.count(a))) {
            map[a] = b;
        }
        fore(x, map) {
            if (x.second == a) {
                x.second = b;
            }
        }
    }
    fore(a, s) {
        if (map.count(a)) {
            cout << map[a];
        } else
            cout << a;
    }
    return 0;
}

振り返り
コードはかなり違うけどやってること自体は模範解答と大体同じそう。最近C問題に関しては全探索した時の計算量がいくらかっていう点から工夫して解く必要があるかどうかということを考えるようになったの良い傾向な気がする。

D - Square Pair

考えてたこと
かなり悩んだ問題。まず計算量を考えて全パターンを試したらN*(N-1)/2で計算量が足りないと考えて何かしら工夫する必要があると判断。とはいえ、最初はどうやって平方数か判断するかも分からずかなり迷走。
小さい数で色々試した結果、全ての値を割り切れる最大の平方数で割って同じ値のものを組み合わせたら解になると気づいてその方針で実装。
(例えば12の場合223なので3とする。同じ処理をして3になる、3や108(22333)などと組み合わせた時平方数になる。)

提出したもの

d.cpp

int main() {
    ll n;
    cin >> n;
    // ここのmapを<int,int>にしてるとWAになる。
    // 下のmap.second*(map.second-1)のところでintの範囲超えそう
    // map.secondの最大値がnのため、n**2で4*10**10になる。
    map<int, ll> map;
    for (ll i = 0; i < n; i++) {
        ll a;
        cin >> a;
        if (a != 0) {
            for (int i = sqrt(200000) + 1; i > 0; i--) {
                if (a % (i * i) == 0) {
                    a /= (i * i);
                }
            }
        }

        if (map.count(a)) {
            map[a]++;
        } else {
            map[a] = 1;
        }
    }

    ll ans = 0;
    fore(a, map) {
        if (a.first == 0) {
            for (ll i = 1; i <= a.second; i++) {
                ans += n - i;
            }
        } else {
            ans += a.second * (a.second - 1) / 2;
        }
    }
    cout << ans << endl;
    return 0;
}

振り返り
方針自体は合っていたが数値が0の時の処理、intの範囲を超えるケースがあること、などで実装が手間取り最終的に7WAからのAC。
方針を思いつけたのは良かったが0の時など例外の値の処理は気を付けていきたい。int, long longに関してはもっと初歩的なことだし二乗の計算をする時はそれがintの範囲内で収まるか考える癖をつける必要がある。

感想

最近、自力でD問題まで解けることが多くて嬉しい。多分、コンテスト参加じゃなくてゆっくり落ち着いて時間をかけられてるからだと思うけど。あとはこれをコンテストでも出せるぐらい実践値を上げていきたい。