AtCoder Beginner Contest 006

[TakefumiYamamura]

http://abc006.contest.atcoder.jp/

[TakefumiYamamura]

D - トランプ挿入ソート

時間制限 : 2sec / メモリ制限 : 256MB

問題文

数字が書かれたカードが N 枚あります。このカードの束（山札）に対して以下の操作が可能です。

山札からカードを 1 枚抜き取り、任意の場所に挿入する。 山札の上から下に向けて、カードを昇順に並べ替えるために必要な、最小の操作回数を求めてください。

Note

結局、最長増加部分列問題。lower_bound をつかわないと間に合わない

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define ll long long
using namespace std;

const ll MAX = 1e9+7;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    ll n;
    ll c[100001];
    cin >> n;
    ll ans = 0;
    ll count = 1;
    for (int i = 0; i < n; ++i)
    {
        cin >> c[i];
    }
    ll dp[100001];
    Fill(dp, MAX);
    for (int i = 0; i < n; ++i){
        *lower_bound(dp, dp+n, c[i]) = c[i];
    }
    cout << n -distance(dp, lower_bound(dp, dp+n, MAX)) << endl;
    return 0;
}

[TakefumiYamamura]

C - スフィンクスのなぞなぞ

問題

http://abc006.contest.atcoder.jp/tasks/abc006_3

note

3次の連立方程式の１つの項を固定させると、他の条件から残りの変数が確定するので計算量はO(n)

#include <iostream>

using namespace std;

class Riddle
{
public:
    int n, m;
    Riddle();
    ~Riddle();
    void exec();
};

Riddle::Riddle(){
    cin >> n >> m;
}

Riddle::~Riddle(){}

void Riddle::exec(){
    for (int adult = 0; adult <= n; ++adult)
    {
        int old = 4*n - 2*adult - m;
        int baby = n - adult - old;
        if(old < 0 || baby < 0) continue;
        if(baby * 4 + adult * 2 + old * 3 == m){
            cout << adult << " " << old << " " << baby << endl;
            return;
        }
    }
    cout << "-1 -1 -1" << endl;
}

int main(){
    Riddle r = Riddle();
    r.exec();
}