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;
}