比較的簡単枠だとは思っていたけど、B よりも解かれたのはびっくり！

問題概要

北海道高校には $M$ 個の科目があり、それぞれ 1, 2, 3 の 3 段階で成績がつけられる。各生徒の成績は長さ $M$ の文字列で表される

生徒 $X$ が生徒 $Y$ の「上位互換」であるとは

すべての科目 $i$ について ( $X$ の科目 $i$ の成績) ≥ ( $Y$ の科目 $i$ の成績)
ある科目 $i$ が存在して、( $X$ の科目 $i$ の成績) > ( $Y$ の科目 $i$ の成績) の両方がみたされることをいいます。

今、教室には誰もいない。これから $Q$ 人の生徒が順に教室に入っていく。 $i$ 番目の生徒の成績は文字列 $S_{i}$ で表される。各生徒は、自分が教室に入ったときに教室に自分の上位互換が存在していると悲しくなる。

$Q$ 人それぞれの生徒について、悲しくなるかどうかを判定せよ。

制約

$1 \le Q \le 5 \times 10^{5}$
$1 \le M \le 15$

考えたこと

上位互換の条件に含まれる「1 科目だけ完全に上でなければならない」という部分が扱いづらい。ここでは、A が B 以上であるとは、すべての成績が A >= B であることと定義する。このとき、(a, b, c, ...) の上位互換の人は

(a+1, b, c, ...) 以上
(a, b+1, c, ...) 以上
(a, b, c+1, ...) 以上
...

のいずれかの条件を満たすことになる。

DP へ

以上の考察を基にして、こんな DP を前処理で求めておこう。

dp[ S ] := 成績 S 以上をおさめる人の index の最小値

これは先ほどの考察から、

dp[ S ] = min_{T: S を 1 教科だけ点数を上げたもの} dp[ T ]

という漸化式で更新できる。この計算量は $O(M 3^{M})$ 。これはまさに $M$ 次元累積 min そのもの。高速ゼータ変換の一種ともみなせる。

このテーブルがあれば、各クエリには簡単に答えられる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

inline int conv(const string &s) {
    int res = 0;
    for (int i = s.size()-1; i >= 0; --i) res *= 3, res += (int)(s[i] - '1');
    return res;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N);
    vector<int> bitS(N);
    for (int q = 0; q < N; ++q) cin >> S[q], bitS[q] = conv(S[q]);

    vector<int> three(M+1, 1);
    for (int i = 0; i < M; ++i) three[i+1] = three[i] * 3;
    vector<int> dp(three[M], N);
    for (int q = 0; q < N; ++q) chmin(dp[bitS[q]], q);
    for (int bit = three[M]-1; bit >= 0; --bit) {
        for (int i = 0; i < M; ++i) {
            if (bit / three[i] % 3 == 2) continue;
            chmin(dp[bit], dp[bit + three[i]]);
        }
    }
    for (int q = 0; q < N; ++q) {
        int res = N;
        for (int i = 0; i < M; ++i) {
            if (S[q][i] == '3') continue;
            chmin(res, dp[bitS[q] + three[i]]);
        }
        cout << (res < q ? 1 : 0);
    }
    cout << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 3184 Hokkaido High School (HUPC 2020 day3-M)

問題概要

制約

考えたこと

DP へ

コード