AtCoder Grand Contest 004: B - Colorful Slimes

,

http://agc004.contest.atcoder.jp/tasks/agc004_b

誤読していた。 変色の際に元の色のスライムも残るのだと思っていた。 この条件だと$O(N^3)$までしか落とせなかったが、両端繋がってないことにすると$O(N^2)$なはず。 元の問題だと両端繋がってないことにしても$O(N)$にはならない気がするのでちょっと面白い。

solution

魔法を唱える回数$k$を総当たり。最終的な色$i$のスライムがどの色のスライムとして捕まえられるべきかは$\min \{ a_j \mid i - k \le j \le i \}$を使って求まる。$O(N)$。

implementation

sparse tableである必要はない。

#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

template <class Monoid>
struct sparse_table {
    typedef typename Monoid::underlying_type underlying_type;
    vector<vector<underlying_type> > table;
    Monoid mon;
    sparse_table() = default;
    sparse_table(vector<underlying_type> const & data, Monoid const & a_mon = Monoid())
            : mon(a_mon) {
        int n = data.size();
        int log_n = log2(n) + 1;
        table.resize(log_n, vector<underlying_type>(n, mon.unit()));
        table[0] = data;
        for (int k = 0; k < log_n-1; ++ k) {
            for (int i = 0; i < n; ++ i) {
                table[k+1][i] = mon.append(table[k][i], i + (1ll<<k) < n ? table[k][i + (1ll<<k)] : mon.unit());
            }
        }
    }
    underlying_type range_concat(int l, int r) const {
        if (l == r) return range_concat(0, table[0].size());
        if (l > r) return mon.append(
                l == table[0].size() ? mon.unit() : range_concat(l, table[0].size()),
                r == 0 ? mon.unit() : range_concat(0, r));
        assert (0 <= l and l <= r and r <= table[0].size());
        if (l == r) return mon.unit();
        int k = log2(r - l);
        return mon.append(table[k][l], table[k][r - (1ll<<k)]);
    }
};
struct min_t {
    typedef int underlying_type;
    int unit() const { return INT_MAX; }
    int append(int a, int b) const { return min(a, b); }
};

constexpr ll inf = ll(1e18)+9;
int main() {
    // input
    int n, x; scanf("%d%d", &n, &x);
    vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
    // solve
    sparse_table<min_t> rmq(a);
    ll result = inf;
    repeat (k, n) {
        ll acc = x *(ll) k;
        repeat (i, n) {
            acc += rmq.range_concat(i, (i + k + 1) % n);
        }
        setmin(result, acc);
    }
    // output
    printf("%lld\n", result);
    return 0;
}