PKU 1011

Sticks
Time Limit Exceedを回避することができず、諦めてカンニング。ShortCoding本に載っていた。著者のサイトにも250Bまでは。書き方は違うけど、やっていることは同じだよなと首を捻ったが、バグで一部枝刈りが働いていなかった。

枝刈り

• 長い順に試していく
• 一つの棒の中での順番を長→短に固定（5+1=6は探すが、1+5=6は無視）
• 全ての棒の長さが等しいので、棒をまるごと入れ替えた解を探さない
• 同じ長さのパーツは１つのみチェック

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

vector<int>     part;       //  length of divided sticks
vector<bool>    assign;     //  whether i-th part is assigned
int             total;      //  total length of sticks
int             length;     //  length of a stick

bool            connect( int current, int i );

int main()
{
    int n;
    while ( cin>>n && n>0 )
    {
        part.resize( n );
        assign.resize( n, false );

        for ( int i=0; i<n; i++ )
            cin >> part[i];

        sort( part.begin(), part.end() );

        total = accumulate( part.begin(), part.end(), 0 );
        
        for ( int num=total/part.back(); ; num-- )
        if ( total % num == 0 )
        {
            length = total / num;

            if ( connect( 0, 0 ) )
            {
                cout << length << endl;
                break;
            }
        }
    }

    return 0;
}

//  connect a part to stick
//  current: current total length of sticks
bool connect( int current, int i )
{
    if ( current >= total )
        return true;

    bool first = current % length == 0;
    
    if ( first )
        i = (int)part.size() - 1;

    int last = -1;

    for ( ; i>=0; i-- )
    if ( ! assign[i]  &&
         current/length == (current+part[i]-1)/length  &&
                            //  part must be in one stick
         part[i] != last )  //  check the same-length part only once
    {
        assign[i] = true;
        bool f = connect( current+part[i], i-1 );
        assign[i] = false;

        last = part[i];

        if ( f )  return true;
        if ( first )  break;
    }

    return false;
}