ARC 088

C

何回2倍できるかを数える

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    ll X, Y;
    cin >> X >> Y;
    int ans = 0;
    while(X <= Y) {
        X *= 2;
        ans++;
    }
    cout << ans << endl;
}

Submission #1895699 - AtCoder Regular Contest 088

D

文字列長をn、0と1が切り替わるところをk(1-indexed)としたとき、max(k, n-k)の最大値が答え。全ての文字が同じ場合はnが答え。

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    string S;
    cin >> S;
    int n = S.size();
    int ans = n;
    for(int k=0; k<n; ++k) {
        if(S[k] != S[k+1]) {
            ans = min(ans, max(k+1, n-k-1));
        }
    }
    cout << ans << endl;
}

Submission #1902173 - AtCoder Regular Contest 088

ARC 087

C

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    map<int, int> m;
    cin >> N;
    REP(i, N) {
        int j;
        cin >> j;
        m[j]++;
    }
    int ans = 0;
    for(auto k : m) {
        if (k.second >= k.first) {
            ans += k.second - k.first;
        } else {
            ans += k.second;
        }
 
    } 
    cout << ans << endl;
}

Submission #1874632 - AtCoder Regular Contest 087

D

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int dx3[16010];
int dy3[16010];
int *dx = dx3+8005;
int *dy = dy3+8005;
 
int dx4[16010];
int dy4[16010];
int *dx2 = dx4+8005;
int *dy2 = dy4+8005;
 
int main(void) {
    string s;
    cin >> s;
    int gx, gy;
    cin >> gx >> gy;
 
    bool isX = true;
    int t = 0;
    vector<int> X, Y;
    for(int i=0; i<s.size(); ++i) {
        if(s[i] == 'F') t++;
        if(s[i] == 'T' || i==s.size()-1) {
            if(isX) {
                X.push_back(t);
            } else {
                Y.push_back(t);
            }
            t = 0;
            isX = !isX;
        }
    }
    dx[X[0]] = 1;
    for(int i=1; i<X.size(); ++i) {
        int mx = X[i];
        if(i%2==1) {
            for(int j=-8000; j<=8000; ++j) {
                if(dx[j] == 1) {
                    dx2[j+mx] = 1;
                    dx2[j-mx] = 1;
                    dx[j] = 0;
                }
            }
        } else {
            for(int j=-8000; j<=8000; ++j) {
                if(dx2[j] == 1) {
                    dx[j+mx] = 1;
                    dx[j-mx] = 1;
                    dx2[j] = 0;
                }
            }
        }
    }
 
    if(Y.size() > 0) {
        dy[Y[0]] = 1;
        dy[-Y[0]] = 1;
    } else {
        dy2[0] = 1;
    }
    for(int i=1; i<Y.size(); ++i) {
        if(i%2==1) {
            for(int j=-8000; j<=8000; ++j) {
                if(dy[j] == 1) {
                    dy2[j+Y[i]] = 1;
                    dy2[j-Y[i]] = 1;
                    dy[j] = 0;
                }
            }
        } else {
            for(int j=-8000; j<=8000; ++j) {
                if(dy2[j] == 1) {
                    dy[j+Y[i]] = 1;
                    dy[j-Y[i]] = 1;
                    dy2[j] = 0;
                }
            }
        }
    }
 
    bool okX = false;
    if(X.size()%2 == 0) {
        if(dx2[gx] == 1) okX = true;
    } else {
        if(dx[gx] == 1) okX = true;
    }
    bool okY = false;
    if(Y.size()%2 == 0) {
        if(dy2[gy] == 1) okY = true;
    } else {
        if(dy[gy] == 1) okY = true;
    }
 
    if(okX && okY) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Submission #1878861 - AtCoder Regular Contest 087

ARC 086

arc086.contest.atcoder.jp

C - Not so Diverse

  • mapで各数字がいくつあるかカウント
  • 数字の個数を降順にソートして、大きい方から(K+1)番目以降の数字の和が答え
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N, K;
    cin >> N >> K;
    map<int, int> A;
    REP(i, N) {
        int t;
        cin >> t;
        A[t]++;
    }
    vector<int> v;
    for(auto x : A) {
        v.push_back(x.second);
    }
    sort(v.rbegin(), v.rend());
    int ans = 0;
    for(int i=K; i<=v.size(); ++i) {
        ans += v[i];
    }
    cout << ans << endl;
}

