ACCE55_DE21ED

競プロとCTF

APIO 2020 参加記 【コンテスト実況】

競プロ 参加記

1. 雑

8/16 10:00 ~ 15:00 (JST) ，APIO 2020に参加しました．今年は残念ながらオンライン開催でしたが，長時間コンテストならではの楽しみを味わうことができました！

普通に5時間参加して疲れたんですが，春合宿の時はこれを4日連続でやってたのか... まぁ，実際 5 時間やってみると思った以上にあっという間に終わっちゃうものですよね．

時間配分に完全に失敗した感じがあるんですが，まぁそれでも 1 完できて良かった（？） でもAPIOの方が春合宿よりだいぶ簡単目ではあると思います．

APIO 2017 Virtual の時に，VSCodeで複数ファイルデバッグのやり方を確認しておいたのはかなり役立ちました．JOIの時使えるのかなぁ？

2. 全体

（提出履歴）

f:id:defineprogram:20200819200201p:plain

f:id:defineprogram:20200819200231p:plain

（得点）

  • [A] Painting Walls 100点 (小課題 1 ~ 5)
  • [B] Swapping Cities 50点 (小課題 1 ~ 4)
  • [C] Fun Tour †0点†

計 150 点でした．ちーん

f:id:defineprogram:20200818221559p:plain

まだ日本順位出てないので分かりませんが，9位〜11位くらいじゃないかと思います．春合宿よりは全然マシ．

3. コンテスト実況（唐突）

それでは，define 選手のコンテスト中のムーブを実況しようと思います． 実況は私 define が，解説はこちらの define が担当します．よろしくお願いしま〜す（茶番開始）

主観と客観が入り混じって変になってる所あるけど許して下さい

※所々真面目な話をしていますが，ほぼ茶番ですのでご注意下さい

3.0 開始前

まずはラムネをティッシュの上におき，机の上に置きました．競技時間中にサッと食べるためでしょうか． あれ，これは春合宿用に買ったやつでは？そうです，春合宿中は競技会場内に持ち込めなかったので 2 袋買ったのに結局食べなかったのでしたね．糖分大事．

そうこうしている内に残り1分です．本選，春合宿の開始直前と同じ緊張に襲われています．

刻一刻と迫る時間の前に，人間は何と無力な事でしょう！まるで課題の締切

3.1 開始直後 〜 1時間

3.1.1 誤った計算量見積もり

まずはいつも通り A 問題からです． A 問題は簡単枠の可能性が割とあるため，慎重に見極めないと満点を逃すなんて事も起きかねません． ちょっと実験をしながら，10 分ちょっとで問題の意図を理解しました．

「なるほど，各色を好む作業員は最大でも \(650\) 人程度だから，各領域を好む作業員の合計は高々 \(650 \times 10^{5} \) 程度って事か〜．1.5 秒だし log はつけられなさそう...」

それにしても，問題文作成者は，なぜ \(f(k)^{2} \leq 4 \times 10^{5}\) などという表記をしたのでしょうか？かなり不自然に思えます．

「各領域で \(1,2,3,0,1, \cdots \) みたいになっていればそこを \(M\) ずつ指示を出していけるのか． それぞれの作業員は連続する区間で高々 1 回しか使われないから，自分の含まれる区間の右端の最大値を持っておけば貪欲に決められそう！」

「log 付けられないけど，unordered_set使えば間に合うやろ！笑」

簡単枠であると確信し，取り敢えず解法を実装します．

コード 

#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

unordered_set<int>st[100005];
int mx[100005];
int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) {
    rep(i,N){
        mx[i]=i;
        rep(j,M){
            for(int k:B[j])if(C[i]==k)st[i].insert(j);
        }
    }
    rep(i,N){
        for(int j:st[i]){
            int worker=j,cur=i+1;
            while(cur<N&&st[cur].find((worker+1)%M)!=st[cur].end()){
                (worker+=1)%=M;
                st[cur].erase(st[cur].find(worker));
                cur++;
            }
            if(cur<i+M)continue;
            for(int k=cur-1;k>=i;k--)mx[k]=max(mx[k],cur);
        }
    }
    int now=0,ans=0;
    while(now<N){
        if(now+M<=mx[now]){
            ans++;now+=M;
        }else if(mx[now]==now)return -1;
        else {
            ans++;now=mx[now];
        }
    }
    return ans;
}

