キーエンス プログラミング コンテスト 2020 B - Robot Arms (緑色, 200 点)

区間スケジューリング問題そのものだった！！！
...とはいえ 200 点というのは衝撃！！！

問題へのリンク

問題概要

ある工場では、 数直線上に 個のロボットが設置されている。 ロボット は座標 に設置されていて、左右に長さ のアームを伸ばしている。

これらのロボットのうちいくつかを取り除き、 残ったどの 2 つのロボットについても、アームが共通部分を持たないようにしたい。取り除かずに残せるロボットの個数の最大値を求めよ。

制約

• 

考えたこと

つまり、以下の 個の区間についての、区間スケジューリング問題 (蟻本参照) ということになる。

• 
• 
• ...
• 

区間スケジューリング問題とは、いくつかの区間の中から、重ならないように最大で何個選べるかを問う問題である。

区間スケジューリング問題の解き方

区間を「終端が早い順」にソートして、とれる順にとる Greedy で解くことができる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pll = pair<long long, long long>;

int main() {
    int N; cin >> N;
    vector<pll> v(N);
    for (int i = 0; i < N; ++i) {
        long long a, l;
        cin >> a >> l;
        v[i] = {a - l, a + l};
    }

    // 区間を右端の小さい順にソート
    sort(v.begin(), v.end(), [](pll a, pll b) {
            return a.second < b.second;});

    // cur := 現在選んでいる区間のうち、最も右にあるやつの右端
    int res = 0;
    long long cur = -(1LL<<60);
    for (int i = 0; i < N; ++i) {
        if (cur > v[i].first) continue; // 被るやつは飛ばす
        ++res;
        cur = v[i].second;
    }
    cout << res << endl;
}

yukicoder No.973 余興

Deque に似てる。けど、Deque と違って、先手と後手がとりうる選択肢は常に一緒 (最初、先手は左から、後手は右からと誤読した)。

問題へのリンク

問題概要

長さ の数列に対し、先手は左から順に、後手は右から順にとっていく。どのターンもとった値の合計値が 以下でなければらなない。最後の 1 ピースをとってしまった方の負けである。

双方最善を尽くしたとき、どちらが勝つか？

制約

• 

考えたこと

いかにも、こんな感じの DP をしたくなる。

• dp[ l ][ r ]:= 区間 [l, r) が残った状態から勝てるかどうか？

このままだと、先手・後手が手番において「どこまで取るか」をきちんと考えた DP 遷移をしようと思うと になってしまう。ここでよくある DP 高速化をする。 通りの遷移を高速化するのは非常によく見られる典型ではある。

