2018-05-01

CODE FESTIVAL 2017 Elimination Tournament Round 1: D - Ancient Tree Record

https://atcoder.jp/contests/cf17-tournament-round1-open/tasks/asaporo2_d

問題概要

N頂点の木とN要素の数列Sが与えられる。木のすべての辺に整数の長さを割り当てて、Siが木の頂点iとすべての頂点との最短距離の和と等しくなるようにせよ。与えられる入力においてはそのような割り当て方がただひとつ存在することが保証される。

N <= 10⁵

解法

ある頂点の組(a, b)を結ぶ辺eに注目すると、「Saの計算過程においてe以外の辺を通る回数」と「Sbの計算過程においてe以外の辺を通る回数」は等しい。また「Saの計算過程においてeを通る回数」はaから見てbの向こう側にある頂点の数に等しく、「Sbの計算過程においてeを通る回数」はbから見てaの向こう側にある頂点の数に等しい。よってSaとSbの差を取ったあと、eを通る回数の差でそれを割ればeの長さが一意に決定できる。

一点例外として、辺eの繋ぐ頂点(a, b)が両方とも木の中心である場合は注意が必要で、この場合SaもSbもeを通る回数も同じであるため上の方法では計算できない。しかしこの場合にも他のすべての辺は上の方法で求めることができるので、先にそれらを求めておけば残る辺eもそこから計算できる。

感想

なんか解けた、嬉しい　木の問題は辺を通る回数に着目するのが重要テクのひとつっぽいですね

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

void main() {
    auto N = readln.chomp.to!int;
    auto E = new Tuple!(int, int)[](N-1);
    auto G = new Tuple!(int, int)[][](N);
    foreach (i; 0..N-1) {
        auto s = readln.split.map!(to!int);
        G[s[0]-1] ~= tuple(s[1]-1, i);
        G[s[1]-1] ~= tuple(s[0]-1, i);
        E[i] = tuple(s[0]-1, s[1]-1);
    }
    auto S = readln.split.map!(to!long).array;

    if (N == 2) {
        writeln(S[0]);
        return;
    }
    
    auto depth = new int[](N);
    auto sub = new int[](N);
    auto ans = new long[](N-1);
    
    int dfs(int n, int p, int d) {
        depth[n] = d;
        foreach (m; G[n]) if (m[0] != p) sub[n] += dfs(m[0], n, d+1);
        return sub[n] + 1;
    }
    dfs(0, -1, 0);

    long dfs2(int n, int p, long d) {
        long ret = d;
        foreach (m; G[n]) if (m[0] != p) ret += dfs2(m[0], n, d+ans[m[1]]);
        return ret;
    }

    foreach (i, e; E.enumerate) {
        int a = e[0];
        int b = e[1];
        if (S[a] == S[b]) continue; 
        if (depth[a] > depth[b]) swap(a, b);
        long aa = sub[b];
        long bb = N - sub[b] - 2;
        ans[i] = (S[a] - S[b]) / (aa - bb);
    }

    foreach (i, e; E.enumerate) {
        int a = e[0];
        int b = e[1];
        if (S[a] != S[b]) continue;
        if (depth[a] > depth[b]) swap(a, b);
        long aa = dfs2(a, b, 0);
        long bb = dfs2(b, a, 0);
        long ss = aa + bb;
        ans[i] = (S[a] - ss) / (sub[b] + 1);
    }

    ans.each!writeln;
}

2018-05-01

CODE FESTIVAL 2016 Elimination Tournament Round 1: A - グラフ / Graph

問題記録 AtCoder CODE FESTIVAL

問題概要

辺に正整数の重みが設定されたN頂点M辺の無向グラフと、Q個のクエリが与えられる。i個目のクエリでは頂点SiとTiが指定される。各クエリにおいて、「SiまたはTiを始点としたとき、集合に含まれる辺のみを使ってすべての頂点にたどりつくことができる」という条件を満たすように辺集合を選ぶとき、集合に含まれる辺の重みの和の最小値を求めよ。

N <= 4000

M <= 400000

Q <= 100000

解法