Submission #1858429 - AtCoder Regular Contest 086 | AtCoder

D - Non-decreasing

  • 前から順に最大の正の数を足していくか、後ろから順に最小の負の数を足していけば非減少列が作れる
  • 最大値の絶対値と最小値の絶対値の大小関係によって取れる方針が決まることに注意する(max>0 かつ min>0なら前者、max>0 かつ min<0 かつ |max|<|min| なら後者……のように場合分けして考えると絶対値のみ比較すればよいことが分かる)
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i, N) {
        cin >> a[i];
    }
    int Max = a[0];
    int Max_idx = 0;か
    int Min = a[0];
    int Min_idx = 0;
    FOR(i, 1, N) {
        if(a[i] > Max) {
            Max = a[i];
            Max_idx = i;
        }
        if(a[i] < Min) {
            Min = a[i];
            Min_idx = i;
        }
    }
    if(Max == Min) {
        cout << 0 << endl;
        return 0;
    }
    vector<pair<int, int>> ans;
    if(abs(Max) > abs(Min)) {
        for(int i=1; i<N; ++i) {
            a[i] += Max*2;
            ans.push_back({Max_idx+1, i+1});
            ans.push_back({Max_idx+1, i+1});
            Max = a[i];
            Max_idx = i;
        }
    } else {
        for(int i=N-2; i>=0; --i) {
            a[i] += Min*2;
            ans.push_back({Min_idx+1, i+1});
            ans.push_back({Min_idx+1, i+1});
            Min = a[i];
            Min_idx = i;
        }
    }
    cout << ans.size() << endl;
    for(auto x : ans) {
        cout << x.first << " " << x.second << endl;
    }
}

Submission #1861515 - AtCoder Regular Contest 086 | AtCoder

E - Smuggling Marbles (400点解法)

  • 根からの深さごとに木DPで数え上げる
  • 各頂点は「その頂点に来たときにビー玉が0個になるその頂点を根とする部分木のビー玉配置の場合の数」と「その頂点に来たときにビー玉が1個になるその頂点を根とする部分木のビー玉配置の場合の数」の2つの数(x, y)=(dp[v][0], dp[v][1])を持っている(ビー玉が0個になるとは、その頂点に来たときに2個以上になって取り上げられる場合を含む)
  • 根からの深さがdの頂点を(1, 1)で初期化する
  • 根からの深さがk (k < d)の頂点では、
    • xは深さk+1の子のどれか1つからビー玉が1個来て、残りの全ての子から0個来る場合の数
    • yは自分を頂点とする部分木の全ての置き方の場合の数からxを引いた場合の数
  • これを繰り返すとdp[0][1]が深さdの頂点のみに注目したとき、根までビー玉が来る場合の数になる。それ以外の頂点の置き方は自由なので、2を「深さd以外の頂点数」乗した数のビー玉が根まで到達する
  • 取りうる全てのdについて上のDPを行う

maze1230さんのコードを参考に解きました。

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

ll dp[2010][2];
ll nb_depth[2010];

vector<int> G[2010];
const ll MOD = 1e9+7;
 
void count_depth(int v, int depth){
    nb_depth[depth]++;
    REP(i, G[v].size()){
        count_depth(G[v][i], depth+1);
    }
}


ll mpow(ll a, ll b){
    if(b == 0) return 1;
    if(b < 0) return 0;
    if(b%2) return (a*mpow(a, b-1)) % MOD;
    ll ret = mpow(a, b/2);
    return (ret*ret)%MOD;
}