【結果】

TLE (28pts)

普通に考えて，そもそも

rep(i,N){
    mx[i]=i;
    rep(j,M){
        for(int k:B[j])if(C[i]==k)st[i].insert(j);
    }
}

の時点で相当ヤバイと思うんですが何故気づかないのでしょうか？

f:id:defineprogram:20200818220921p:plain

いい加減気づいてくれ...

3.1.2 重大なバグ

define 選手，ようやく気が付きました．しかし，今度は不幸にも別のバグを埋めてしまいます．

mx[i]=i;

の部分を忘れていたのです．そのため，以下のコードで -1 を返す事なく 0 に戻ってしまい無限ループが引き起こされて小さいケースでもTLE，見事0点．

int now=0,ans=0;
while(now<N){
    if(now+M<=mx[now]){
        ans++;now+=M;
    }else if(mx[now]==now)return -1;
    else {
        ans++;now=mx[now];
    }
}

このバグは暫く気づく事ができず，コンテスト最大の敗因と言っても過言ではないのではないでしょうか．

3.2 開始 1 時間 〜 2 時間

3.2.1 試行錯誤

define 選手，前述のバグによって試行錯誤を繰り返しています．ジャッジがおかしいのでは？と思いもう一度提出しても結果は変わらず． まごまごしている内に，時間配分の目安である 1時間半を超えてしまいます．明らかに簡単枠にも関わらず，未だ 28 点しか取れていません．

とそこで，血迷った define 選手，間違えてラムネを置いたティッシュを引き抜いた〜！！ラムネ，机の上に産卵！頭大丈夫か？？

しかしそんな事で時間を取る訳には行きません．取り敢えずラムネをまとめてから，頭のリフレッシュも兼ねて他の問題を見ます． まずは B 問題．余程パニックなのでしょうか，小課題 1 を見て次数 2 以下は全てパスグラフだと錯覚し全て -1 を返すようにするも，当然 WA ！

f:id:defineprogram:20200818221307p:plain

C 問題を見ても何も分からず，やはり A 問題への未練から集中できていない模様．

A 問題にまた戻るも，未だに前述のバグに気づいていません．

3.3 開始 2 時間 〜 3時間

3.3.1 バグへの気づき

ついにバグに気が付きました！この 1 時間は何だったのか，しかし今となっては時間を巻き戻す事はできません． せめて満点を取らないと挽回は厳しいでしょう．

取り敢えずbool 型で管理するやつを実装し，小課題 2 〜 4 の51点を獲得です．

コード

#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

bool ok[20005][2005];
int mx[100005];
vector<int>oklist[100005];
int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) {
    rep(i,M){
        for(int j:B[i])oklist[j].push_back(i);
    }
    rep(i,N){
        mx[i]=i;
        for(int j:oklist[C[i]])ok[i][j]=true;
    }
    rep(i,N){
        rep(j,M){
            if(!ok[i][j])continue;
            int worker=j,cur=i+1;
            while(cur<N&&ok[cur][((worker+1)%M)]){
                (worker+=1)%=M;
                ok[cur][worker]=false;
                cur++;
            }
            if(cur<i+M)continue;
            for(int k=cur-1;k>=i;k--)mx[k]=max(mx[k],cur);
        }
    }
    int now=0,ans=0;
    while(now<N){
        if(now+M<=mx[now]){
            ans++;now+=M;
        }else if(mx[now]==now)return -1;
        else {
            ans++;now=mx[now];
        }
    }
    return ans;
}

3.3.2 そして満点解法へ

さて，後は区間の管理を高速化するのみです．