クエリ1回であれば最小全域森っぽいものを求めればいけそうだが、それを毎回計算するのは不可能である。ここで重要な発想はSiとTiを同一視して縮約しまうことである。このようにすると「SiまたはTi」という面倒な条件を考える必要がなくなり、単純に縮約後のグラフの最小全域木のコストはいくらになるか、という問題に言い換えることができる。

なおSiとTiを縮約するという操作はSi-Ti間にコスト0の辺を加えると言い換えてもここでは問題がない。後の見通しがよくなるのでここでは後者のやり方を取る。そうすると、各クエリで求める必要があるのは「元のグラフにSi-Ti間のゼロコスト辺を加えたグラフの最小全域木（のコスト）」である。これは各クエリで毎回愚直に求める必要はなく、最初に元のグラフの最小全域木さえ求めておけば簡単に求めることができる。具体的には元のグラフの最小全域木のSi-Ti間にゼロコスト辺を足す。そうするとひとつ辺が余るので取り除いて全体の重みを小さくすることができるようになる。ここで取り除くべき辺は、取り除いても連結のままになる辺のうち、コストがもっとも大きいものである。「取り除いても連結のままになる辺」は初めの最小全域木のうちSiとTiの間にある辺、つまりSi-Tiのパス上にあるいずれかの辺である。Nが小さいのでこれを毎クエリごとにO(N)で求めても十分間に合う。これでO(NQ)で解ける。

感想

縮約、結構現れるテクっぽい

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip, std.regex;

immutable long INF = 1L << 59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto G = new Tuple!(int, long)[][](N);
    foreach (i; 0..M) {
        s = readln.split.map!(to!int);
        G[s[0]-1] ~= tuple(s[1]-1, s[2].to!long);
        G[s[1]-1] ~= tuple(s[0]-1, s[2].to!long);
    }

    long mst_cost = 0;
    auto H = new Tuple!(int, long)[][](N);
    auto P = new Tuple!(int, long)[](N);
    auto D = new int[](N);
    auto used = new bool[](N);
    auto q = new BinaryHeap!(Array!(Tuple!(int, int, long)), "a[2] > b[2]")();
    q.insert(tuple(-1, 0, 0L));

    while (!q.empty) {
        auto t = q.front;
        auto from = t[0];
        auto cur = t[1];
        auto d = t[2];
        q.removeFront;
        if (used[cur]) continue;
        used[cur] = true;
        mst_cost += d;
        if (from != -1) {
            H[from] ~= tuple(cur, d);
            H[cur] ~= tuple(from, d);
        }
        foreach (m; G[cur]) {
            auto tar = m[0];
            auto nd = m[1];
            if (used[tar]) continue;
            q.insert(tuple(cur, tar, nd));
        }
    }

    void dfs(int n, int p, long c, int d) {
        P[n] = tuple(p, c);
        D[n] = d;
        foreach (to; H[n]) if (to[0] != p) dfs(to[0], n, to[1], d+1);
    }

    dfs(0, -1, 0, 0);


    auto Q = readln.chomp.to!int;
    while (Q--) {
        s = readln.split.map!(to!int);
        auto a = s[0]-1;
        auto b = s[1]-1;
        if (D[a] > D[b]) swap(a, b);
        long maxv = -1;
        while (D[b] > D[a]) {
            maxv = max(maxv, P[b][1]);
            b = P[b][0];
        }
        while (a != b) {
            maxv = max(maxv, P[a][1]);
            a = P[a][0];
            maxv = max(maxv, P[b][1]);
            b = P[b][0];
        }
        writeln(mst_cost - maxv);
    }
}

2018-05-01

CODE FESTIVAL 2016 Tournament Round 3: A - ストラックアウト / Struck Out

問題記録 AtCoder CODE FESTIVAL

問題概要

1～Nまでの番号がついたN個のパネルがある。1度のゲームではK回ボールを投げてi回目にパネルjに当てるとi×Aj点が得られ、各回の点の和が得点となる。当てたパネルを順にP1, P2, ..., PK としたとき、1 <= P(i+1) - Pi <= M という条件の下でありうる最大の得点を求めよ。

N, M <= 10⁵

K <= min(300, N)

解法

dp(i, j): i回目にパネルjに当てたときの最大の得点

