SRM 593 Div I

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15705

250にはまりにはまり、55分。Room 41。レートは1231から1308へ。

今回のエントリでは、SRM後に復習として考察した450のみを記載することにする。

	Problem	Status	Points
250	HexagonalBoard	Passed System Test	102.09
450	MayTheBestPetWin	Opened	0.00
1000	WolfDelaymasterHard	Unopened	0.00

250に55分
- はまりにはまった
- 最近、深さ優先探索をすっきり書き上げることができないことが多い
- 方針は合っているので、もったいない
450を復習
- 式変形によるDPであった
- また、dr.kenさんのDPによる実装をコードリーディングし、考察した

MayTheBestPetWin

http://community.topcoder.com/stat?c=problem_statement&pm=12779&rd=15705

苦手なDPであるようなので、復習、考察を行った。

1時間ほど考え、ギブアップ
@fuqinhoさんの式展開を見て、目から鱗

以下の式変形を行う

Σ_i∈UA_iとΣ_i∈UB_iは定数と考えることが出来るので、DPを用いてΣ_i∈S(A_i + B_i)が取りうる値を調べる
調べた値で以下を計算し、一番小さいものが求める答えとなる

すごい
- 式変形を行うことで0-1ナップサックを解く問題になってしまった

以下は式変形を伴ったDPでの実装(システムテストを通る)。

bool dp[1111111];