void dfs(int v, int d) {
    if(d == 0) {
        dp[v][0] = dp[v][1] = 1;
        return;
    }
    ll x = 1, y = 1;
    for(auto c: G[v]) {
        dfs(c, d-1);
        x = (x * dp[c][0]) % MOD;
        y = (y * (dp[c][0]+dp[c][1])) % MOD;
    }
    for(auto c: G[v]) {
        // n^{-1} mod p = n^{p-2} mod p
        dp[v][1] += ((x * mpow(dp[c][0], MOD-2)) % MOD * dp[c][1]) % MOD;
        dp[v][1] %= MOD;
    }
    dp[v][0] = (y - dp[v][1] + MOD) % MOD;
}


int main(void) {
    int N;
    cin >> N;
    if(N>2000) return 0;
    REP(i, N) {
        int p;
        cin >> p;
        G[p].push_back(i+1);
    (}
    count_depth(0, 0);
    ll ans = 0;
    REP(d, N+1) {
        REP(j, 2010) {
            REP(k, 2) {
                dp[j][k] = 0;
            }
        }
        dfs(0, d);
        ans = (ans + dp[0][1] * mpow(2, N-nb_depth[d]+1)) % MOD;
    }
    cout << ans << endl;
}

Submission #1883114 - AtCoder Regular Contest 086 | AtCoder

満点解法は解説が理解できないのでパス。

Codeforces Round #403 (Div. 2)

本番ではAしか通らなかった。反省。それ以外はEditorialを読みながら解く。

A

Problem - 782A - Codeforces

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    int n;
    cin >> n;
    vector<int> x(n, 0);
    int count = 0;
    int ans = 0;
    int t;
    REP(i, 2*n) {
        cin >> t;
        t--;
        if(x[t]==1) {
            x[t] = 0;
            count--;
        } else {
            count++;
            ans = max(ans, count);
            x[t] = 1;
        }
    }
    cout << ans << endl;
}

B

Problem - B - Codeforces

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    int n;
    cin >> n;
    vector<int> x(n), v(n);
    REP(i, n) cin >> x[i];
    REP(i, n) cin >> v[i];
    

    double lb = 0, ub = 1e9;;
    for(int i=0; i<100; ++i) {
        double t = (lb + ub) / 2.0;
        double L = -numeric_limits<double>::max();
        double R = numeric_limits<double>::max();
        REP(i, n) {
            L = max(x[i] - t * v[i], L);
            R = min(x[i] + t * v[i], R);
        }
        if(L <= R) ub = t;
        else lb = t;
    }
    printf("%.10f\n", lb);
}
  • 二分探索は探索回数で抑えるべき。

C

Problem - A - Codeforces (div1ではA問題)

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

vector<vector<int>> G;
vector<int> C;
vector<set<int>> ban;
int ans = 1;

void dfs(int v, int c, int p) {
    C[v] = c;
    int t = 0;
    for(auto i : G[v]) {
        if(C[i] == -1) {
            do {t++;} while(t==c || t==p);
            dfs(i, t, c);
        }
    }
    ans = max(t, ans);
}

int main(void) {
    int n;
    scanf("%d", &n);
    G.resize(n);
    C.resize(n, -1);
    ban.resize(n);
    REP(i, n-1) {
        int x, y;
        scanf("%d %d", &x, &y);
        x--; y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(0, 1, -1);
    cout << ans << endl;
    cout << C[0];
    for(int i=1; i<n; ++i) printf(" %d", C[i]);
    printf("\n");
}
  • 方針は合っていたみたいだが実装が良くなかった。反省。

ABC 008

abc008.contest.atcoder.jp

A問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n); i>=0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int S, T;
    cin >> S >> T;
    cout << T-S+1 << endl;
}

Submission #1025991 - AtCoder Beginner Contest 008 | AtCoder

B問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n); i>=0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    map<string, int> S;
    REP(i, N) {
        string s;
        cin >> s;
        S[s]++;
    }
    string name;
    int ans = 0;
    for(map<string, int>::iterator it = S.begin(); it != S.end(); ++it) {
        if(it->second > ans) {
            ans = it->second;
            name = it->first;
        }
    }
    cout << name << endl;
}