とすると、dp(i, j) = max(dp(i-1, k) for k in (j-M)～(j-1)) である。セグ木をK本持てば普通にできそうだが、それだと O(KNlongN) で2秒には間に合わない。ここでjの小さいほうから順にdpを更新していく過程を見ていると、dp(i-1)から区間を横にずらしつつ最大値を取っていく形になっていることがわかる。このような場合スライド最小値（ここでは最大値だが）のやり方が使えて、これだと計算量がならしでO(N)になる。これでlogが落ちて答えが求まる。

おまけ：スライド最大値について（たぶん俺にしかわからないので蟻本2版p300を見てください）。

まず両端キュー(deque)を用意する。
このキューには値ではなくインデックスが入る
このキューの並び順は、常に次の条件を満たす
- 左にあるものほど、そのインデックスが指す要素の値が大きい
- 要素の値の大きさが同じ場合は、左にあるものほどインデックス自体が小さい
この条件が満たされている場合、区間の最大値は常にキューの左端に入っているインデックスを参照することでO(1)で得ることができる
既にキューがこの状態になっていると仮定して、区間を右にひとつずらすことを考えると
- まずずれた結果区間から外れたインデックスをキューから削除する。もしキューの左端を見て、そのインデックスがそれであればそのままpopする。そうでなければそのインデックスはもうキューの中にはないので何も操作する必要がない。
- 次に新しく加わるインデックスをキューに追加する。今度は右からキューを見ていって、キューが空になるかあるいはキューの右端インデックスの指す要素の値が新しいインデックスの要素の値より小さい間は右をpopし続ける。止まったらそこに新しいインデックスをpushする。
- 以上の操作では各インデックスについてpushとpopが高々1回ずつしか行われないので、ならしでO(N)となる

感想

まんまとlogをつけてTLEした。ゆきことか昔のABC-Dっぽい教育的問題感がある（スライド最小値名前だけ聞いてシカトしてたので勉強になった）。このくらい狙った設定じゃないとなかなかlog付きだけ落とすぞってのは難しそう

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip, std.regex;

immutable long INF = 1L << 59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto K = s[2];
    auto A = readln.split.map!(to!long).array;

    auto dp = new long[][](2, N);
    dp[0] = A.dup;
    int cur = 0, tar = 1;

    foreach (i; 1..K) {
        dp[tar].fill(-INF);
        auto q = new long[](2*N+10);
        int x = N/2;
        int y = N/2;
        foreach (j; i..N) {
            int a = j - M - 1;
            int b = j - 1;
            if (a >= 0 && x < y && q[x] == a) x++;
            while (x < y && dp[cur][q[y-1]] < dp[cur][b]) y--;
            q[y++] = b;
            dp[tar][j] = dp[cur][q[x]] + A[j] * (i + 1);
        }
        swap(cur, tar);
    }

    dp[cur].reduce!max.writeln;
}

2018-05-01

CODE FESTIVAL 2016 qual A: D - マス目と整数 / Grid and Integers

問題記録 AtCoder CODE FESTIVAL

問題概要

R行C列のグリッドがある。このうちN個のマスに非負整数が書き込まれている。まだ何も書き込まれていない残りすべてのマスに対して、以下のルールを満たしながら数字を書き込むことが可能か判定せよ。ルール1: マスに書き込めるのは非負整数のみ。ルール2: どの2×2のマスを取り出しても、左上＋右下＝右上＋左下が成り立つ。

R, C <= 10⁵

N <= 10⁵

解法

式変形をすると左上－左下＝右上－右下となる。つまりどの2つの行を取ってきても、隣り合う列の要素の差は等しい、ということになる。さらにこれを推移的に適用すると隣り合っているものだけなく、「どんな2つの列a, bに対しても、列aと列bの値の差はすべての行において等しい」（ルール2の言い換え）ということになる。

まずは上で言い換えたルールが既に書き込まれているマスの間で成り立っているかを確かめる。そのために以下のようなグラフを構築する。

頂点がC個（元のマス目の列に対応）
ある行において列a, b (a < b)に数字が書き込まれているとき、a->b に重み(b-a)の辺を、b->aに重み-(b-a)の辺を張る