class MayTheBestPetWin {
public:
  int calc(std::vector<int> A, std::vector<int> B) {
    int AA = std::accumulate(ALL(A), 0);
    int BB = std::accumulate(ALL(B), 0);

    int size = A.size();

    memset(dp, 0, sizeof(dp));
    
    dp[0] = true;

    for (int i = 0; i < size; i ++) {
      int s = A[i] + B[i];

      for (int j = 1e+6; j >= 0; j --)
        if (j - s >= 0)
          if (dp[j - s])
            dp[j] = true;
    }

    int dm = INF;

    for (int i = 0; i <= 1e+6; i ++)
      if (dp[i])
        dm = std::min(std::max(std::abs(i - AA), std::abs(i - BB)), dm);

    return dm;
  };

この解法については上位コーダーのエントリを是非参照していただきたい

さて、ここからはdr.kenさんの解法をコードリーディングし、考察を行う
- 氏にはツィッターでの質問に答えていただいたり、またブログを記載することを快諾いただいた
- @drken1215さん、どうもありがとうございます

以下は@drken1215さんの解法。

bool dp[1100000], tdp[1100000];
 
class MayTheBestPetWin {
public:
    int calc(vector <int> A, vector <int> B) {
        memset(dp, 0, sizeof(dp));
        
        int SMax = 0, SMin = 0;
        for (int i = 0; i < A.size(); ++i) {
            SMax += max(A[i], B[i]);
            SMin += min(A[i], B[i]);
        }
        
        dp[550000] = 1;
        for (int i = 0; i < A.size(); ++i) {
            memset(tdp, 0, sizeof(tdp));
            for (int j = 0; j < 1100000; ++j) {
                //if (dp[j]) cout << i << ", " << j-550000 << endl;
                
                if (!dp[j]) continue;
                int lo = min(A[i], B[i]), up = max(A[i], B[i]);
                if (j + up < 1100000) tdp[j+up] = true;
                if (j - lo >= 0) tdp[j-lo] = true;
            }
            for (int j = 0; j < 1100000; ++j) {
                dp[j] = tdp[j];
            }
        }
         
        int res = 0;
        for (res = 550000; res < 1100000; ++res) {
            if (dp[res] && SMax-SMin <= (res-550000)*2) break;
        }
        
        return res - 550000;
    }
};

何やらDPっぽいことは分かる
- だが、先に挙げた式変形を経たDPとは本質的に違う気がした

明確な理由はないが今の自分が理解すべき重要な実装に思えたので、コードリーディングと考察を行った

前処理を前半、DPによる処理を中盤、値を探索しているらしい部分を後半と呼ぼう

前半はA_iとB_iの合計を取っている
- std::minとstd::maxを取っているが、制約から必要がない。これは実装時のノリのようなものだろう
- この値は後半まで使われない

全体の集合をUとしていることに注意
- SはUの部分集合であり、Tをその補集合として定義している

では中盤を読み進める
- 550,000分シフトさせてDPを行っているようだ
- つまり、大体[-550,000, 550,000]までの範囲の値を扱っていると考えられる
- また、tdpは値の一時置き場として使っているようだ。毎反復の最後でdpを更新している

では内側の反復を見てみよう

さっぱり理解できない

と言ってても始まらないので、読み進める

前回までに訪れたことがある値から、lo、up分ずれた値に訪れているようだ
- loとupの算出にstd::minとstd::maxを用いているが、制約から必要がない。これも実装時のノリのようなものだろう

つまり、以下のようなグラフの探索を行っていると言える(ブラウザによっては縮小されて表示されています。オリジナルの解像度のものを見るには、画像をクリックしてください)

んー

つまりは以下の取りうる値を全て調べているのか

取りうる値の集合をXとすると以下のような感じ

やっぱりさっぱり分からん

分からないものは分からないので、一先ず最後まで流し読みしてしまおう。最後は以下の条件を満たす値を探しているようだ

なんだこれは

何故割り算が出てくるのだろう...?

さっぱり分からん

ここまでをつぶやきながら、@drken1215さんにお話を伺ったりしたのだけれども、よく分からなかった...(エントリ最後に掲載)

(半日ほど試行錯誤する)

あー、分かった

伺った内容とは違うような気がするが、すっきり理解できた

では、自分の理解を記載しよう

以下が求めるmaxdiff(S, T)の定義だ(再掲)

この式はとても扱い辛い

絶対値が邪魔をしているんだ

ならば、絶対値を取ってしまえばいいじゃないか

また、制約から以下は明らかだ

これは直感から分かるんだけれども、ちゃんと証明しておこう。制約から、以下が言える

したがって、

であるので、

となる。これを変形すると、先に直感から求めた式を証明できた

これを使って、maxdiff(S, T)を整理しよう

すっっっごくすっきりした
- maxを取っている両方の値ともΣB_i - ΣA_iという形になった

つまり、全てのSとTの分け方について、Σ_i∈SB_i - Σ_i∈TA_iを列挙していることが分かる。これを集合Xと置く(再掲)

また、これを視覚化すると以下となる(再掲)

さて、整理したmaxdiff(S, T)は以下のようなものであった

S、Tと分けた場合とT、Sと分けた場合の結果は対の関係になっていそうだ。直感から、集合Xの値はある値を境に線対称になっているのではないかと推測できる

つまり、以下の集合Xから、

対となる集合X'が算出出来るのではないだろうか

ここで以下を考えてみよう

同様に、

これより、

したがって

つまり、集合Xの値の分布は直線x = (Σ_i∈UB_i - Σ_i∈UA_i) / 2で線対称となっていると言える

視覚化してみよう
- 確かにそれぞれの値に線対称になっている対の値があるようだ

つまり、求めるmaxdiff(S, T)の値は必ず集合の値の中央値以上の値となる

そのため、以下の条件を満たす値を探せばよい(再掲)

うおぉぉぉ

頭超すっきりした

すっきり理解したので、自分なりに実装してみよう
- エントリとしては冗長だが、自分としては大事な行為なので、お許し願いたい

以下の実装はシステムテストを通る。

#define ZERO 550000


class MayTheBestPetWin {
public:
  int calc(std::vector<int> A, std::vector<int> B) {
    std::vector<bool> curr(1111111, false), next(1111111, false);

    int AA = std::accumulate(ALL(A), 0);
    int BB = std::accumulate(ALL(B), 0);

    curr[ZERO] = true;

    for (int i = 0, size = A.size(); i < size; i ++) {
      std::fill(ALL(next), false);

      for (int j = - AA; j <= BB; j ++)
        if (curr[j + ZERO])
          next[j - A[i] + ZERO] = next[j + B[i] + ZERO] = true;

      curr.swap(next);
    }

    for (int i = (BB - AA + 1) / 2; ; i ++)
      if (curr[i + ZERO])
        return i;

    // The code never reaches here.
    return -1;
  }
};