ここで，\(0,1,2,0 \dots \) を index の分だけ差し引けば同じ数になって管理しやすくなる事に気が付きました． 気づくのが遅すぎる，もはや致命的ですがこのチャンスを逃すわけには行きません．

早速実装するも，WA．重大なバグを埋め込んでいるにも関わらず，なぜか小課題 1 が取れました．

コード

#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

vector<int>st[100005];
int mx[100005];
vector<int>oklist[100005];
int start[100005],en[100005];
int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) {
    rep(i,M){
        for(int j:B[i])oklist[j].push_back(i);
    }
    int ad=(100000+M-1)/M*M;
    rep(i,N){
        mx[i]=i;
        for(int j:oklist[C[i]]){
            st[i].emplace_back((j-i+ad)%M);
        }
    }
    rep(i,M){
        start[i]=-2;en[i]=-2;
    }
    rep(i,N){
        for(int j:st[i]){
            if(en[j]==i-1)en[j]++;
            else {
                for(int k=max(0,start[j]);k<=en[j];k++)mx[k]=max(mx[k],en[j]+1);
                start[j]=i;en[j]=i;
            }
        }
    }
    rep(i,M){
        if(en[i]==N-1){
            for(int j=start[i];j<N;j++)mx[j]=N;
        }
    }
    int now=0,ans=0;
    while(now<N){
        if(now+M<=mx[now]){
            ans++;now+=M;
        }else if(mx[now]==now)return -1;
        else {
            ans++;now=mx[now];
        }
    }
    return ans;
}

適当に以下のように場合分けをしましたが，これは実は意味がありません．途中で終わっている場合を無視しているからです．

rep(i,M){
    if(en[i]==N-1){
        for(int j=start[i];j<N;j++)mx[j]=N;
    }
}

そこでそれを直すも，WA(0pts)． サンプル 2 が間違っている事に気が付きデバッグをすると，連続する区間が \(M\) 未満の場合も処理を行っているのが原因でした．

それを直し，提出．13:00:38 の提出で，見事ACを獲得！

ACコード

#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

vector<int>st[100005];
int mx[100005];
vector<int>oklist[100005];
int start[100005],en[100005];
int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) {
    rep(i,M){
        for(int j:B[i])oklist[j].push_back(i);
    }
    int ad=(100000+M-1)/M*M;
    rep(i,N){
        mx[i]=i;
        for(int j:oklist[C[i]]){
            st[i].emplace_back((j-i+ad)%M);
        }
    }
    rep(i,M){
        start[i]=-2;en[i]=-2;
    }
    rep(i,N){
        for(int j:st[i]){
            if(en[j]==i-1)en[j]++;
            else {
                if(en[j]-start[j]+1>=M){
                    for(int k=max(0,start[j]);k<=en[j];k++)mx[k]=max(mx[k],en[j]+1);
                }
                start[j]=i;en[j]=i;
            }
        }
    }
    rep(i,M){
        if(en[i]-start[i]+1>=M){
            for(int j=max(0,start[i]);j<=en[i];j++)mx[j]=max(mx[j],en[i]+1);
        }
    }
    int now=0,ans=0;
    while(now<N){
        if(now+M<=mx[now]){
            ans++;now+=M;
        }else if(mx[now]==now)return -1;
        else {
            ans++;now=mx[now];
        }
    }
    return ans;
}

3.4 開始 3 時間 〜 4 時間

3.4.1 小課題 1

ACして喜ぶのも束の間，時間配分を盛大に失敗している事に気づき絶望．残り時間は僅か 2 時間です． さぁ define 選手，未だに A 問題しか正の得点を得ていない，流石に 1 完 のみじゃ代表は厳しいぞ！

先程「次数 2 以下はパスグラフ」という盛大な嘘解法を実装した define 選手，図を書いたらサイクルグラフの場合も 次数が 2 以下を満たす事に気が付きました．1 完して頭に余裕が出来たのでしょうか，しかし余裕ぶっこいてる場合ではありません． 取り敢えず 6 点を獲得．

コード