このとき全部の書き込み同士で辺を張っているとO(N²)になってしまうので、ある行に列同士で辺を張る際は、書き込まれている中での隣接列同士だけに辺を張るようにする（列1, 3, 4に書き込みがあれば1-3, 3-4だけに張って、1-4は張らない）。こうして作ったグラフにおいて、上で言い換えたルールに違反するような矛盾が生じないかをDFSで確認することができる。具体的には以下のような手順で行う。

適当にDFSの始点を選ぶ。スタート時には数0を持っている。
ある頂点を初めて訪れたとき、持っている数をその頂点に割り当ててDFSを続行する
既に訪れている頂点に再び訪れたとき、今持っている数とその頂点に割り当てられている数が同じかどうかチェックする。もし同じであればtrueを返す。もし違っていれば矛盾が生じたことになるのでfalseを返す
この過程においてどこかで1回でもfalseが返ってきたらそもそも書き込まれている数字の時点でルール違反のため、問題の答えはNoとなる

以上の手順によってルール2の違反がないかを確かめることができる。実際には作ったグラフは必ずしも連結ではないので、各連結成分に対しそれぞれ独立に上のDFSを行う必要がある。もしここでルール違反がなかった場合、今度はルール1の違反がないかを確認する。つまり上で求めた差分関係のルールに従ってマスを埋めていったとき、どこかで非負整数が現れないかをチェックする。これは既に書き込まれているN個のマスをそれぞれ起点として、ルールに従って埋めたとき現れる最小値が0以上であることを確かめればよい。実装では先ほどのDFSで求めた相対的な値の割り当て表を再利用して、連結成分の中の最小値ひとつをチェックするだけでよい（たとえば今見ている既に書き込まれたマスの列に割り当てられた相対値が3, 同じ連結成分の中で最小の相対値が-5のとき、実際の最小値は（マスの数字-8）になる。連結成分のまとめにはUnionFind等を使う。

感想

最初等差数列だろとか思って全然通らなかった、あとあんまりエレガント感ないけどこれでいいんかいなと思いつつ地道に考察進めて書いたのが通ってよかった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long MOD = 10^^9 + 7;


void main() {
    auto s = readln.split.map!(to!int);
    auto R = s[0];
    auto C = s[1];
    auto N = readln.chomp.to!int;
    auto A = new Tuple!(int, long)[][](R);

    foreach (i; 0..N) {
        s = readln.split.map!(to!int);
        auto r = s[0] - 1;
        auto c = s[1] - 1;
        auto a = s[2].to!long;
        A[r] ~= tuple(c, a);
    }
    foreach (i; 0..R) A[i].sort!"a[0] < b[0]";

    auto G = new Tuple!(int, long)[][](C);

    foreach (i; 0..R) {
        foreach (j; 0..A[i].length.to!int-1) {
            G[A[i][j][0]] ~= tuple(A[i][j+1][0], A[i][j+1][1] - A[i][j][1]);
            G[A[i][j+1][0]] ~= tuple(A[i][j][0], A[i][j][1] - A[i][j+1][1]);
        }
    }

    auto used = new bool[](C);
    auto vals = new long[](C);

    bool dfs(int n, long x) {
        if (used[n]) return vals[n] == x;
        used[n] = true;
        vals[n] = x;
        foreach (m; G[n]) if (!dfs(m[0], x+m[1])) return false;
        return true;
    }

    foreach (i; 0..C) if (!used[i] && !dfs(i, 0)) {writeln("No"); return;}

    used.fill(false);
    auto mins = new long[](C);
    int[] g;

    long dfs2(int n, long x) {
        if (used[n]) return x;
        x = min(x, vals[n]);
        used[n] = true;
        g ~= n;
        foreach (m; G[n]) x = min(x, dfs2(m[0], x));
        return x;
    }

    foreach (i; 0..C) {
        if (used[i]) continue;
        g = [];
        auto m = dfs2(i, 1L<<59);
        foreach (j; g) mins[j] = m;
    }

    foreach (i; 0..R) {
        foreach (a; A[i]) {
            auto m = mins[a[0]];
            auto x = a[1] - (vals[a[0]] - mins[a[0]]);
            if (x < 0) {
                writeln("No");
                return;
            }
        }
    }

    writeln("Yes");
}

