cafelier@SRM

ACM-ICPC 2013 Aizu Regional 問題I

その他 | 00:36 |

ACM-ICPC 2013 アジア地区予選会津大会 の問題Iを解いてみたよ。

まず、balanced tree はなんであれ、深さ d の葉の重みが w だったら深さ d-1 の重みは 2w、深さ d-2 の重みは 4w、d-3 は 8w、…と倍々に増えていきます。なので例えば、同じ木に重み 1 と 3 の葉が混ざることは絶対にありえない。というわけで、まず最初の列を 1,2,4,8,... だけ含む列と、3,6,12,24,... だけ含む列と、5,10,20,…と、等々に分離してそれぞれ別々に解くことができます。つまり、一般性を失わず、配列の要素が1,2,4,8,...だけの場合のみ考えれば良い。

で、1,2,4,8,... だけの場合、まず過程をすっ飛ばして答えだけ先に書くと、こんな感じに更新式が +1 と max だけの非常にシンプルな DP になります。

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

// Aの要素が全部 {1,2,4,8,16,...} の場合を解く
int solve_1248(const vector<int>& A)
{
   int sum = accumulate(A.begin(), A.end(), 0);

   vector<int> dp(sum+1, -999999999);
   dp[0] = 0;
   for(int Ai: A)
      for(int x=sum/Ai*Ai; x>=Ai; x-=Ai) // (Aiの倍数すべてについて)
         dp[x] = max(dp[x], dp[x-Ai]+1);

   int best = 0;
   for(int x=1; x<=sum; x*=2)
      best = max(best, dp[x]);
   return best;
}

// A を {1,2,4,8,...} と {3,6,12,24,...} と {5,10,20,40,...} に分けてそれぞれ解く
int solve(const vector<int>& A)
{
   map<int, vector<int>> bucket;
   for(int Ai: A)
   {
      int lsb = Ai & (~Ai+1);  // (Aiの1が立ってる一番下のビットだけ残す)
      bucket[Ai/lsb].push_back(lsb);
   }

   int best = 0;
   for(const auto& kv: bucket)
      best = max(best, solve_1248(kv.second));
   return best;
}

// 入出力
int main()
{
   for(int N; cin>>N, N; )
   {
      vector<int> A(N);
      for(auto& Ai: A)
         cin >> Ai;
      cout << solve(A) << endl;
   }
}

計算量は O(N・ΣA) で、N≦1000、Ai≦500 なので少し大きめに見えますが、ループの中身がものすごく単純なので余裕です。（※あるいは、上に述べたように2の冪乗だけ考えればいいので、Aiの実質の上限は256で、ΣA は 256000 ですが、これも本当は2の冪乗までしか要らないのでつまり 131072 まで見ればよい、等々細かく解析していくと意外と安心できる演算回数が上限として計算できます。）

solve_1248() の導出

上のコードは、実はこういうことをやっています。配列 A を左から見ていって、balanced tree を左からじわじわと作っていく。

int solve_1248(const vector<int>& A)
{
   map<作りかけの木, その木を作るのに最大で使える葉の数> dp;
   dp[空集合] = 0;

   for(int Ai : A)
      for((partial_tree, leaf_count) : dp)
         if(partial_tree の右に葉 Ai をくっつけることができる) {
            ptree2 = partial_tree の右に葉 Ai をくっつけたもの
            dp[ptree2] = max(dp[ptree2], leaf_count+1);
         }

   int best = 0;
   for((ptree, leaf_count) : dp)
      if(ptreeが木として完成している)
         best = max(best, leaf_count);
   return best;
}

作りかけの木、や、右から葉を足す、というのはこんな感じ：

で、こんな木っぽいものを dp のキーにするのは大変そうですしそもそも木の形って指数的にパターンがありすぎて爆発しそうな気が一瞬しますが、そうでもありません。この木はあとで「右から葉を足す」操作しか行わないので、「右から葉を足す」観点で違いがない木たちは同一視して同じものと思って構いません。具体的には、完全に二分木として完成している部分は重みを合計して１ノードにつぶしてしまって差し支えない。

で、こうやって潰した作りかけ木だけを考えると、葉ノードは、常に、左から右に狭義単調減少しているものだけが現れます。上の図なら[8,4]という減少列。なんでかというと減少しないで同じ値が並んでたらそこは木が完成していて潰せるので。同じ並びがないなら、増えるところがあるとbalanced treeにならない。

で、で、[8,4] や [16,2,1] や [8,4,2,1] のような２の冪の狭義減少列は、自然数の二進数表記と１対１に対応します。[8,4]は8+4=12という自然数を、[16,2,1]は19=16+2+1という自然数を表していると思えばよい。逆に自然数から列は一意に復元できます。

つまり、長々と書いてきましたが、ここまで書いたことをまとめると、「作りかけの木」は、「葉の重みを全部足した自然数」で表現できます。ので、それをDPのキーにすれば簡単です。

int solve_1248(const vector<int>& A)
{
   int sum = accumulate(A.begin(), A.end(), 0);

   vector<int> dp(sum+1, -999999999);
   dp[0] = 0;
   for(int Ai: A)
      // 重み総和x-Aiの作りかけの木に、右から葉 Ai をくっつけて重み総和xの木を作る。
      // 右から葉Aiをくっつけるには、単調減少列をキープするには、
      // x-Aiの二進数で一番右の桁がAi以上でないといけない。
      // つまりx-Aiが、あるいはxがAiの倍数でないと。
      for(int x=sum/Ai*Ai; x>=Ai; x-=Ai)
         dp[x] = max(dp[x], dp[x-Ai]+1);

   // 完成している木の重みは2のベキ乗なのでそこのスコアを数える
   int best = 0;
   for(int x=1; x<=sum; x*=2)
      best = max(best, dp[x]);
   return best;
}

以上。

vector<int> dp;という配列を作るのではなくて、map<int,int> や vector<pair<int,int>> を使って実際に作れる可能性のあるsumだけ覚える、というコードを考えた人もいるかもしれませんが、可能性のあるsumは簡単に全通りできるので、この表はちょっとでも意地の悪いデータなら全エントリ埋まります。普通の配列でベタに持つ方が圧倒的に効率がよいです。

solve_1248() の導出：別の見方

この問題は構文解析問題だと思っています。

1. balanced treeを表現する文法を定義する。こういうBNFですね。

2 ::= 1 1
4 ::= 2 2
8 ::= 4 4
... 

2. LR(0)構文解析器のようなボトムアップの構文解析器を作る

3. 使わない数値は捨てるという処理が必要なので非決定的な構文解析になりますが、その非決定性を全探索…は非効率的なので

4. ボトムアップ構文解析のスタックをキーにしてメモ化する

5. スタックの要素は必ず [8,4,1] 的な単調減少列になっているので、（上でも書いた二進数と対応する理論により）高々、作れる最大ツリーの重みくらいの可能性しかないので十分なメモ化が利く