JOI難しい

二問しかといてないけどそれはあり本で勉強してたからです（言い訳）

AOJ 0534

Run-Length圧縮したらはやくなるかなとかやってたらしいけど、それだと例外できまくってだめだった。
実際はただの探索。
nが小さいからO(n^2)で普通にできる。

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
int n, col[10000];
int calc(int x, int c) {
    if (col[x]==c) return n;
    int p=x-1, q=x+1;
    int cnt=1;
    for (;p>=0;p--) {
        if (col[p]==c) cnt++;
        else break;
    }
    for (;q<n; q++) {
        if (col[q]==c) cnt++;
        else break;
    }
    if (cnt<4) return n;
    else if (p<0||q>=n) return n-cnt;
    else if (col[p]!=col[q]) return n-cnt;

    int res=n-cnt;
    while (true) {
        cnt=0;
        c=col[p];
        for (;p>=0;p--) {
            if (col[p]==c) cnt++;
            else break;
        }
        for (;q<n; q++) {
            if (col[q]==c) cnt++;
            else break;
        }
        if (cnt<4) return res;
        else if (p<0||q>=n) return res-cnt;
        else if (col[p]!=col[q]) return res-cnt;
        res-=cnt;
    }
    return res;
}
int main() {
    while (scanf("%d",&n)) {
        if (!n) break;
        for (int i=0; i<n; i++) {
            scanf("%d",&col[i]);
        }
        int res=INT_MAX/2;
        for (int i=0; i<n; i++) {
            for (int j=1; j<=3; j++) {
                res=min(res,calc(i,j));
            }
        }
        printf("%d\n",res);
    }
}

PKU 3660

グラフに落とし込めるのがわかるようになったのは嬉しい。ちょっとした成長
勝ちチームから負けチームへ有向の辺をはっていって有向グラフにしたとき、それはDAGなので各頂点についてその頂点にたどりつける頂点の数と、その頂点からたどりつける頂点の数の合計がn-1になるとき（上下のチームが確定するので）その頂点のチームの順位が確定する。
よってこれを単純に探索すればよい。単純に幅優先n回やったけど自明な枝刈りをしてAC

#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
using namespace std;
int n, m;
vector<int> G[100];
set<int> in[100], out[100];
bool used[100];
void calc(int x) {
    memset(used, 0, sizeof(used));
    queue<int> que;
    que.push(x);
    while (!que.empty()) {
        int nx=que.front(); que.pop();
        if (used[nx]) continue;
        used[nx]=true;
        for (int i=0; i<G[nx].size(); i++) {
            int y=G[nx][i];
            in[y].insert(x);
            out[x].insert(y);
            que.push(y);
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i=0; i<m; i++) {
        int a, b; scanf("%d%d",&a,&b); a--; b--;
        G[a].push_back(b);
    }
    int res=0;
    for (int i=0; i<n; i++) {
        calc(i);
    }
    for (int i=0; i<n; i++) {
        if (in[i].size()+out[i].size()+1==n) res++;
    }
    printf("%d\n",res);
}