2018-05-01

天下一プログラマーコンテスト2016本戦: D - 右往左往

AtCoder 問題記録天下一プログラマーコンテスト天下一プログラマーコンテスト2016本戦

問題概要

N個のタスクと2つの部屋がある。タスクiは部屋1で行うとAi, 部屋2で行うとBi時間かかる。またi回目の部屋の移動には C×(i-1)+D 時間かかる。またタスクにはM個の依存関係(Xi, Yi)があり、タスクYiはタスクXiの完了後でないと行えない。初めにいる部屋とタスクを行う順番を自由に選べるとき、タスク完了までの時間を最小化せよ。

解法

dp(mask, i, j) = タスク集合maskが完了、部屋をi回移動、現在部屋jにいる、という条件の下での最小時間

でbitDPをする。O(2^N×N²)でかなりギリギリだが制限時間も長めなのでたぶんこれが想定解だと思います（この問題は公式のも野良のも解説が見つけられなかった）。一点ハマったところがあって、DPの中で次にタスクxをやろうとするとき、依存関係のあるタスクが全部終わってるかを見る必要があるわけだが、これを愚直に1個1個見てるとオーダーに余計なNがひとつついて間に合わない。なので依存関係（そのタスクに取り掛かるために完了していないといけないタスク番号の集合）はbitの形で持っておいて、maskと&をとっても変化しないかでO(1)でチェックする必要がある。

感想

D言語で通せず　じゃっかんの虚無みがある

コード (C++)

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

int T[20][2]; 
int G[20];
int dp[1<<20][21][2];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    const int INF = 1 << 29;

    int N, M, C, D;
    cin >> N >> M >> C >> D;
    REP(i, N) REP(j, 2) cin >> T[i][j];
    REP(i, M) {
        int a, b; cin >> a >> b; --a; --b;
        G[b] |= (1 << a);
    }

    for (int i = 0; i < (1<<N); ++i)
        for (int j = 0; j < N; ++j)
            for (int k = 0; k < 2; ++k)
                dp[i][j][k] = INF;
    dp[0][0][0] = dp[0][0][1] = 0;
    
    for (int mask = 0; mask < (1 << N); ++mask) {
        for (int i = 0; i < N; ++i) {
            for (int a = 0; a < 2; ++a) {
                if (dp[mask][i][a] == INF) continue;
                for (int j = 0; j < N; ++j) {
                    if (mask & (1 << j)) continue;
                    if ((mask & G[j]) != G[j]) continue;
                    for (int b = 0; b < 2; ++b) {
                        if (a == b) {
                            dp[mask|(1<<j)][i][b] = min(dp[mask|(1<<j)][i][b],
                                                        dp[mask][i][a] + T[j][b]);
                        } else if (i < N-1) {
                            dp[mask|(1<<j)][i+1][b] = min(dp[mask|(1<<j)][i+1][b],
                                                          dp[mask][i][a] + T[j][b] + C*i+D);
                        }
                    }
                }
            }
        }
    }

    int ans = INF;
    REP (i, N) REP(j, 2) ans = min(ans, dp[(1<<N)-1][i][j]);
    cout << ans << endl;
}

2018-05-01

DISCO presents ディスカバリーチャンネルコードコンテスト2016 本戦: C - 01文字列

問題記録 AtCoder DDCC2016本戦

問題概要

空文字列Sに対して以下の3種類の操作を好きな順番で好きな回数行い、与えられた文字列Tに一致させたい。そのための最小コストを求めよ。 1. Sの先頭に0を挿入する(コストA)。 2. Sの末尾に1を挿入する(コストB)。 3. Sの01をすべてflipする(コストC)

|T| <= 2×10⁵

解法

操作1の回数をa回と決め打つと、操作bの回数は|T|-b回に定まる（Sの長さは操作1, 操作2によってしか増えないため）。さらに操作の特性上、先頭a文字が操作1由来、後ろのb文字が操作2由来であることも確定する。この時点でコストAはa回, コストBはb回支払うことが確定し、問題は操作3の回数をどれだけ少なくできるかという点に移る。操作3が反転であることを考えると明らかに0と1の切れ目では反転を行う必要があり、そうでないところでは必要がない。またaとbの切断箇所で隣り合う文字が同一の場合、どちらかが1回待たなければならない。とかの面倒なケースを処理しつつ計算する。これはO(1)でできるので操作1の決め打ち回数を全探索してO(N).