多分累積和とかで良さそうだけど、ここでは BIT でやってみた。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <class Abel> struct BIT {
    const Abel UNITY_SUM = 0;                       // to be set
    vector<Abel> dat;
    
    /* [1, n] */
    BIT(int n) : dat(n + 1, UNITY_SUM) { }
    void init(int n) { dat.assign(n + 1, UNITY_SUM); }
    
    /* a is 1-indexed */
    inline void add(int a, Abel x) {
        for (int i = a; i < (int)dat.size(); i += i & -i)
            dat[i] = dat[i] + x;
    }
    
    /* [1, a], a is 1-indexed */
    inline Abel sum(int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i)
            res = res + dat[i];
        return res;
    }
    
    /* [a, b), a and b are 1-indexed */
    inline Abel sum(int a, int b) {
        return sum(b - 1) - sum(a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat.size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int N;
long long X;
vector<long long> a, s;
vector<int> l2r, r2l;

bool solve() {
    l2r.assign(N+1, -1), r2l.assign(N+1, -1);
    int r = 0;
    for (int l = 0; l < N; ++l) {
        while (r < N && s[r + 1] - s[l] <= X) {
            ++r;
            r2l[r] = l;
        }
        l2r[l] = r;
    }

    vector<BIT<int> > left(N+5, BIT<int>(N+5));
    vector<BIT<int> > right(N+5, BIT<int>(N+5));
    for (int l = 0; l <= N; ++l) left[l].add(l+1, 1);
    for (int r = 0; r <= N; ++r) right[r].add(r+1, 1);
    for (int bet = 1; bet <= N; ++bet) {
        for (int l = 0; l+bet <= N; ++l) {
            int r = l+bet;
            
            // l+1, ..., min(l2r[l], r) に「負け」があれば OK
            int mi = min(l2r[l], r);
            int tmp1 = (mi-l) - right[r].sum(l+2, mi+2);

            // max(l, r2l[r]), ..., r-1 に「負け」があれば OK
            int ma = max(l, r2l[r]);
            int tmp2 = (r-ma) - left[l].sum(ma+1, r+1);

            // judge
            if (tmp1 + tmp2) left[l].add(r+1, 1), right[r].add(l+1, 1);
        }
    }
    return left[0].sum(N+1, N+2);
}

int main() {
    while (cin >> N >> X) {
        a.resize(N); s.assign(N+1, 0);
        for (int i = 0; i < N; ++i) cin >> a[i], s[i+1] = s[i] + a[i];
        if (solve()) cout << "A" << endl;
        else cout << "B" << endl;
    }
}

yukicoder No.972 選び方のスコア

すごく面白かった！！！

問題へのリンク

問題概要

長さ の数列 が与えられる。ここから何個か選ぶ。選んだ値を としたとき、そのスコアを以下のように定義する。

• 選んだ値のメディアンを とする
  • 奇数個の場合は真ん中の値
  • 偶数個の場合は真ん中の 2 つの値の平均値
• スコアは とする

スコアの最大値を求めよ。

制約

• 

考えたこと

面白そう！！！！！！
とりあえずメディアンを固定して考えて見ることにした。偶数個を選ぶときはちょっと考えづらいので、まずは、奇数個選ぶ場合を考えて見る。メディアンの index を固定して考えて見る。このとき、まず

• 数列を大きい順に k 個
• 数列の median 以降から k 個

を選ぶ中に最適解があることがわかる。

そしてこの の値って、実は全部調べなくてもわかる。数列の値を median の値を 0 にして、そこからの差分で表したとき、「左側 < 右側」となる瞬間から先は採用しない方がいい。この切れ目を二分探索で求めることができる。

偶数個選ぶとき

実は奇数個選ぶ場合のみ考えればよい。まず、奇数個の場合は、「真ん中の 2 つの値」を固定して考えることになる。しかしこの場合、片方のみにすることでスコアが減少することはない！！！

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }


int N;
vector<long long> a, s;

long long solve() {
    sort(a.begin(), a.end(), greater<long long>());
    s.assign(N+1, 0);
    for (int i = 0; i < N; ++i) s[i+1] = s[i] + a[i];
    long long res = 0;
    for (int median = 1; median < N-1; ++median) {
        int mak = min(median, N-1-median);
        int left = 1, right = mak + 1;
        while (right - left > 1) {
            int mid = (left + right) / 2;
            if (a[mid-1] - a[median] >= a[median] - a[median+mid]) left = mid;
            else right = mid;
        }
        long long tmp = s[median+1+left] - s[median+1] + s[left];
        tmp -= a[median] * left * 2;
        chmax(res, tmp);
    }
    return res;
}

int main() {
    while (cin >> N) {
        a.resize(N);
        for (int i = 0; i < N; ++i) cin >> a[i];
        cout << solve() << endl;
    }
}

Educational Codeforces Round 80 F. Red-Blue Graph (R2900)

需要供給を考え、さらに最小流量制約もある最小費用フロー！！！

問題へのリンク

問題概要

左頂点数 、右頂点数 、辺数 の二部グラフが与えられる。各頂点は「赤」または「青」または「白」に塗られている。

さて、各辺は最初は白色である。そのうちの何本かを「赤」や「青」に塗って以下の条件を満たすようにしたい。

• どの「赤」の頂点についても、その頂点に接続している赤辺の本数が、青辺の本数よりも多い
• どの「青」の頂点についても、その頂点に接続している青辺の本数が、赤辺の本数よりも多い
• 「白」の頂点についてはそのような制約はない

赤く塗るコストは 1 本あたり で、青く塗るコストは 1 本あたり である。最小コストで実現する方法を求めよ (復元もせよ)。

制約

• 

考えたこと

各辺について

• 赤色に塗る： 左から右へ 1 のフローを流す (左から右向きにコスト の辺)
• 青色に塗る： 右から左へ 1 のフローを流す (右から左向きにコスト の辺)

という風に考えてみる。そうすると条件は

• 左側の赤頂点： 流量が +1 以上のソース点
• 左側の青頂点： 流量が -1 以上のシンク点
• 左側の白頂点： 流量任意
• 右側の赤頂点： 流量が -1 以上のシンク点
• 右側の青頂点： 流量が +1 以上のソース点
• 右側の白頂点： 流量任意

という需要供給を満たすような最小費用流を求める、という問題になる。需要供給付き最小費用流の求め方は、

• ソースに対応するスーパーノード を作って、流量 のソース点 に対しては、 から へ容量 の辺を張る
• シンクに対応するスーパーノード を作って、流量 のシンク点 に対しては、 から へ容量 の辺を張る

としたグラフ上で、 から への流量 の最小費用流を求めればよい。今回は、需要供給量が「下限制約付き」なので、それに関する対策も行う。ひとまず、上記と同じように

• ソース点については、 から下限容量 1 の辺を張る
• シンク点については、 へと下限容量 1 の辺を張る

という風にしておく。また流量任意の頂点 に対しては、

• から へ上限容量 の辺を張る
• から へ上限容量 の辺を張る

としておく。さらに、下限制約さえ満たせば から への流量は自由なので、 から へ上限容量 の辺を張る。こうして得られたグラフで、最小費用循環流を求める問題とみなすことができる。次に、下限容量付きの辺を処理する。

下限制約付きフローの考え方

下限制約付きフローの考え方はいたってシンプルで、

• その分の流量だけあらかじめ流してしまう
• 上限制約の値をその分だけ減らす (今回は上限制約は なので変化なし)

という風にする。あらかじめ流したことで発生する需要供給についてはまた改めて補正する。

---

辺 について、下限流量制約 がついているとき、 を流してしまったことにする。このとき

• は のソース点
• は のシンク点

となるので、それに対応するスーパーノードを用意して対応する

---

という感じ。今回結局、2 組のスーパーノード を用意して、以下のようにしたグラフにおいて、 から へと、流量 (「赤」と「青」の頂点の個数の合計値) の最小費用流を求めれば OK。

• 下限流量 1 のソース点となった頂点 (左の赤と右の青) に対しては
  • には容量 の辺を張る
  • から へ、容量 の辺を張る
  • から へ、容量 の辺を張る (最後にまとめる)
• 下限流量 1 のシンク点となった頂点 (左の青と右の赤) に対しては
  • には容量 の辺を張る
  • から へ、容量 の辺を張る
  • から へ、容量 の辺を張る (最後にまとめる)
• 流量任意の頂点 (左右の白) に対しては
  • から へ、容量 の辺を張る
  • から へ、容量 の辺を張る
• 左側頂点 と右側頂点 からなる辺については、
  • から へは、容量 、コスト の辺を張る
  • から へは、容量 、コスト の辺を張る
• 最後に、 から へ容量 の辺を張る

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

// edge class (for network-flow)
template<class FLOWTYPE, class COSTTYPE> struct Edge {
    int rev, from, to, id;
    FLOWTYPE cap, icap;
    COSTTYPE cost;
    Edge(int r, int f, int t, FLOWTYPE ca, COSTTYPE co, int id = -1) :
        rev(r), from(f), to(t), cap(ca), icap(ca), cost(co), id(id) {}
    friend ostream& operator << (ostream& s, const Edge& E) {
        if (E.cap > 0)
            return s << E.from << "->" << E.to <<
                '(' << E.cap << ',' << E.cost << ')';
        else return s;
    }
};

// graph class (for network-flow)
template<class FLOWTYPE, class COSTTYPE> struct Graph {
    vector<vector<Edge<FLOWTYPE, COSTTYPE> > > list;
    
    Graph(int n = 0) : list(n) { }
    void init(int n = 0) { list.clear(); list.resize(n); }
    void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; }
    inline vector<Edge<FLOWTYPE, COSTTYPE> >& operator [] (int i) { return list[i]; }
    inline const size_t size() const { return list.size(); }
    
    inline Edge<FLOWTYPE, COSTTYPE> &redge(const Edge<FLOWTYPE, COSTTYPE> &e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    
    void addedge(int from, int to, FLOWTYPE cap, COSTTYPE cost, int id = -1) {
        list[from].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[to].size(), from, to, cap, cost, id));
        list[to].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[from].size() - 1, to, from, 0, -cost));
    }
    
    void add_undirected_edge(int from, int to, FLOWTYPE cap, COSTTYPE cost, int id = -1) {
        list[from].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[to].size(), from, to, cap, cost, id));
        list[to].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[from].size() - 1, to, from, cap, cost, id));
    }

    friend ostream& operator << (ostream& s, const Graph& G) {
        s << endl;
        for (int i = 0; i < G.size(); ++i) {
            s << i << ":";
            for (auto e : G.list[i]) s << " " << e;
            s << endl;
        }
        return s;
    }   
};

