SRM 424 div1 med:StrengthOrIntellect

SRM424の練習会に参加しました。結果はeasyだけ通して200ptくらいです。hardは今では典型になってそうな問題だったので後で解きたいと思います。

問題:TopCoder Statistics - Problem Statement

解法:まず注目すべきことは,
・最終的なStrengthとIntellectがわかれば何個のミッションをクリアできるかがわかる
なぜならばStrengthとIntellectのどっちかが必要とされているステータス以上だったらそのミッションをクリアできるので,それを全部数え上げれば良いからです。

ということで,「ステータスとしてどういうものがあり得るか」ということを調べたいですのですが,上の数え上げの方法では更に別のこともわかります。それは「そのステータスにした時余っているポイント(ステータス振り分けに使ってないポイント)がどれだけ残っているか」という情報です。これ(freePntとする)がわかると,あり得るステータスdpは以下のように求めることができます。

・dp[1][1]はtrue(初期値なので)
・dp[i][j]は以下の条件のいずれかが成り立てばtrue
・・i > 1かつfreePnt[i-1][j]が正 かつdp[i-1][j]がtrue
・・j > 1かつfreePnt[i][j-1]が正 かつdp[i][j-1]がtrue
これらの情報がわかれば答えを求めることができます。
以下ソースコード

bool dp[1111][1111];
int freePnt[1111][1111];

class StrengthOrIntellect {
public:
    int numberOfMissions(vector <int> strength, vector <int> intellect, vector <int> points) {
        int n = strength.size();
        memset(dp, 0, sizeof(dp));
        memset(freePnt, 0, sizeof(freePnt));
        dp[1][1] = true;
        for (int i = 0; i <= 1000; i++) {
            for (int j = 0; j <= 1000; j++) {
                int point = 0;
                for (int k = 0; k < n; k++) {
                    if (i >= strength[k] || j >= intellect[k]) {
                        point += points[k];
                    }
                }
                freePnt[i][j] = max(0, point-i-j+2);
            }
        }
        for (int i = 1; i <= 1000; i++) {
            for (int j = 1; j <= 1000; j++) {
                if (i > 1 && dp[i-1][j] && freePnt[i-1][j] > 0) dp[i][j] = true;
                if (j > 1 && dp[i][j-1] && freePnt[i][j-1] > 0) dp[i][j] = true;
            }
        }
        int ans = 0;
        for (int i = 0; i <= 1000; i++) {
            for (int j = 0; j <= 1000; j++) {
                if (!dp[i][j]) continue;
                int tmp = 0;
                for (int k = 0; k < n; k++) {
                    if (i >= strength[k] || j >= intellect[k]) tmp++;
                }
                ans = max(ans, tmp);
            }
        }
        return ans;
    }
};

この問題では「素直に全探索してたら探索量多すぎてどうにもならんよなぁ」とか思ってたんだけど,そういうのは探索の仕方の発想を変えるのが大事ですね。なんとなくyukicoderの「エラストテネスのざる」って問題を思い出しました。