感想

なんかごちゃごちゃしてしまってつらかった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

void main() {
    auto s = readln.split.map!(to!long);
    auto A = s[0];
    auto B = s[1];
    auto C = s[2];
    auto S = readln.chomp.map!(c => (c - '0').to!int).array;
    auto N = S.length.to!int;
    long ans = 1L << 59;

    auto seg1 = new int[](N);
    auto seg2 = new int[](N);
    seg1[0] = 1;
    seg2[N-1] = 1;
    foreach (i; 1..N) seg1[i] = S[i] == S[i-1] ? seg1[i-1] : seg1[i-1] + 1;
    foreach_reverse (i; 0..N-1) seg2[i] = S[i] == S[i+1] ? seg2[i+1] : seg2[i+1] + 1; 
    
    foreach (a; 0..N+1) { // 先頭に追加する回数
        int b = N - a; // 末尾に追加する回数
        int s1 = a == 0 ? 0 : seg1[a-1];
        int s2 = a == N ? 0 : seg2[a];
        int flip = max(s1, s2) - 1;
        if (a > 0 && a < N && s1 == s2 && S[a] == S[a-1]) flip += 1;
        if (s1 >= s2 && S[0] == 1) flip += 1;
        if (s1 < s2 && S[N-1] == 0) flip += 1;
        ans = min(ans, a * A + b * B + flip * C);
    }

    ans.writeln;
}

2018-02-08

yukicoder No.127 門松もどき

問題記録 yukicoder 区間DP

https://yukicoder.me/problems/no/127

問題概要

N要素の正整数列Aが与えられる。Aの部分列で門松もどきであるようなものの最大の長さを求めよ。ただし門松もどきとは各要素の大きさが「左端→右端→左から2番目→右から2番目→...」で昇順になっているもの、または「右端→左端→右から2番目→左から2番目→...」で昇順になっているものをいう。

N <= 2000

解法

DPを2つ持って区間DPをする。

dp_left(l, r): 最も小さい要素がA[l]で、右端の位置がr以下であるような最長の門松もどきの長さ
dp_right(l, r): 最も小さい要素がA[r]で、左端の位置がl以上であるような最長の門松もどきの長さ

要するに最小の要素を固定した区間DPをする。このとき例えばdp_left(l, r)は A[l] < A[r] であるとき dp_right(l+1, r) + 1 を値にとることができる。どういうことかというとA[r] が最小であるような[l+1, r]の範囲の門松もどきに対して、その左にそれより小さいA[l]をくっつけるというイメージである。

門松もどきが伸びるのはこのパターンだけなので、あとは含む区間の最大値を引き継ぐようにすればいい。全体でO(N²).

感想

右が一番小さいやつにそれより小さい左をくっつければいいっていうの確かにそうなんだけど思いつかなかった

ていうかこれもしかして左最小あるいは右最小の片方だけの問題にすると誘導がなくなってむしろ難しくなるんですかね？

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long MOD = 10^^9 + 7;

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!int).array;

    auto dp1 = new int[][](N, N);
    auto dp2 = new int[][](N, N);
    foreach (i; 0..N) dp1[i][i] = dp2[i][i] = 1;

    foreach (len; 2..N+1) {
        foreach (l; 0..N-len+1) {
            int r = l + len - 1;
            dp1[l][r] = dp1[l][r-1];
            if (A[l] < A[r]) dp1[l][r] = max(dp1[l][r], dp2[l+1][r] + 1);
            dp2[l][r] = dp2[l+1][r];
            if (A[l] > A[r]) dp2[l][r] = max(dp2[l][r], dp1[l][r-1] + 1);
        } 
    }

    int ans = 0;
    foreach (i; 0..N) foreach (j; 0..N) ans = max(ans, dp1[i][j], dp2[i][j]);
    ans.writeln;
}