#include<bits/stdc++.h>
using namespace std;
#include "swap.h"
#define rep(i,n) for(int i=0;i<n;i++)

int ans;
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
    rep(i,M){
        ans=max(ans,W[i]);
    }
    if(M==N-1)ans=-1;
}

int getMinimumFuelCapacity(int X, int Y) {
    return ans;
}

3.4.2 小課題 2

「\(N \leq 3\) の場合は明らかにアウトで，\(X = 0\) の場合は \(Y\) とのやつ以外に余分な辺を 2 本， それ以外の場合は余分な辺を 1 本取れば大丈夫そう〜」

さて，現在 13 点です．

コード

#include<bits/stdc++.h>
using namespace std;
#include "swap.h"
#define rep(i,n) for(int i=0;i<n;i++)

int ans;
vector<int>memo;
vector<int>idx;
int nn;
multiset<int>st;
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
    idx.resize(N);
    nn=N;
    memo=W;
    rep(i,M){
        idx[V[i]]=i;
        st.insert(W[i]);
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    if(nn<4)return -1;
    if(X==0){
        st.erase(st.find(memo[idx[Y]]));
        auto it=st.begin();it++;
        int ans=max(*it,memo[idx[Y]]);
        st.insert(memo[idx[Y]]);
        return ans;
    }else {
        st.erase(st.find(memo[idx[X]]));
        st.erase(st.find(memo[idx[Y]]));
        int ans=max({*st.begin(),memo[idx[X]],memo[idx[Y]]});
        st.insert(memo[idx[X]]);
        st.insert(memo[idx[Y]]);
        return ans;
    }
}

3.4.3 小課題 3 , 4

「小課題 3 はサイズが小さいので辺を小さい順に追加して行く事が可能だなぁ．閉路がある（辺の本数が頂点数以上）か，パスグラフではなくなった(次数の最大値が3以上）時点でOKだよね．これUnionFindでできるじゃん！」

UnionFindをちょっと改造して提出したら予想以上に点数が高い！これは...？

なんと，小課題 4 も取れています！（ﾄﾞﾝﾄﾞｺﾄﾞﾝﾄﾞｺ)

コード

#include<bits/stdc++.h>
using namespace std;
#include "swap.h"
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()

struct UnionFind{
    vector<int>par,size,edges,mx;
    int find(int x){
        return (par[x]==x?x:par[x]=find(par[x]));
    }
    void merge(int x,int y){
        x=find(x);y=find(y);
        if(x==y){
            edges[x]++;
            return;
        }
        if(size[x]<size[y]){
            par[x]=y;
            size[y]+=size[x];
            edges[y]+=edges[x]+1;
            mx[y]=max(mx[x],mx[y]);
        }else {
            par[y]=x;
            size[x]+=size[y];
            edges[x]+=edges[y]+1;
            mx[x]=max(mx[x],mx[y]);
        }
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
    UnionFind(int x){
        rep(i,x){
            par.push_back(i);size.push_back(1);
            edges.push_back(0);mx.push_back(0);
        }
    }
};

int n,m;
struct S{
    int from,to,weight;
    bool operator<(S e){
        return weight<e.weight;
    }
};
vector<S>edge;
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
    n=N;m=M;
    rep(i,M)edge.push_back({U[i],V[i],W[i]});
    sort(all(edge));
}

vector<int>num;
int getMinimumFuelCapacity(int X, int Y) {
    num.assign(n,0);
    UnionFind uf(n);
    for(S e:edge){
        num[e.from]++;
        num[e.to]++;
        uf.mx[uf.find(e.from)]=max(uf.mx[uf.find(e.from)],num[e.from]);
        uf.mx[uf.find(e.to)]=max(uf.mx[uf.find(e.to)],num[e.to]);
        uf.merge(e.from,e.to);
        if(uf.same(X,Y)){
            int siz=uf.size[uf.find(X)];
            int ed=uf.edges[uf.find(X)];
            int mx=uf.mx[uf.find(X)];
            if(siz-1!=ed||mx>2)return e.weight;
        }
    }
    return -1;
}

