SRM 680 Div2 Easy, Medium

Easy(250): BearPair

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14130

解法

全探索。

class BearPair {
    public:
    int bigDistance(string s) {
        int ans = -1;
        int n = s.size();
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i == j) continue;
                if(s[i] != s[j]) ans = max(ans, abs(i-j));
            }
        }
        return ans;
    }
};

243pt くらい

Medium(500): BearCharis

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14131

熊は最低 d の間隔を空けて座らなければならない。 i 番目に来客の熊は atLeast[i] 以上に座る。 熊が座れる最小の席番号を返す。

解法

来客した熊(atLeast[i])について、既に座ってる熊で席番号の小さい順(st[j])(j<i)から見ていき、パーソナルスペースが被る

なら atLeast[i] = st[j] + d に更新していく。

class BearChairs {
    public:
    vector<int> findPositions(vector<int> a, int d) {
        int N = a.size();
        vector<int> ans;
        vector<int> st; // 決まった席(ans)をソートしたもの
        ans.push_back(a[0]);
        st = ans;
        for(int i=1; i<N; i++) {
            for(int j=0; j<(int)st.size(); j++) {
                if(st[j] - d + 1 <= a[i] and a[i] <= st[j] + d - 1) a[i] = st[j] + d;
            }
            ans.push_back(a[i]);
            st = ans;
            sort(st.begin(), st.end());
        }

        return ans;
    }
};

本番では変なことして落ちました（上のソースは正しいです）。

結果

Rating: 537 → 619 (+82)

div2 easy でも難しいと思ってたけど最近毎日過去問題を解いてたらだいぶ楽になってきた。Med はつらい。