Codeforces Round #256 (Div. 2)

翌日早起きする必要があったのでリアルタイムでは不参加でした。

A

x = gets.chomp.split.map{|i| i.to_i}.inject(:+)
y = gets.chomp.split.map{|i| i.to_i}.inject(:+)

if (x+4)/5 + (y+9)/10 <= gets.to_i
  puts "YES"
else
  puts "NO"
end

B

if( に含まれる文字と に含まれる文字が順不同で等しい) -> array
else if ( が の部分文字列) ->automaton
else if ( に含まれる文字で を作れる) -> both
else need tree

// aとbの最長共通部分列(lcs)を求める
template<typename T>
T lcs(T const& a, T const& b) {
    const int n = a.size(), m = b.size();
    vvi X(n+1, vi(m+1));
    vvi Y(n+1, vi(m+1));
    rep(i,n)rep(j,m){
        if (a[i] == b[j]) {
            X[i+1][j+1] = X[i][j] + 1;
            Y[i+1][j+1] = 0;
        } else if (X[i+1][j] < X[i][j+1]) {
            X[i+1][j+1] = X[i][j+1];
            Y[i+1][j+1] = +1;
        } else {
            X[i+1][j+1] = X[i+1][j];
            Y[i+1][j+1] = -1;
        }
    }
    T c;
    for (int i = n, j = m; i > 0 && j > 0; ) {
        if      (Y[i][j] > 0) --i;
        else if (Y[i][j] < 0) --j;
        else { c.push_back(a[i-1]); --i; --j; }
    }
    reverse(all(c));
    return c;
}

string solve(string a, string b){
    string ta=a;
    string tb=b;
    sort(all(ta));
    sort(all(tb));
    if(ta==tb){
        return "array";
    }

    if(lcs(a,b)==b){
        return "automaton";
    }

    bool both=true;
    map<char,int> ca;
    map<char,int> cb;
    each(i,a)ca[i]++;
    each(i,b)cb[i]++;

    each(p,cb){
        if(ca[p.first]<p.second){
            both=false;
            break;
        }
    }
    if(both){
        return "both";
    }
    return "need tree";
}

int main(){
    string a,b;
    while(cin>>a>>b)
        cout << solve(a,b) << endl;
}

C

3 3 3 3 3のように長方形になっているときは縦の長さと横の長さのうち短い方を返す。
そうでないときは

• 全部縦に塗る
• 数列の最小値の回数だけ下の方を塗ったあと、残った部分をどう塗るか再帰的に考えて足す。

の2通りのうち小さい方を返す。
例えば2 2 3 3 2 2なら

• 縦に5回塗る
• 横に2回塗って0 0 1 1 0 0にしたあと残った1 1どう塗るか考える

のどちらがいいか？となる。

こういう貪欲法の他にもDPで解くこともできるらしい。

int a[6000];

int solve(int l, int r){
    if(l==r) return 0;
    int m=a[l];
    bool rect=true;
    loop(i,l,r){
        if(a[l]!=a[i])rect=false;
        m=min(a[i],m);
    }
    loop(i,l,r)a[i]-=m;

    int res;
    if(rect){
        res = min(m,r-l);
    }else{
        res=r-l;
        int x=0;
        int tl=0;
        while(1){
            while(tl<r && a[tl]==0){
                tl++;
            }
            int tr=tl;
            while(tr<r && a[tr]!=0){
                tr++;
            }
            x+=solve(tl,tr);
            tl=tr;
            if(tl==r) break;
        }

        res=min(res, x+m);
    }

    // cout << l << " " << r << " " << res << endl;
    return res;
}

int main(){
    int n;
    while(cin>>n){
        rep(i,n)cin>>a[i];
        cout << solve(0,n) << endl;
    }
}

D

段目の行 の中で 以下の数の個数は (が割り切れるときは1引く)となる。これを まで足していけば表全体で より小さいものの個数がわかる。
の値で二分探索する。

ll solve(ll w,ll h,ll k){
    if(w<h) swap(h,w);
    ll l=1;
    ll r=inf;
    // [l,r)
    while(l+1<r){
        ll mid=(l+r)>>1;
        ll c=0;
        loop(y,1,h+1){
            c+=min(w,(mid-1)/y);
        }
        // cout << mid << " " << c << endl;
        if(c<k)l=mid;
        else r=mid;
    }
    return l;
}

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