APIO2022に参加しました！！

　幸いにも今年は募集枠が多かったため、今年のAPIO(Asia Pacific Informatics Olympiad)2022Egyptに出場することができました。競技の感想について残します。コードにおけるマクロに関しては

k1suxu.hatenablog.com

の「テンプレートの作製」の欄をご参照ください。
書くだけ書いて投稿してなかったことに気付いたので2年越しに公開しました。

当日の流れ

競技前

　当日はゆっくり9時ごろに起きて競技開始時間の13:00に向けてご飯を食べたりしました。

競技開始

　APIOでは、問題、サンプル、各種コードなどがzipファイルなどにまとまった状態で掲示されるので、とりあえずそれらをダウンロードしてフォルダに入れました。
　とりあえず問題を一通り読みます。marsの問題文の意味が分からなくて焦りながら、とりあえずgame, permの読解に移ります。とりあえず問題設定は把握したのですぐに考察に移りました。以下は自分が解いた問題の順番とその解法です。

perm 91.36点

　これは部分列のうち単調増加であるような数が $K$ 個となるような順列 $A$ を構成してほしいということです。こういった構築系は二進数にするのがいいという典型があるのでとりあえず二進数で考えてみると、ある時点でどの要素よりも大きいような要素を右に入れると条件を満たすような部分列の個数は2倍になって(手順1)(1bit右にずらす)、右に入れてから左に入れると元の通り数を $X$ とすると、 $2X+1$ となる(手順2)(1bitずらしてから+1)ことがわかりました。ということでビットが立っている位置を見つけたら手順2を、そうでなければ手順1を行うようにするとうまく構成できます。実際には再帰的に求めることで構成しました。
提出コードは以下です。

vector<int> construct_permutation(ll k) {
    k--;

    if(k == 0) return {};
    
    if(k == 1) return {0};

    vector<int> ret;

    if(k%2 == 1) {
        vector<int> ret = construct_permutation(k/2+1);
        ret.push_back(ret.size());
        return ret;
    }else {
        vector<int> ret = construct_permutation(k);
        ret.insert(ret.begin(), ret.size());
        return ret;
    }

    assert(false);
    return {};
}

game 30点

　部分点の1~3については毎回DFSをすればいいことはすぐにわかったので実装しました。まず、initが呼び出されるタイミングで、初期状態のテレポーターを示す辺を張り、add_teleporterが呼ばれるたびに辺を追加しDFSによって判定しました。判定においては、 $0\leqq{i}\leqq{j}\lt k$ なる頂点組 $(i, j)$ であって、 $j$ から一つ以上の辺を通って $i$ に行けるようなものが存在するかどうかを判定できればいいです。より具体的には頂点0からDFSをし、現在の経路内にある頂点をsetで管理し、頂点番号が $k$ よりも小さいような頂点に来たらset.findで既出判定を行うことで判定できます。
提出コードは以下です。

vvi g;
vector<bool> can;
int nn, kk;

void init(int n, int k) {
    g.resize(n);
    nn = n;
    kk = k;
    FOR(k-1) g[i].push_back(i+1);
    can.resize(n, false);
}

vector<bool> done;
set<int> st;

int dfs(int v) {
    if(can[v]) return true;

    done[v] = true;
    st.insert(v);
    for(auto e : g[v]) {
        if(e < kk && st.find(e) != st.end()) return can[v] = true;
        else if(!done[e]) {
            if(dfs(e) == 1) return can[v] = true;
        }
    }

    st.erase(v);
    return can[v];
}

int add_teleporter(int u, int v) {
    done.assign(nn, false);
    st.clear();
    g[u].push_back(v);
    return dfs(0);
}

mars 14点

　ここにきて問題文の意味が理解できなかったmarsの読解に入ります。簡潔に言えば、「連結成分の個数を数えたいけどメモリの制限が厳しいからデータをうまく圧縮してね」という問題です。普段こういった形の問題を解く機会はなかったので、読解に苦戦してしまいましたが、非常に勉強になりました。
　簡単にわかることとして、盤面の情報をbitで表したものを左上に左上に渡していけばいいのでその方針で実装すると14点が取れました。連結成分の個数は簡潔にBFSで数え上げました。
提出コードは以下です。