// min-cost flow (primal-dual)
template<class FLOWTYPE, class COSTTYPE> COSTTYPE MinCostFlow(Graph<FLOWTYPE, COSTTYPE> &G, int s, int t, FLOWTYPE f) {
    int n = (int)G.size();
    vector<COSTTYPE> pot(n, 0), dist(n, -1);
    vector<int> prevv(n), preve(n);
    COSTTYPE res = 0;
    while (f > 0) {
        priority_queue<pair<COSTTYPE,int>, vector<pair<COSTTYPE,int> >, greater<pair<COSTTYPE,int> > > que;
        dist.assign(n, -1);
        dist[s] = 0;
        que.push(make_pair(0,s));
        while(!que.empty()) {
            pair<COSTTYPE,int> p = que.top();
            que.pop();
            int v = p.second;
            if (dist[v] < p.first) continue;
            for (int i = 0; i < G[v].size(); ++i) {
                auto e = G[v][i];
                if (e.cap > 0 && (dist[e.to] < 0 || dist[e.to] > dist[v] + e.cost + pot[v] - pot[e.to])) {
                    dist[e.to] = dist[v] + e.cost + pot[v] - pot[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.push(make_pair(dist[e.to], e.to));
                }
            }
        }
        if (dist[t] < 0) return -1;
        for (int v = 0; v < n; ++v) pot[v] += dist[v];
        FLOWTYPE d = f;
        for (int v = t; v != s; v = prevv[v]) {
            d = min(d, G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += pot[t] * d;
        for (int v = t; v != s; v = prevv[v]) {
            Edge<FLOWTYPE,COSTTYPE> &e = G[prevv[v]][preve[v]];
            Edge<FLOWTYPE,COSTTYPE> &re = G.redge(e);
            e.cap -= d;
            re.cap += d;
        }
    }
    return res;
}


int main() {
    int N1, N2, M;
    long long r, b;
    cin >> N1 >> N2 >> M >> r >> b;
    string ls, rs;
    cin >> ls >> rs;

    const long long INF = 1<<29;
    Graph<long long, long long> G(N1 + N2 + 4);
    int s = N1 + N2, t = N1 + N2 + 1, ss = N1 + N2 + 2, tt = N1 + N2 + 3;
    long long nS = 0, nT = 0;
    for (int v = 0; v < N1; ++v) {
        if (ls[v] == 'R') {
            ++nS;
            G.addedge(s, v, INF, 0);
            G.addedge(ss, v, 1, 0);
        }
        else if (ls[v] == 'B') {
            ++nT;
            G.addedge(v, t, INF, 0);
            G.addedge(v, tt, 1, 0);
        }
        else {
            G.addedge(s, v, INF, 0);
            G.addedge(v, t, INF, 0);
        }
    }
    for (int v = 0; v < N2; ++v) {
        if (rs[v] == 'B') {
            ++nS;
            G.addedge(s, v+N1, INF, 0);
            G.addedge(ss, v+N1, 1, 0);
        }
        else if (rs[v] == 'R') {
            ++nT;
            G.addedge(v+N1, t, INF, 0);
            G.addedge(v+N1, tt, 1, 0);
        }
        else {
            G.addedge(s, v+N1, INF, 0);
            G.addedge(v+N1, t, INF, 0);
        }
    }
    G.addedge(s, tt, nS, 0);
    G.addedge(ss, t, nT, 0);
    for (int i = 0; i < M; ++i) {
        int x, y; cin >> x >> y; --x, --y;
        G.addedge(x, y+N1, 1, r, i);
        G.addedge(y+N1, x, 1, b, i);
    }
    G.addedge(t, s, INF, 0);

    auto res = MinCostFlow(G, ss, tt, nS + nT);
    cout << res << endl;
    if (res == -1) return 0;
    string ans(M, 'U');
    for (int v = 0; v < N1; ++v) {
        for (auto e : G[v]) {
            if (e.id == -1) continue;
            if (e.cap == 0 && e.icap == 1) ans[e.id] = 'R';
        }
    }
    for (int v = 0; v < N2; ++v) {
        for (auto e : G[v+N1]) {
            if (e.id == -1) continue;
            if (e.cap == 0 && e.icap == 1) ans[e.id] = 'B';
        }
    }
    cout << ans << endl;
}

Educational Codeforces 80 E. Messenger Simulator (R2100)

面白かった。
数列の区間に含まれる値の種類数を答えるクエリに素早く答える技術が必要になった。

問題へのリンク

問題概要

がこの順に並んでいる。ここから 回の操作を行う。

• 回目の走査は、 以上 以下の値 で表され
• 現在の順列のうち、値 を先頭にもってくる操作を行う

たとえば (3, 4, 2, 1) に対して、値 2 を指定すると (2, 3, 4, 1) になる。各 に対して、操作過程において が登場した index の最小値と最大値を求めよ。

制約

• 

考えたこと

まず最小値は簡単

• の中に があるなら、最小値は
• の中に がないなら、最小値は

の登場する最大値を考える。 が

○, ○, ..., ○, ○, ○, ..., ○, , ○, ○, ..., ○, , ○, ..., ○

と表されるときに、先頭を除くと

• 「( で挟まれた区間に登場する値の種類数) + 1」の最大値

が答えになることがわかる。先頭は例外で

• ( で挟まれた区間に登場する より大きい値の種類数) + 1

となる。ただこれは扱いづらいので、 の先頭に付け加えて

○, ○, ..., ○, ○, ○, ..., ○, , ○, ○, ..., ○, , ○, ..., ○

という風にする。こうしておくと、 で挟まれた区間に登場する値の種類数さえ答えればよくなる。それを行うための方法として、Mo や、BIT がある。それらについては以下の記事に。

drken1215.hatenablog.com

コード (1)： BIT

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template <class Abel> struct BIT {
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;                     // to be set
    
    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }
    
    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x) {
        sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1));
    }
    
    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    vector<int> a;
    for (int i = 0; i < N; ++i) a.push_back(N-i-1);
    for (int j = 0; j < M; ++j) {
        int b; cin >> b; --b;
        a.push_back(b);
    }
    
    BIT<int> bit(N+M+10);
    vector<int> prev(N, -1);
    vector<bool> exist(N, false);
    vector<int> res(N, 0);
    for (int i = 0; i < N+M; ++i) {
        if (prev[a[i]] != -1) {
            chmax(res[a[i]], bit.sum(prev[a[i]]+2, prev[a[i]]+3) + 1);
        }
        bit.add(prev[a[i]]+2, i+2, 1);
        if (i >= N) exist[a[i]] = true;
        prev[a[i]] = i;
    }
    for (int i = 0; i < N; ++i) {
        chmax(res[i], bit.sum(prev[i]+2, prev[i]+3) + 1);
    }
    for (int i = 0; i < N; ++i) {
        if (exist[i]) printf("%d ", 1);
        else printf("%d ", i+1);
        printf("%d\n", res[i]);
    }
}