Submission #1026002 - AtCoder Beginner Contest 008 | AtCoder

C問題

C問題とは思えない難易度。解説を見てその通りに実装した

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n); i>=0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

int main(void) {
    int N;
    cin >> N;
    vector<int> C(N);
    REP(i, N) cin >> C[i];
    double ans = 0;
    REP(i, N) {
        int S = 0;
        REP(j, N) {
            if(i != j && C[i] % C[j] == 0) S++;
        }
        if(S%2 == 1) ans += 0.5;
        else ans += double(S+2.0)/(2.0*S+2.0);
    }
    printf("%.10f\n", ans);
}

Submission #1030429 - AtCoder Beginner Contest 008 | AtCoder

D問題

領域内にある採掘機全てについて、「その採掘機で取れる金塊+残りの長方形4つについての最大金塊数」の最大値を求める関数を作ってメモ化再帰。 座標圧縮のためにtupleを使った。

#include <bits/stdc++.h>
#include <tuple>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n); i>=0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int W, H;
int N;
int X[81], Y[81];
 
typedef tuple<int, int, int, int> T;
map<T, int> c;
 
int dp(int i, int j, int w, int h) {
    T t = make_tuple(i, j, w, h);
    if(c.count(t) == 1) return c[t];
    int ret = 0;
    REP(k, N) {
        int s = X[k]; int t = Y[k];
        if(s >= i && s <= w && t >= j && t <= h) {
            ret = max(ret, w+h-i-j+1 + dp(i, j, s-1, t-1) + dp(s+1, j, w, t-1)
                                     + dp(i, t+1, s-1, h) + dp(s+1, t+1, w, h));
        }
    }
    return (c[t] = ret);
}
 
int main(void) {
    cin >> W >> H;
    cin >> N;
    REP(i, N) cin >> X[i] >> Y[i];
    cout << dp(1, 1, W, H) << endl;
}

Submission #1033456 - AtCoder Beginner Contest 008 | AtCoder

ABC 007

abc007.contest.atcoder.jp

A問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int n;
    cin >> n;
    cout << n-1 << endl;
}

Submission #1025099 - AtCoder Beginner Contest 007 | AtCoder

B問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    string A;
    cin >> A;
    if(A == "a") cout << -1 << endl;
    else cout << "a" << endl;
}

Submission #1025101 - AtCoder Beginner Contest 007 | AtCoder

C問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
typedef pair<int, int> P;
 
char c[51][51];
int v[51][51];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int main(void) {
    int R, C, sx, sy, gx, gy;
    cin >> R >> C >> sy >> sx >> gy >> gx;
 
    REP(i, R) {
        REP(j, C) {
            cin >> c[i][j];
            v[i][j] = -1;
        }
    }
 
    sx--; sy--; gy--; gx--;
 
    queue<P> que;
    que.push(P(sy, sx));
    v[sy][sx] = 0;
    while(true) {
        P p = que.front(); que.pop();
        int y = p.first;
        int x = p.second;
        int s = v[y][x];
        if(x == gx && y == gy) {
            cout << s << endl;
            return 0;
        }
        REP(i, 4) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx < 0 || nx >= C || ny < 0 || ny >= R
                || v[ny][nx] != -1 || c[ny][nx] == '#') continue;
            que.push(P(ny, nx));
            v[ny][nx] = s+1;
        }
    }
}

Submission #1025116 - AtCoder Beginner Contest 007 | AtCoder