ll cal(string s, int n) {
    vector<vector<bool>> grid(n, vector<bool>(n, false));
    rep(i, n) {
        rep(j, n) {
            if(s[i*n+j] == '1') grid[i][j] = true;
        }
    }

    vector<vector<int>> dist(n, vector<int>(n, -1));

    auto bfs = [&](int X, int Y) -> void {
        dist[X][Y] = 0;
        queue<pii> que;
        que.emplace(X, Y);
        while(que.size()) {
            int x, y;
            tie(x, y) = que.front();
            que.pop();

            rep(d, 4) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if(dist[nx][ny] < 0 && grid[nx][ny]) {
                    dist[nx][ny] = dist[nx][ny] + 1;
                    que.emplace(nx, ny);
                }
            }
        }
    };

    ll ans = 0;

    rep(i, n) {
        rep(j, n) {
            if(grid[i][j] && dist[i][j] < 0) {
                bfs(i, j);
                ans++;
            }
        }
    }

    return ans;
}

string to_bit(ll n) {
    string ret(100, '0');
    rep(i, 60) {
        if(n >> i & 1) ret[i] = '1';
    }
    return ret;
}

string process(vector<vector<string>> a, int i, int j, int k, int n) {
    int dim = 2*k+1;
    string ret(100, '0');
    rep(id, dim) {
        rep(jd, dim) {
            rep(ii, 3) {
                rep(jj, 3) {
                    ret[(id + ii) * (dim + 2) + (jd + jj)] = a[ii][jj][id * dim + jd];
                }
            }
        }
    }

    // cout << ret << endl;

    if(k == n - 1) {
        return to_bit(cal(ret, dim+2));
    }else {
        return ret;
    }

    assert(false);
    return "";
}

　marsに関してはこれ以上の部分点を取ることはできませんでした。

game 60点

　30点を取ったときの考察にある「 $i\leqq{j}\lt k$ なる頂点組 $(i, j)$ であって、 $j$ から一つ以上の辺を通って $i$ に行けるようなもの」という部分を高速化したいなと思いました。ここで、説明の都合上、順辺を張ったグラフを $G$ , 逆辺を張ったグラフを $G'$ とします。ある頂点 $v$ について $G$ 上で到達可能な頂点のうち、 ${0\leqq{i}} \lt k$ を満たすものの最小値を $min_v$ とし、 $G'$ 上で到達可能な頂点のうち、 ${0\leqq{i}} \lt k$ を満たすものの最大値を $max_v$ とします。
するとこの問題は、 $min_v\leqq{max_v}$ を満たすような頂点 $v$ が存在するかというものに帰着します。
　あとはうまいこと必要部分のみを更新するように実装するだけです、少し複雑ですが以下の実装を参考にしてください。
　正直この提出で60点をとれるとは思っていなかったのですが、 $k\leqq{1000}$ がうまく効いてくれたおかげで得点を伸ばすことができました。

vvi g, rg;
vector<int> from, to;
int nn, kk;

void init(int n, int k) {
    g.resize(n);
    rg.resize(n);
    nn = n;
    kk = k;
    FOR(k-1) g[i].push_back(i+1);
    FOR(k-1) rg[i+1].push_back(i);
    
    to.assign(n, INF);
    from.assign(n, -1);
    FOR(k) from[i] = i;
    FOR(k-1) to[i] = i+1;
}


void dfs1(int v, int now, int& mnto) {
    from[v] = now;
    chmin(mnto, to[v]);

    for(auto e : g[v]) {
        if(from[e] < now) {
            dfs1(e, now, mnto);
        }
    }
}

void dfs2(int v, int now, int& mxfrom) {
    to[v] = now;
    chmax(mxfrom, from[v]);

    for(auto e : rg[v]) {
        if(to[e] > now) {
            dfs2(e, now, mxfrom);
        }
    }
}

int add_teleporter(int u, int v) {
    if(u < v && v < kk) return 0;

    if(u == v) {
        if(u < kk) {
            return 1;
        }else {
            return 0;
        }
    }

    g[u].push_back(v);
    rg[v].push_back(u);

    int mxfrom = -1, mnto = INF;

    if(v < kk) {
        if(to[u] > min(to[v], v)) {
            dfs2(u, min(to[v], v), mxfrom);
        }
    }else {
        if(to[u] > to[v]) {
            dfs2(u, to[v], mxfrom);
        }
    }
    if(u < kk) {
        if(from[v] < max(from[u], u)) {
            dfs1(v, max(u, from[u]), mnto);
        }
    }else {
        if(from[v] < from[u]) {
            dfs1(v, from[u], mnto);
        }
    }

    if(to[u] <= mxfrom || mnto <= from[u] || to[v] <= mxfrom || mnto <= from[v]) {
        return 1;
    }

    return 0;
}

競技終了

　ここまで合計得点 $14+60+91.36=165.36$ で競技が終了しました。最終順位は国内16位(同順位5人)銅メダル相当という結果になりました。
ちなみに、permは既出だったらしいです(悔しい) atcoder.jp
　私にとってはこれが最後の情報オリンピック関連大会だったので、いい結果が残せてよかったです。大学ではICPCにも出たいですね。