コード (2)： Mo 法

想定解法ではなさそうだけど、本番は Mo でやった。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
 
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
 
template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template<class T, class V>
typename enable_if<is_class<T>::value == 0>::type fill(T &t, const V &v) {
    t = v;
}
template<class T, class V>
typename enable_if<is_class<T>::value != 0>::type fill(T &t, const V &v){
    for (auto &e : t) fill(e, v);
}
 
 
 
struct Mo {
    vector<int> left, right, index; // the interval's left, right, index
    vector<bool> v;
    int window;
    int nl, nr, ptr;
    
    Mo(int n) : window(max((int)sqrt(n), 1)), nl(0), nr(0), ptr(0), v(n, false) { }
    
    /* push */
    void push(int l, int r) { left.push_back(l), right.push_back(r); }
    
    /* sort intervals */
    void build() {
        index.resize(left.size());
        iota(begin(index), end(index), 0);
        sort(begin(index), end(index), [&](int a, int b) {
            if(left[a] / window != left[b] / window) return left[a] < left[b];
            return right[a] < right[b];
        });
    /*
        sort(begin(index), end(index), [&](int a, int b)
             {
                 if(left[a] / window != left[b] / window) return left[a] < left[b];
                 if(right[a] / window != right[b] / window) return bool((right[a] < right[b]) ^ (left[a] / window % 2));
                 return bool((index[a] < index[b]) ^ (right[a] / window % 2));
             });
    */
    }
    
