SRM456 Div1 Midium(450) CutSticks

CutSticks

二分法。最初ループの条件を while((b-a)>1e-10) としていたら、無限ループになるテストケースがあった。参加した方のブログを見るに、二分法のループ回数は定数にするものらしい。
今回の問題は、最初の幅が高々10⁹、求められている精度が10^-9で、１回のループで幅が半分になるから、lg(10^18)≒60回以上回せばOK。

#include <vector>

using namespace std;

class CutSticks
{
    bool check( vector <int> sticks, int C, int K, double l );
public:
    double maxKth( vector <int> sticks, int C, int K );
};

double CutSticks::maxKth( vector <int> sticks, int C, int K )
{
    double a = 0;
    double b = 1000000000;

    for ( int i=0; i<100; i++ )
    {
        double c = ( a + b ) / 2;

        if ( check( sticks, C, K, c ) )
            a = c;
        else
            b = c;
    }

    return ( a + b ) / 2;
}

//  C回以内のカットで長さl以上の棒をK本以上切り出せるか
bool CutSticks::check( vector <int> sticks, int C, int K, double l )
{
    int n = (int)sticks.size();

    int k = 0;

    for ( int i=0; i<n; i++ )
    if ( sticks[i] >= l )
    {
        int c = min( C, (int)(sticks[i]/l)-1 );
        k += c + 1;
        C -= c;
    }
    
    return k >= K;
}

本番中に考えていた方針は、１本の棒から分割された棒は全て同じ長さとなる最適解があるという仮定で、各棒の分割数を決めていくというもの。終了後書き上げてみたけど、TLE。そりゃそうか。いくつかの長い棒の分割数を交互に増やしていく形になるので、高速化も難しい。

#include <vector>
#include <algorithm>

using namespace std;

class CutSticks
{
    struct STICK
    {
        int l, n;

        double length() const { return (double)l/n; }
        bool operator<( const STICK &s ) const { return length() < s.length(); }
    };

public:
    double maxKth( vector <int> sticks, int C, int K );
};

double CutSticks::maxKth( vector <int> sticks, int C, int K )
{
    int n = (int)sticks.size();
    vector<STICK> s( n );
    for ( int i=0; i<n; i++ )
        s[i].l = sticks[i],
        s[i].n = 1;

    double m = 0;

    for ( int i=0; i<=C; i++ )
    {
        //  K番目の長さを調べる
        sort( s.begin(), s.end() );

        if ( n + i >= K )
        {
            int c = 0;
            int j;
            for ( j=n-1; j>=0; j-- )
                if ( ( c += s[j].n ) >= K )
                    break;

            m = max( m, s[j].length() );
        }

        //  分割数を+1したときに最も長くなる棒を分割
        for ( int j=0; j<n; j++ )
            s[j].n++;
        max_element(s.begin(),s.end())->n++;
        for ( int j=0; j<n; j++ )
            s[j].n--;
    }

    return m;
}