📝

【ABC257】「C - Robot Takahashi」のメモ

2022/07/18に公開

AtCoder

競プロ

tech

概要

日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257）でC問題が解けなかったので、解説を見て得られた知見などを書いておきます。

コンテスト中に書いたコード

この問題では実数Xについては何の制約も設けられていませんでした。計算量を考えなければ、Wの最小値から最大値までの整数についてXと仮定してチェックしていけば解けます。
NとWの制約が大きいので明らかにTLEになりそうですし、求めるべき答えはXの最大値ではなくあくまでもf(X)の最大値なので、Xのパターンを調べていくアプローチが明らかに間違ってそうな雰囲気はありましたが、他に方法が思いつかなかったのでとりあえず愚直に実装してみました。
制約が大きい中での2重ループなのでもちろんTLEでした。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    string S;
    cin >> S;

    vector<int> W(N);

    int mx = -1;
    int mn = 999999999;
    for(int i = 0; i < N; i++) {
        int w;
        cin >> w;
        W.at(i) = w;
        mx = max(mx, w);
        mn = min(mn, w);
    }
    mx++;

    int ans = 0;
    for(int i = mn; i <= mx; i++) {
        int count = 0;
        for(int j = 0; j < N; j++) {
            int w = W.at(j);
            char ad = S.at(j);
            if(w < i && ad == '0') {
                count++;
            } else if(w >= i && ad == '1') {
                count++;
            }
        }
        ans = max(ans, count);
    }

    cout << ans << endl;
}

解説を見て

Xに惑わされていましたが、実際にはXとか関係なく求められるようでした…
もしくは、2人の間に引く線がXと考えるか。
解説を受けて書いたコードは以下です。

#include <bits/stdc++.h>
using namespace std;

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

    vector<pair<int, char>> v;

    int cnt = 0;
    for(int i = 0; i < n; i++) {
        int w;
        cin >> w;
        char c = s.at(i);

        if(c == '1') cnt++;

        v.push_back({w, c});
    }

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

    int ans = cnt;
    for(int i = 0; i < n; i++) {
        if(v.at(i).second == '1') {
            cnt--;
        } else {
            cnt++;
        }
        if(i == n - 1 || v.at(i).first != v.at(i + 1).first) {
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;
}

体重と大人かどうかのフラグをセットで扱う必要があるためpairを使っています。そのままソート可能です。
cnt はその時点で正しく判定できている人数です。最初は全員を大人と判定するため、大人の人数が正しく判定できている人数です。
for文のループカウンタは線ではなく、線を右に移動させたときに左側に移動した人を指しています。その人が大人だった場合、今まで正しく大人と判定していたのに子供と判定するようになってしまったということなので、正しく判定できている人数を減らします。その人が子供だった場合はその逆です。
解説に「体重が等しい 2 人を高橋君は区別できないため、その間には線を引けない事に注意してください」とあるので、その考慮を入れています。 ans を更新しなければ実質スキップできます。ただし、正しく判定できている人数は更新する必要はあります。
i == n - 1 は配列の範囲外を参照しないためのガードです。また、体重が同じ人が最後だった場合の ans の更新漏れも防げます。

教訓

本番ではソートせずに考えていましたが、とりあえずソートしてみるとかすれば解法を発想していた可能性がなきにしも非ず、ということで数列が来たら必要性がよくわからずともとりあえずソートしてみるというのを今後は考えてみます。

制約がない変数についてはあまり考えない
数列が来たらとりあえずソートしてみる

概要

コンテスト中に書いたコード

解説を見て

教訓

Discussion