Yukicoder No.335 門松宝くじ

,

このとき3つの数が門松列になっていたら3つの数の最大値が当選金額となる。

ってのを、3つの数の*総和*が当選金額になる、と誤読してしまった。 誤読後の問題に対しても元々の問題に対してもWAするような解答を投げたのにACしてしまった。 この解説を書いてるときに誤読に気付いた。

No.335 門松宝くじ

解法

それぞれの列に関して期待値を求める。 ランダムに決まる2点を全探索し、自分の決める1点をsegment木で処理する。$O(M N^2 \log N)$。

ランダムに決まる2点を$e_i, e_j$とする。 門松列ができるような$e_k$で$\max \{ e_i, e_j, e_k \}$を最大化するものを見つけたい。 $i < j$かつ$e_i < e_j$として話をする。 門松列とはつまり広義単調増加でない列のことである。よって、

  • $k < i$ ならば
    • $e_k > e_i$ である必要がある。
  • $i < k < j$ ならば
    • $e_i < e_k \land e_k > e_j$ または
    • $e_i > e_k \land e_k < e_j$ である必要がある。
  • $j < k$ ならば
    • $e_j > e_k$ である必要がある。

$\max \{ e_i, e_j, e_k \}$を最大化するので、$\max \{ e_i, e_j \} < e_k$であるかどうかで事を簡単にできる。 以下の4点のみを確認すればよい。

  • $k \in [0,i)$の範囲で最大の$e_k$
  • $k \in (i,j)$の範囲で最大の$e_k$
  • $k \in (i,j)$の範囲で最小の$e_k$
  • $k \in (j,n)$の範囲で最小の$e_k$

最小をのものを求めているものは、$\max \{ e_i, e_j, e_k \}$を最大化したいが制約として$e_k < e_i$や$e_k < e_j$があり、門松列を作るものの存在を確認するだけでよいからである。 それぞれに関してそれが門松列を作るかどうかを判定し、門松列を作るものの中での最大を採用すればよい。 区間に対する最大最小はsegment木で$O(\log n)$である。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <typename T> bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; }
template <typename T>
struct segment_tree { // on monoid
    int n;
    vector<T> a;
    function<T (T,T)> append; // associative
    T unit;
    template <typename F>
    segment_tree(int a_n, T a_unit, F a_append) {
        n = pow(2,ceil(log2(a_n)));
        a.resize(2*n-1, a_unit);
        unit = a_unit;
        append = a_append;
    }
    void point_update(int i, T z) {
        a[i+n-1] = z;
        for (i = (i+n)/2; i > 0; i /= 2) {
            a[i-1] = append(a[2*i-1], a[2*i]);
        }
    }
    T range_concat(int l, int r) {
        return range_concat(0, 0, n, l, r);
    }
    T range_concat(int i, int il, int ir, int l, int r) {
        if (l <= il and ir <= r) {
            return a[i];
        } else if (ir <= l or r <= il) {
            return unit;
        } else {
            return append(
                    range_concat(2*i+1, il, (il+ir)/2, l, r),
                    range_concat(2*i+2, (il+ir)/2, ir, l, r));
        }
    }
};
bool is_kadomatsu(int a, int b, int c) {
    if (a == b or b == c or c == a) return false;
    if (a < b and b < c) return false;
    if (a > b and b > c) return false;
    return true;
}
ll nc2_expected_value(int n, vector<int> const & e) {
    segment_tree<int> mint(n, n+1, [](int a, int b) { return min(a,b); });
    segment_tree<int> maxt(n,   0, [](int a, int b) { return max(a,b); });
    repeat (i,n) {
        mint.point_update(i, e[i]);
        maxt.point_update(i, e[i]);
    }
    ll result = 0;
    repeat (i,n) {
        repeat_from (j,i+1,n) {
            int l, mn, mx, r;
            if (e[i] < e[j]) {
                l  = maxt.range_concat(0,i);
                mn = mint.range_concat(i+1,j);
                mx = maxt.range_concat(i+1,j);
                r  = mint.range_concat(j+1,n);
            } else {
                l  = mint.range_concat(0,i);
                mn = mint.range_concat(i+1,j);
                mx = maxt.range_concat(i+1,j);
                r  = maxt.range_concat(j+1,n);
            }
            int a = 0;
            if (i   != 0 and is_kadomatsu(l,  e[i], e[j])) setmax(a, max(l,  max(e[i], e[j])));
            if (i+1 != j and is_kadomatsu(e[i], mn, e[j])) setmax(a, max(mn, max(e[i], e[j])));
            if (i+1 != j and is_kadomatsu(e[i], mx, e[j])) setmax(a, max(mx, max(e[i], e[j])));
            if (j != n-1 and is_kadomatsu(e[i], e[j],  r)) setmax(a, max(r,  max(e[i], e[j])));
            result += a;
        }
    }
    return result;
}
int main() {
    int n, m; cin >> n >> m;
    vector<vector<int> > e(m, vector<int>(n));
    repeat (y,m) repeat (x,n) cin >> e[y][x];
    vector<ll> a(m); repeat (y,m) a[y] = nc2_expected_value(n, e[y]);
    cout << max_element(a.begin(), a.end()) - a.begin() << endl;
    return 0;
}