D問題

  •  [A, B]に含まれる禁止された数(4または9が含まれる数)の個数を数え上げる
  •  [0, A]に含まれる禁止された数を求める関数f(A)を作ればf(B)-f(A-1)が答え
  • f(A)の作り方を考えるために例としてA=3456の場合を考える
  • A=3256のときは、A=2999までの禁止された数とA=456までの禁止された数を数えればよい。
  • このように、同じ桁数の数についてのカウントと、違う桁数の数についてのカウントを分けて再帰的に数えていく。
  • A=2999までのときは0〜9991000〜19992000〜2999にそれぞれ 1000 - 8^3個の禁止された数がある
  • A=456までのときは最上位が禁止された数なのでA=399までの禁止された数の個数と400〜456の数の個数の和が禁止された数の個数である。
  • したがって、最上位の数が4 or 9のときとそれ以外のときで再帰するかどうかが変わる
  • 「同じ桁数の数についてのカウント」で最上位の桁が4 or 9の数は全て禁止された数になるのでカウント時に8のべき乗を引かなくて良い。それを表すために最上位の桁に応じた引く回数を配列cntに入れておく。
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n); i>=0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int cnt[] = {0, 1, 2, 3, 4, 4, 5, 6, 7, 8};
 
ll f(ll n) {
    if(n == 0) return 0;
 
    ll size = 1;
    ll ok = 1;
    while(n/size >= 10) {
        size *= 10;
        ok *= 8;
    }
    ll msd = n / size;
 
    ll ret = size * msd - ok * cnt[msd];
 
    ll rem_digit = n - msd * size;
 
    if(msd == 4 || msd == 9) {
        return ret + (rem_digit + 1);
    } else {
        return ret + f(rem_digit);
    }
}
 
 
int main(void) {
    ll A, B;
    cin >> A >> B;
    cout << f(B) - f(A-1) << endl;
}

Submission #1025963 - AtCoder Beginner Contest 007 | AtCoder

ABC 006

abc006.contest.atcoder.jp

A問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    cout << (N%3 == 0 ? "YES" : "NO") << endl;
}

Submission #1025003 - AtCoder Beginner Contest 006 | AtCoder

B問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int a[1000010];
int main(void) {
    int n;
    cin >> n;
    a[1] = a[2] = 0;
    a[3] = 1;
    FOR(i, 4, n+1) {
        a[i] = (a[i-1] + a[i-2] + a[i-3]) % 10007;
    }
    cout << a[n] << endl;
}

Submission #1025009 - AtCoder Beginner Contest 006 | AtCoder

C問題

全てのbに対して解が存在するか調べる。

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N, M;
    cin >> N >> M;
    int a, b, c;
    REP(b, N+1) {
        int t = M - 3*b;
        if(t % 2 != 0) continue;
        c = t/2 - (N-b);
        a = (N-b) - c;
        if(a >= 0 && c >= 0) {
            printf("%d %d %d\n", a, b, c);
            return 0;
        }
    }
    a = b = c = -1;
    printf("%d %d %d\n", a, b, c);
}

D問題

最長増加部分列問題 (Longest Increasing Subsequence) という典型問題らしい。

  • k枚抜いたらソート済みになる最小のkが求まれば、k枚を適切な位置に挿入することで全てソート済みの列が作れるからkが答えになる。
  • 「今まで見たカードまでで作れる長さiのソート済み部分列の最後の数字の最小値」を格納するdp[i]を用意しておいてカードを前から見て埋めていく。
  • カードcを見ているとき、「dp[i-1] < c < dp[i+1]を満たす最小のi」に埋めるので二分探索で行う
  • 埋まっている数の最大値が最小数のカードを抜いた後の残り枚数なので、Nから最大値を引くと答えになる
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
int main(void) {
    int N;
    cin >> N;
    vector<int>c(N);
    REP(i, N) cin >> c[i];
    vector<int> dp(N+1, 1e9);
    dp[0] = -1e9;
    REP(i, N) {
        int k = c[i];
        int l = 0, r = N+1;
        while(l < r) {
            int m = (l + r) / 2;
            if(k < dp[m]) r = m;
            else l = m+1;
        }
        dp[l] = k;
    }
    int ans = 0;
    REP(i, N+1) {
        if(dp[i] != 1e9) ans = i;
    }
    cout << N-ans << endl;
}

Submission #1025896 - AtCoder Beginner Contest 006 | AtCoder

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