これで小課題 1 〜 4 を獲得し，B 問題で 50 点を得ました．

実は小課題 5 の解法も分かってはいたものの，残り 1 時間しかなかった上に実装が重そうだったのでパス．

3.5 開始 4 時間 〜 5 時間

3.5.1 嘘解法，再び そして競技終了

残り僅か 1 時間，何としてでも C 問題で 正の点数を取りたい所です．

「えー，グラフが与えられても順列の構築って難しくない？？？」

取り敢えずクエリを飛ばす必要のない小課題 3 に目を向け，適当な嘘解法を実装するも，当然 WA． 色々直す内に，無理そうな気がするもののやはりこの 21 点は取っておきたい所です．

まごまごしている内に残り 10 分を切りました．未だ 1 点も得ず．C 問題やらずに B の小課題 5 を実装すれば良かった... と思っても，今更そんな事はできません．さぁ，残り 5 分 になっても未だ進展はありません．

残り1分，30秒，15,14, ... そして C で 1 点も取れないまま競技は終了です．

4. 反省点・ポエム他

時間配分をミスっていた事，小さなバグに長い時間気が付かなかった事など非常に反省の余地があります． C 問題で小課題 1,2 から取っておけば良かったな... e.t.c. ただ，コンテストが終わった後に「〜だったら〜だったのに」みたいな事を言うのは大嫌いなので そういう事はしません．

良かった点としては，割と正しい難易度判定ができた事が挙げられると思います． 個人的に，9-10-? だと感じました．

全体の結果としては，Kodaman や blackyuki といった同級生が B で満点を取って代表となり，メダルを獲得した一方， 私は精進不足で部分永続 Union Find を知らず代表落ち，破滅となってしまいました．

非常に悔しいですが，これが実力です．APIOどころでなく破滅した春合宿直後は 「APIOに向けて極度精進するぞ！」と心に誓っていたのに，この4ヶ月の間に いつの間にかCTF をやっていたり（悪い事ではないけど） ，Youtubeに走ってしまったり（最悪）していた自分の信念の弱さが憎いです．

実際CTF は楽しいし役にも立ちますが，現実逃避の1つになっていたと考えられない事もないだろうと思います． CTF は別に大学生になってからでも全然できますが，情報オリンピックに参加できるのは残り僅か 3 年もありませんし， 同期がめちゃくちゃ強いので，今逃げてしまったら絶対にIOI代表にはなれないでしょう． 実際，今回私はAPIOで代表になり損ねました．

そういえば，小学生の時にやっていた暗算/珠算の時も同様でした． 今と同様（？）に全国レベルの実力はありましたが，上には上がいるという感じで どうしても勝てない同期がいたのです（名前は伏せますが，Googleで検索してみたらかなり有名になっていました）． 結局中学受験を理由に，暗算も九段のまま中途半端に終わる結果となってしまいました．

今の自分のままだと，暗算の時のように競プロも中途半端で終わってしまうんじゃないかと危惧しています． まぁ，こういうのも明日になったら忘れてたりするんですけどね...

これ以上重い感じ出すと界隈に悪影響与えそうなのでこれくらいで． ま，あんまり重い気持ちで競プロをやっても折角の楽しみが失われてしまうと思うので，これからも楽しんでやろうと思います！

5. い か が で し た か ？

実況で謎テンションをした挙げ句，ポエムで激重テンションをする謎ムーブ... 最後まで謎テンションに付き合って下さった皆様，ありがとうございました．

（宣伝）

（余談）

APIO のスタートボタンの下に書かれていた英文が，英語の例文チックで面白いなーと思いました（どうでも良い）

Welcome, APIO 2020 Contestants. APIO 2020 is a 5-hour virtual contest. To start your participation, click the "Click here to start your participation" button to start reading the problems and start your personal 5 hour timer.
Note that once your timer has started, there is no way to pause the timer. Do not press the button unless you are ready to start the contest.