1014

漸化式にならないなら再帰のプログラム書いてからそれをDPに直せば良いじゃん。俺は人生で数式よりもプログラムに触れてた時間の方が32倍(当社比)くらいなげーんだよ！って開き直って適当に再帰で書いてみた。

bool search(int sum, int target)
{
    for (int i = 6; i >= 1; i--) {
        if (a[i] > 0) {
            if (sum + i == target) return true;
            if (sum + i > target) return false;
            a[i]--;
            if (search(sum + i, target)) return true;
            a[i]++;
        }
    }
    return false;
}

a[i]は価値iの残りの数、sumは再帰中に計算された和、targetは求める和(価値の総和/2)である。この再帰的な手法からDPに持って行く。この再帰の方法では総当たりで考えられる和を全て生成し、targetと同じになるまで探索している。

とりあえず分かったことは、適当に数字を足してtargetと数になればいい。ここで、与えられた数から作れる和の集合を考える。まず集合を空集合とし、その集合に0を入れる。次に、1がn_1個あったとしたら1*1,1*2,...,1*n_1を集合に入れる。
次に、n_2個の2に対して同じ事をするわけだが、2*1,2*2,...,2*n_2を集合に入れるだけでなく、それぞれの数と既に集合に含まれている元との和も集合に加える。これを6まで繰り返すことで全ての場合の和を求める事ができるので、その中にtargetが含まれていれば分割可能ということになる。ただし、これをこのままsetとかで実装するとオーダーが大変なことになるので他の方法を考える。

今回は

bool table[2][60001]

という配列を作ってみた。trueだったらその和を計算可能という感じ。

for (int i = 2; i <= 6; i++) {
    for (int k = 0; k < i; k++) {
        int c = a[i];
        for (int n = k; n <= target; n += i) {
            if (table[i&1^1][n]) {
                table[i&1][n] = true;
                c = 0;
            } else if (c < a[i]) {
                table[i&1][n] = true;
                c++;
            }
        }
    }
}

後はこんな感じにして、予めtable[1][0, a[1]の数]の先頭要素をtrueで初期化してループを回してやる(このときにtable[0]の初期化を忘れてWAが出まくってたorz)。このようにすると最大でtarget回内側のループを回すだけで済む。それx5なので求める和をNとすればO(N)で済むハズ。後はkのループを無くしてキャッシュを意識した高速化とかも出来るけど0msだったのでおｋという事にしておく。

くだらないミスで凄まじい時間を消費してしまた。

追記: ショートコーディングしてて気付いたけど、table[60001]だけで十分だった。改良前のやり方が悪かったせいで[2]も必要だっただけだった。

ショートコーディング:
340Bまで減ったけど200台になる気がしねぇ…。根本的にやり方変えるしか無いのか、見知らぬテクがあるのか…。ショートコーディング本欲しいなぁ(´･ω･｀)

#include<stdio.h>
#define F(i,a,b)for(i=a;i<=b;i++)
a[7],D[60001],C,c,i,k,n,t;
main(){
    t=0;
    F(i,1,6){scanf("%d",&a[i]);t+=i*a[i];}
    if(t){
        if(~t%2){
            t/=2;
            F(i,0,t)D[i]=0;D[0]=1;
            F(i,1,6)F(k,0,i-1){
                c=a[i];
                for(n=k;n<=t;n+=i)D[n]=D[n]?c=-1,1:++c<a[i];
            }
            t=D[t]^1;
        }
        printf("Collection #%d:\nCan%s be divided.\n\n",++C,t&1?"'t":"");
        main();
    }
}

とりあえず326Bの途中成果。合宿までにショートコーディング本読んでそっち系の話題で燃えたい。てかもう4時ですか…。台風も去ったみたいで外もすげー静か。寝るしかねぇ。やっぱりこういうくだらないプログラム書くのは楽しすぎてヤバイ。特にアセンブリ言語で組んでるとこういう細かいこと考える機会が多くて面白いんだよなぁ。