Codeforces Round #257 (Div. 2)

http://codeforces.com/contest/450
oo--- =1540 (-99), expert Rank: 1085 とダメダメでした。
最近バグ取りもアルゴリズムを考えるのも遅くなってきてる気がする

A

待ち行列なのでQueueに入れ空になるまでループを回した。

int main(){
    int n;
    while(cin>>n){
        int m; cin>>m;
        typedef pair<int,int> P;
        queue<P> s;
        rep(i,n){
            int x;cin>>x;
            s.push(P(i+1,x));
        }
        while(s.size()){
            P t=s.front();
            s.pop();
            if(t.second>m){
                t.second-=m;
                s.push(t);
            }else{
                ;
            }
            if(s.size()==0){
                cout << t.first << endl;
                break;
            }
        }
    }
}

B

何も考えずに行列ライブラリ(蟻本)に突っ込んだ。が、負の数のを正に直すときにwhile(y<0)x+=M;などして無駄に時間を使う。こんなこと考えなくても少し手計算すると周期性が見えたらしい。

mat mul(mat &A, mat&B) {
    mat C(A.size(), vec(B[0].size()));
    rep(i,A.size()){
        rep(k,B.size()){
            rep(j,B[0].size()){
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]);
            }
        }
    }
    rep(i,C.size())rep(j,C[0].size()){
        while(C[i][j]<0) C[i][j]+=M;
        C[i][j]%=M;
    }
    return C;
}

mat pow(mat A, ll n) {
    mat B(A.size(), vec(A.size()));
    for (int i = 0; i < A.size(); i++) {
        B[i][i] = 1;
    }
    while (n > 0) {
        if (n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

ll solve(ll x,ll y,ll n) {
    n--;
    ll res;
    if(n==0) res= x;
    else if(n==1) res= y;
    else{
        while(x<0)x+=M;
        while(y<0)y+=M;
        mat A(2, vec(2));
        A[0][0] = 1; A[0][1] = -1+M;
        A[1][0] = 1; A[1][1] = 0;
        A = pow(A, n);

        res=A[1][0]*y + A[1][1]*x;
    }
    while(res<0) res+=M;
    res%=M;
    return res;
}

int main(){
    ll x,y,n;
    while(cin>>x>>y>>n){
        cout << solve(x,y,n) << endl;
    }
}

C

切り方で全探索するとTLEする。

回水平に切ると垂直には 回切らなければならない。小さな長方形の高さの最小値は に、幅の最小値は となる。

が大きくなるほど が大きくとれる。 が の約数でなければ より大きい最小の約数で切るのと同じになるので、 は の約数の中だけで考えれば良い。 の約数を全列挙し、 の最大値をとる。同様に、垂直に切る回数 を の約数の中で考えた場合の最大値と比較して大きい方を返す。

これなら くらいなので間に合う。

他の人のソースによると全部垂直に切るか全部水平に切るかのどっちかだけで良いらしい。(どうしてかはよく分からない。)結局間に合わず解けなかったけどこういう問題好きだなー

ll a[1<<10];
template<typename T>
ll divider(T n, T* a){
    ll c=0;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            a[c++]=i;
            if(i*i!=n)a[c++]=n/i;
        }
    }
    sort(a,a+c);
    return c;
}

ll solve(ll n,ll m, ll k){
    int const c=divider(n,a);
    if(n-1+m-1<k) return -1;
    ll ans=-1;
    rep(i,c){
        ll w=a[i];
        ll k1=n/w-1;
        ll k2=k-k1;
        if(0<=k1&&k1<=k&&0<=k2&&k2<=k){
            ll h=m/(k2+1);
            ans=max(ans,h*w);
        }
    }
    return ans;
}

int main(){
    ll n,m,k;
    while(cin>>n>>m>>k){
        ll a1=solve(n,m,k);
        ll a2=solve(m,n,k);
        cout<<max(a1,a2)<<endl;
    }
}