    /* extend-shorten */
    void extend_shorten(int id) {
        v[id].flip();
        if (v[id]) insert(id);
        else erase(id);
    }
    
    /* next id of interval */
    int next() {
        if (ptr == index.size()) return -1;
        int id = index[ptr];
        while (nl > left[id]) extend_shorten(--nl);
        while (nr < right[id]) extend_shorten(nr++);
        while (nl < left[id]) extend_shorten(nl++);
        while (nr > right[id]) extend_shorten(--nr);
        return index[ptr++];
    }
    
    /* insert, erase (to be set appropriately) */
    void insert(int id);
    void erase(int id);
};
 
 
int N;
int A[1000001];
int cnt[1000001];
int num_kind = 0;
 
void Mo::insert(int id) {
    int val = A[id];
    if (cnt[val] == 0) ++num_kind;
    ++cnt[val];
}
 
void Mo::erase(int id) {
    int val = A[id];
    --cnt[val];
    if (cnt[val] == 0) --num_kind;
}
 
 
 
int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    
    int N, M;
    while (cin >> N >> M) {
        vector<int> a(M);
        for (int i = 0; i < M; ++i) scanf("%d", &a[i]), --a[i];
 
        vector<bool> exist(N, false);
        for (int i = 0; i < M; ++i) {
            exist[a[i]] = true;
        }
 
        vector<vector<int>> pls(N);
        for (int i = 0; i < N; ++i) pls[N-1-i].push_back(i), A[i] = N-1-i;
        for (int i = 0; i < M; ++i) pls[a[i]].push_back(i+N), A[i+N] = a[i];
 
        vector<int> left, right, ids;
        vector<int> res(N, 0);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < pls[i].size(); ++j) {
                left.push_back(pls[i][j] + 1);
                right.push_back(j+1 < pls[i].size() ? pls[i][j+1] : N+M);
                ids.push_back(i);
            }
        }
 
        //for (int i = 0; i < N+M; ++i) cout << A[i] << ","; cout << endl;
 
        Mo mo(N+M + 10);
        memset(cnt, 0, sizeof(cnt));
        num_kind = 0;
        int Q = left.size();
        for (int i = 0; i < Q; ++i) {
            mo.push(left[i], right[i]);
        }
        mo.build();
 
        for (int q = 0; q < Q; ++q) {
            auto moid = mo.next();
            auto kind = num_kind;
 
            //cout << moid << ": " << left[moid] << ", " << right[moid] << " (" << ids[moid] << "): " << kind << endl;
 
            int id = ids[moid];
            chmax(res[id], kind+1);
        }
 
        for (int i = 0; i < N; ++i) {
            if (exist[i]) printf("1 ");
            else printf("%d ", i+1);
            printf("%d\n", res[i]);
        }
    }
}