SRM482 Div1 Easy(250) LockersDivOne

偶数のみ追加の高速化が無くてもギリギリ通った。

LockersDivOne

#include <list>

using namespace std;

class LockersDivOne{public:
int lastOpened( int N )
{
    if ( N == 1 )
        return 1;

    list<int> locker;
    for ( int i=2; i<=N; i+=2 )
        locker.push_back( i );

    for ( int n=2; locker.size()>1; n++ )
    {
        for ( list<int>::iterator it=locker.begin(); it!=locker.end(); )
        {
            it = locker.erase(it);

            for ( int i=0; i<n && it!=locker.end(); i++ )
                it++;
        }
    }

    return locker.front();
}};

n = 1, 2, 3……に対して答えは、
1 2 2 4 4 6 6 6 6 10 10 12 12 12 12 12 12 18 18 18 18 22 22 22 22 22 22 22 22 30 30 30 30 34 34 34 34 34 34 34 34 42 42 42 42 42 42 48 48 48 48 48 48 48 48 48 48 58 58 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 78 78 78 78 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 ……。
整数列大辞典に
1 2 4 6 10 12 18 22 30 ……
を訊いてみると、A002491。

class LockersDivOne{public:
int lastOpened( int N )
{
    int ans = 1;
    for ( int n=0; ; n++ )
    {
        int x=1;
        for ( int t=n; t>=1; t-- )
            x = (x+t-1)/t*t;
        if ( x > N )
            break;
        ans = x;
    }
    return ans;
}};

これなら最大ケースでも50msくらい。