Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2009-12-06

NumbersAndMatches (SRM454 DIV1Comments Medium)

| 18:06 | NumbersAndMatches (SRM454 DIV1Comments Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - NumbersAndMatches (SRM454 DIV1Comments Medium) - TopCoder煮ブログ

答えを見ても全く分からずに一日悩んだ。いろいろ探す過程で「今回の500は簡単」という発言をみて萎える。

今回は、桁の数を増やしながら計算するのが一番外側のループ。表に記憶するのは、1つ前の桁の過不足を含んだ数の個数。

DP

追加数と減少数の表をまず作る

del\add01234
010000
100000
200000
300000

最初に処理する桁が「2」のときは、それぞれの数に移動したときの数を記録する。

del\add01234
010100
101300
200100
301200

(0,0)は2から2に遷移するとき(つまり移動は発生しない)。(1,1)が2から1に遷移するとき(1個減らして1個追加、つまり1回の移動)。

(2,1)は2から0,6,9に遷移するとき。たとえば、2から0に遷移するには2個追加して1個減ったらいける。このままだと過不足が発生しているが、この次の桁で1個減らす遷移が発生すると、過不足は解消される。

さて、次の桁。

たとえば次の桁が「2」のときは、2から10通りの数に移る場合の移動を計算する。この移動方法を(0,0)からだけじゃなく、その他の数字がある場所全てに適用して、2桁目を変えた全パターンについて移動先の数を求める。

こんな感じで全ての桁について DP 表を更新したら、最後に K 個の対角線の数を足し合わせる。対角線というのは、マッチの移動が過不足なく行えた場所。

ソース

cafelier 先生のソースを解読してコメントつけてみた。


#include <string>
#include <vector>
#include <numeric>
#include <iostream>
using namespace std;

//   0
// 1   2
//   3
// 4   5
//   6
char* NUMBERS[] = {
    "1110111", //0
    "0010011", //1
    "1011101", //2
    "1011011", //3
    "0111010", //4
    "1101011", //5
    "1101111", //6
    "1010010", //7
    "1111111", //8
    "1111011", //9
};
int DP[18][200][200];

class NumbersAndMatches {

public:
    // a から b へ遷移するときに追加、削除するマッチの数を取得する
    void diff(int a, int b, int* add, int* del){
        for(int i = 0; i < 7; i++){
            if(NUMBERS[a][i] < NUMBERS[b][i]) *add += 1;
            else if(NUMBERS[a][i] > NUMBERS[b][i]) *del += 1;
        }
    }

    long long differentNumbers(long long N, int K) {
        // DP の領域を初期化する
        memset(DP, 0, sizeof(DP));
        DP[0][0][0] = 1;

        // 一桁ずつ処理していく
        int cnt = 0;
        while(N){
            // 処理する桁の数字を取得する
            int n = N % 10;
            N /= 10;
            cnt++;
            
            // 追加する回数、減らす回数を総当りする
            for(int i = 0; i < K; i++){
                for(int j = 0; j < K; j++){
                    // cnt 番目の数が k になるとき
                    for(int k = 0; k < 10; k++){
                        // マッチの増加数、減少数を調べる
                        int add = 0, del = 0;
                        diff(n, k, &add, &del);

                        // 移動数が上限 K を超えないときは、
                        // DP の表に記録する
                        if(add + i < K && del + j < K){
                            // 次の場所の数に n から k に移動する数を追加する
                            DP[cnt][add+i][del+j] += DP[cnt - 1][i][j];
                        }
                    }
                }
            }
        }

        // 対角線の値を K 個足し合わせる
        long long ret = 0;
        for(int i = 0; i <= K; i++){
            ret += DP[cnt][i][i];
        }
        return ret;
    }
};

2008-11-07

StrengthOrIntellect (SRM424 DIV1 Medium)

| 23:57 | StrengthOrIntellect (SRM424 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - StrengthOrIntellect (SRM424 DIV1 Medium) - TopCoder煮ブログ

HPとMPがあってレベルアップのときにどう振り分けるか、みたいな問題。現在の strength と intellect が分かれば、そこから余剰ポイントと通過したミッションが定まるのでそれをベースに次の状態を求めていけることに気づいた。最悪時に同じ計算を何度もやってしまっていたので、メモして高速化してみたら、難なく System Test に通った。一応ソースを貼っておこう。

#include <vector>
#include <iostream>
using namespace std;

template<class T> inline int count_bit(T n){int r=0;while(n > 0){if(n&1)r++; n>>=1;}return r;}
int visited[1001][1001];

class StrengthOrIntellect {
public:
    int N;
    vector<int> SV, IV, PV;

    int solv(int S, int I){
        S = min(S, 1000);
        I = min(I, 1000);
        if(visited[S][I]) return visited[S][I];

        int points = 0;
        long long state = 0;
        for(int i = 0; i < N; i++){
            if(S >= SV[i] || I >= IV[i]){
                state += (1LL << i);
                points += PV[i];
            }
        }
        points = points - (S + I) + 2;

        int Smin = (int)1e9, Imin = (int)1e9;
        int Sind, Iind;
        for(int i = 0; i < N; i++){
            if((state & 1LL << i)) continue;
            if(Smin > SV[i]){Smin = SV[i]; Sind = i;}
            if(Imin > IV[i]){Imin = IV[i]; Iind = i;}
        }

        int ret = 0;
        if(points > 0 && Smin <= S + points){
            ret = max(ret, solv(Smin, I));
        }
        if(points > 0 && Imin <= I + points){
            ret = max(ret, solv(S, Imin));
        }

        return visited[S][I] = max(ret, count_bit(state));
    }

    int numberOfMissions(vector <int> strength, vector <int> intellect, vector <int> points) {
        N = strength.size();
        SV = strength;
        IV = intellect;
        PV = points;
        memset(visited, 0, sizeof(visited));
        return solv(1, 1);
    }
};

ただ DP で解いたほうが全体的にすっきりとしたソースになる。

VrmanVrman2012/07/10 01:49Whoever edits and publishes these atrilces really knows what they're doing.

itdcbmoevcitdcbmoevc2012/07/10 16:018wcDPn <a href="http://xkevcdxqtevw.com/">xkevcdxqtevw</a>

nsyzafooknsyzafook2012/07/12 12:18x6IGQS <a href="http://ucopfphvzofe.com/">ucopfphvzofe</a>

gojwfkgojwfk2012/07/12 17:48qezOlz , [url=http://ezuzdkbwcdug.com/]ezuzdkbwcdug[/url], [link=http://vdrugwwanyht.com/]vdrugwwanyht[/link], http://qbsozmxyjucd.com/

2008-11-02

ContiguousCache (SRM410 DIV1 Medium)

| 22:06 | ContiguousCache (SRM410 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - ContiguousCache (SRM410 DIV1 Medium) - TopCoder煮ブログ

見当がつかないので解答をみる。DPな問題はどうも発想方法が分からん。ソースを読んでもしばらく理解できず。1度キャッシュした場所はずっとキャッシュされ続けているかと勘違いしていて余計に時間かかった。なんとなく理解できたが書ける気がしない。Read開始アドレスが addresses もしくはそこから K - 1 を引いたもののどちらかでよい、というところがいまいちしっくり来ない。

ClosestRegex (SRM410 DIV2 Hard)

| 00:29 | ClosestRegex (SRM410 DIV2 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - ClosestRegex (SRM410 DIV2 Hard) - TopCoder煮ブログ

text に最も近い正規表現にマッチするものを求める問題。正規表現は50文字までなのだけど、"a*b*c*d*..."のようなパターンだと正攻法で解いたら計算時間がひどいことになる。それを解決するためには、おそらく DP でなんとかするんだろうが、やっぱりひらめかない。DP 弱い。Match EditorialsDynamic Programming: From novice to advancedというリンクが。おお、こんな素敵なチュートリアルがあったのか! 他にも左メニューの「Algorithm Tutorials」には魅力的な文章がいくつも。このあたりをまずは一読しておくとよさそうだ。

一読して、そのあとにしばらく考えたらひらめいた。DP[i]には文字数が i の正規表現のうち、text にマッチする数が最小となるものを保存すればよい。atomでforを回して、DP[i] を更新していく。atom が * の場合には DP[i] を右短まで更新して、* がない場合には1つ進める。例えば、1) の例だと、最初の t* を解釈したときの DP は次のようになる。

DP[0]: 0  // ""
DP[1]: 0  // "t"
DP[2]: 1  // "tt"
DP[3]: 2  // "ttt"
DP[4]: 3  // "tttt"
DP[5]: 4  // "ttttt"
DP[6]: 5  // "tttttt"
DP[7]: 6  // "ttttttt"
DP[8]: 7  // "tttttttt"

次の p を解釈したらこうなる。

DP[0]  ∞ // ""
DP[1]  1  // "p"
DP[2]  1  // "tp"
DP[3]  1  // "ttp"
DP[4]  3  // "tttp"
DP[5]  4  // "ttttp"
DP[6]  5  // "tttttp"
DP[7]  6  // "ttttttp"
DP[8]  7  // "tttttttp"

DP[0] はありえないので∞にしている。こんな感じで続けていけばおk。