# ARC183-C Not Argmax

2018diff
https://atcoder.jp/contests/arc183/tasks/arc183_c

## 解法

適切に前計算を行っておくことで、「$N$をおいてはいけない場所」がわかる。$N$を置いて良い場所を一つ固定して($i$)、そこに$N$を置いたとする。そうすると$L_{j}\le i\le R_{j}$なる区間の条件はすべて無視して良いことになる。なぜならそのような区間の$\text{argmax}$は$\{ i\}$だから。

結局の所$i$を固定すると$(P_{1}, P_{2}, \dots, P_{i - 1})$と$(P_{i + 1}, P_{i + 2}, \dots, P_{N})$それぞれについて同様の問題を解くことに帰着する。これは区間DPをやれば良いという兆し。

DPの計算と入力を受け取るのがボトルネックで、 $\Theta (N^{3} + M)$

## 実装

#include <bits/stdc++.h>

const long long MOD{998244353};
const int MAX{510};
long long comb[MAX][MAX];

long long add(long long a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

long long mul(long long a, long long b) {
    return a * b % MOD;
}


int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    for (int i{} ; i < MAX ; i++) comb[i][0] = comb[i][i] = 1;
    for (int i{1} ; i < MAX ; i++) for (int j{1} ; j < i ; j++) 
        comb[i][j] = add(comb[i - 1][j - 1], comb[i - 1][j]);

    int N, M;
    std::cin >> N >> M;
    std::vector ng(N, std::vector(N + 1, std::vector<bool>(N)));
    for (int i{} ; i < M ; i++) {
        int L, R, X;
        std::cin >> L >> R >> X;
        L--; X--;
        ng[L][R][X] = true;
    }
    for (int len{1} ; len <= N ; len++) {
        for (int l{} ; l + len <= N ; l++) {
            int r{l + len};
            if (l) {
                for (int i{l} ; i < r ; i++) ng[l - 1][r][i] = ng[l - 1][r][i] | ng[l][r][i];
            }
            if (r < N) {
                for (int i{l} ; i < r ; i++) ng[l][r + 1][i] = ng[l][r + 1][i] | ng[l][r][i];
            }
        }
    }
    std::vector dp(N + 1, std::vector<long long>(N + 1, -1LL));
    auto rec{[&](auto rec, int l, int r) -> long long {
        if (dp[l][r] != -1) return dp[l][r];
        long long& res{dp[l][r]};
        res = 0;
        if (l == r) return res = 1;
        for (int m{l} ; m < r ; m++) if (!ng[l][r][m]) {
            res = add(res, mul(rec(rec, l, m), mul(rec(rec, m + 1, r), comb[r - l - 1][m - l])));
        }
        return res;
    }};

    std::cout << rec(rec, 0, N) << '\n';
}

[提出](https://atcoder.jp/contests/arc183/submissions/58390369)

## 感想

この回はコンテストにオンタイムで参加していて、$120$分ほぼ全部これにつっぱして解けなかった思い出がある。感想戦で方針を知っていた。

当時は包除原理ばっかり考えていて詰んでいた。変に解法をエスパーするよりも、堅実に観察・定式化を積み上げる考察を心がけたいものだ。