DISCO presents ディスカバリーチャンネル コードコンテスト2021 本戦 参加記

2021/03/28に行われたDISCO presents ディスカバリーチャンネル コードコンテスト2021 本戦に参加してきました。

今年はコロナウイルス感染拡大の影響で全然オンサイトがなく、なんと最後に参加したものは去年のDDCC2020本戦でした。

kotatsugame.hatenablog.com

なかなか面白いめぐり合わせですね。この状況下で開催を決断してくださった運営の方々、また感染症対策などに気を使いつつコンテストを進行してくださったスタッフの皆さん、ありがとうございました。

ちなみに、念の為予選の成績を書いておくと、30分ちょっとで全完でした。

朝

今年はコード部門がないので、本戦開始時刻も遅くなりました。具体的には、午前13時開始なので、朝にはいくらか余裕があります。昨年は始発の新幹線に乗りましたからね……。

とはいえ、今年は僕が富山県に帰省中なので、仙台駅から向かった昨年と比べて（駅までの移動も合わせ）移動時間は増えます。なかなかちょうどよい列車がなかったこともあって、今年は指定席特急券を買い、速い列車で行くことにしました。僕は22卒の対象に含まれるので、交通費も支給されます。というわけで、09:08富山駅発11:20東京駅着のかがやきに乗りました。

新幹線の中で本戦参加者のTwitterリストを作りました。

twitter.com

東京駅から品川駅を経由して大森海岸駅まで向かいます。うっかりグリーン車の車両に乗ってしまい、わざわざ普通車に通り抜けさせてもらいました。こういうのは問答無用でグリーン車乗車券を買わされるものだと思っていたので、人の温かみに触れた気がしました。

品川駅でJRと京急の乗り換えに失敗し、検索して出てきたものより1本遅れてしまいましたが、無事到着。駅の近くで食事をしようと考え、ふとTLで目にしたなか卯に行ってみると、4人くらいの競プロerが集まっていました。5人目は流石にマズいので、挨拶だけして食事は別の席でしました。

僕「これって勝手に帰っていいんですか」

kort0nさん「（券売機を指しつつ）お金払ったでしょ」

僕「……（納得して退店）」

ディスコ本社に向かうも、受付開始の12:30までは入れないようだったので、横のイトーヨーカドーに向かいます。その途中すれ違ったkyopro_friendsさんに声を掛けていただき、2人で少しだけうろつきましたが、特に何か見るわけでもなく、すぐディスコ本社前に向かいました。本社前には他にも所在なげに立ち尽くしている競プロerが複数人いて、そのうち自宅番兵さん等と挨拶しているうちに、受付開始時間になりました。

コンテスト前

検温・マスク交換・アルコール消毒して、名札を受け取り、コンテスト会場に向かいます。交通費領収書もこのとき渡すのですが、封筒に入れなければならないところを用意していなかったので、急遽クリアファイルをもらって名前を書くことになりました。少し時間を食って他の人を待たせてしまい申し訳ない……。

コンテスト会場に用意されていた席は、上下以外の4方がビニールに覆われていてびっくりしました。企業紹介映像を見る限り、このようなブースは普段の業務でも使用しているようで、なかなか大変そうだなあという気持ちになりました。

机に用意されていたTシャツを着ていると、インタビューを申し込まれたので、しばらく答えていました。

これまでのDDCCへの参加経験を聞かれ、昨年本戦に出たということ、また予選は詳しく覚えていないが、2016年から競プロを始めたので、それ以降のものには出ているんじゃないかと答えました。DDCCもちょうど2016年から始まったということで、これも面白いめぐり合わせです。後から確認したところ、2016年と2017年の予選には参加していたようです。

また、この記事の冒頭でも書きましたが、昨年のDDCCから丸1年オンサイトがなかったことにも触れ、開催していただけてありがたいということも言いました。

本戦にかける意気込みを聞かれて、「昨年は装置に自分のプログラムを実装することができなかったので、今年はそこまで進みたい」ということを答えたのですが、今年はシミュレーションで点数を取れば全員実装できるということを知ってちょっと拍子抜けしました。まあ30人しかいなければそんなものなんですかね。

その後説明・会社紹介があって、いよいよ問題公開・コーディングです。

シミュレータ問題

問題は、簡単にいえば次のようなものです。制約の細かい値（例えば穴の詳細等）は、忘れたものもあるので、気にしないでください。

長方形の平面がある。ある辺の中心にボール射出装置があり、平面上に10個の穴がある。

ボール射出装置の向きと平面の傾きをある程度操作できるので、ボールを射出して穴に入れ、後述するスコアを最大化する。

スコアは、穴に入ったボールの個数×ボールが1つ以上入った穴の個数で計算される。 ただし、1つの穴に10個ボールが入るとそれ以上その穴にボールを入れてもスコアには影響しなくなる。

ボール射出装置や平面の操作のパラメータ、射出するボールの個数、その後の次の動作までの待ち時間をセットで指定して、装置を動かすことを繰り返す。 ボール射出装置や平面の操作のために1.7secかかり、ボールを1つ発射するのに0.5secかかる。

まずは60分コーディングし、シミュレータ上でスコアを競います。シミュレータでは、制限時間は100secで、待ち時間が終了するとその時点で穴に入っていないボールは無視されます。

まず、ボール射出装置の角度だけで狙える穴だけ狙うことにします。待ち時間は、最も遠い穴まで転がることを考えても2.1secあれば十分で、このとき1.7+0.5×10+2.1=8.8[sec]となり、10個の穴をそれぞれ狙って10個ずつボールを打っても制限時間に間に合います。

テストケース5つは、予選と同様事前に公開されたものをコードに貼り付ける形です。実は1つだけ、ボール射出装置の角度だけでは狙えない位置にある穴が存在しましたが、それ以外は大丈夫なようです。コーディングして提出すると、3070点になりました。

これは予想していたよりかなり低いスコアです。適当に提出を繰り返して何故か調べてみたところ、どうやら奥の穴を狙って打ったのに手前の穴に吸い込まれてしまっていたようでした。当たり前すぎる……。これをなんとかするためには、平面を傾けて狙う必要がありそうです。

傾いた平面における、球の傾き方向への加速度の式は、問題ページに書いてありました。傾きを\thetaとして\frac 5 7g\sin\thetaらしいです。係数が何から出ているのかよくわかりませんが、これの物理学的導出に注意を払っている時間はなく、僕は久しぶりに扱う等加速度運動にドキドキしていました。

とりあえず平面をボール射出装置（の初期状態の方向）から見て左右に傾けるだけにすることにします。最初に打ち出す角度と到達させたい場所が分かれば、平面の傾きをarcsinで求められることがわかりました。平面の傾きは、支持する軸を上下させて操作するという制約上、それほど大きく傾けられるわけではありません。適当に三分探索などして、平面の傾きが打ち出す角度が制限内に収まるものを探しました。

これで、以前に射出した角度に近いものを使用しないようにしてコーディングしたところ、3260点が出ました。思ったより伸びませんでしたが、ここでシミュレータ問題の時間終了です。

実機への実装

シミュレータ問題の順位が発表されました。僕は2位だったようです。beetさんなどの話を聞く限り、その下はだいたい3060点で団子になっているような感じでした。少しでも改善できたことが良かったのでしょう。2位なので、実機実装は2番目に行えます。

まず30分のコーディング時間が与えられ、そこで最後に提出したコードが実機に実装されます。実機の穴の情報もシミュレータ問題と同様のフォーマットで与えられますが、制約に変更がありました。

待ち時間が終了しても穴に入っていないボールが消えたりしないこと、また台を手前に向けて傾けることが可能になったことは、シミュレータで再現が難しかった部分の制限撤廃でしょう。最も大きい変更は、制限時間が60secになったことです。これによって、ボールを全て打ち切ることが不可能になりました。

実機では、ボール射出装置から見てある穴の後ろに隠れてしまう穴が4つ程度存在するようでした。テストで動かしてみる機会は1度しかなく、10発ずつ打っていると時間がなくなってしまうため、とりあえずの軌道だけ確認しようと1発ずつ打つことにしました。これは結構特徴的だったようです。

それで動かしてみたところ、他の穴に隠れていない穴には順当に入りましたが、傾けて打ったボールは1つが狙い通りに入り、もう1つ穴に弾かれて別の穴に入っただけでした。どうやら遠くの穴を狙うとかなりブレてしまうようです。

これをメモして、他の人の動作をしばらく見ていましたが、装置の不具合などもあって順調に進まず、結構暇を持て余していました。この時間はコーディング不可なので、手で少し計算するくらいしかやることがなくて、あとはなろう小説を読んだりしていました。

本番前

また30分与えられてコーディングし、ここでの最終提出を再度動かして順位を決めます。

先程見たように、遠くの穴を狙うとブレている、もっと詳しく言えば曲がりすぎてしまうようだったので、そこを補正しました。これは「頭で考えた値を埋め込むことを禁止する」というルールに抵触しそうだなと思いましたが、それっぽいif文で押し切りました。

他にも、ボールを射出してからの待ち時間を0secにしてしまったが故に、まだ転がっているボールがあるのに平面を傾けてしまいあらぬところに転がっていった人がかなりいたので、その点も調整しました。具体的には、平面を操作せずに狙える穴だけまとめて待ち時間0secで狙い、そこからしばらく待って、転がりきってから平面を操作し始めるという感じにしました。

傾けずに狙える穴へは変わらず10発打ちますが、傾けて穴を狙うのは難しいので、10発ではなくそれぞれ3発だけにして、時間制限のクリアとともに全ての穴に入れることでのスコアアップを狙いました。

本番

人生終了

穴を狙うときの射出装置の傾き同士の差が、より大きくなるようにしたのですが、それで台を傾けたときの誤差が大きくなったのでしょうか、全然入りませんでした。補正する値を適当に決めたのも良くなかったのでしょう。見返してみると謎の軌道で狙っている穴もあって、よくわかりません。

スコアは420点で、最終的に22位だったようです。同点が3人いて、タイブレークにはシミュレータ問題の順位が使用されました。

コンテスト後

実はスケジュールが遅れた影響で予定していた新幹線に間に合わない可能性が出てきて、本番実装を一番最初に行ってもらった上、最後の10人くらい（と表彰式）を見ずに帰宅しました。

ディスコ本社の看板を撮影していると、玄関口まで送ってくださったスタッフさんが声を掛けてくださって、写真を撮ってもらいました。

夜はぽかーん懐古DPさんと食事する予定を立てていましたが、時間に余裕がなく失敗。一人で食べることになりました。前に碧黴さんと行った東京ラーメンストリートのつけ麺屋に入ろうとしましたが、微妙に並んでいたので、諦めて2軒隣の豚骨ラーメン屋に入りました。

夜は20:12東京駅発22:57富山駅着のはくたかに乗りました。東京・上野・大宮で結構人が乗ってきましたが、幸い2人がけの席を1人で使えるくらいだったので、安心してパソコンを出し、ARCに出場しました。別に隣に人がいたからと言ってARCに出ないわけはないのですが、まあ気を使わなくて済むのはよいことです。

ARCはEまで速解きして温まりました。

コード

コードを公開しておきます。

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int XYin[20]={0,450,85,575,340,700,170,700,0,700,-340,700,-280,825,255,950,0,950,-340,950};
pair<int,int>XY[10];
int elapsed;
double calc(int x,int y,double th)
{
    double t=y/(500*cos(th));
    double dx=x-tan(th)*y;
    dx/=t*t/2*5/7*9.8e3;
    return asin(dx);
}
vector<double>S;
void disp(double th,int id,int N,int Tm)
{
    int x=XY[id].first,y=XY[id].second;
    double ph=calc(x,y,th);
    int up=round(tan(ph)*400*1e3);
    int theta=round(th*180/M_PI*1e3);
    if(abs(up)>25000)
    {
        cerr<<"ERROR"<<endl;
    }
    cout<<0<<","<<up<<","<<-up<<","<<theta<<","<<N<<","<<Tm<<endl;
    elapsed+=N*500+Tm+1700;
    //cerr<<elapsed<<endl;
}
bool usd[10];
void disp(int id,int N)
{
    int x=XY[id].first,y=XY[id].second;
    double pre=-M_PI/4;
    const double EPS=1e-2;
    sort(S.begin(),S.end());
    double ansth,ansph;
    double absmn=0;
    for(double t:S)
    {
        double thl=pre+EPS;
        double thr=t-EPS;
        if(thl<thr)
        {
            for(int _=0;_<50;_++)
            {
                double th1=(thl*2+thr)/3,th2=(thl+thr*2)/3;
                double ph1=calc(x,y,th1);
                double ph2=calc(x,y,th2);
                if(abs(ph1)<abs(ph2))thr=th2;
                else thl=th1;
            }
            double th=(thl+thr)/2;
            double ph=calc(x,y,th);
            int up=round(tan(ph)*400*1e3);
            int theta=round(th*180/M_PI*1e3);
            if(abs(up)>25000)continue;
            double mn=9e9;
            for(int i=0;i<10;i++)if(usd[i])
            {
                int tx=XY[i].first,ty=XY[i].second;
                double phi=calc(tx,ty,th);
                mn=min(mn,abs(ph-phi));
            }
            if(absmn<mn)
            {
                absmn=mn;
                ansth=th;
                ansph=ph;
            }
        }
        pre=t;
    }
    if(absmn==9e9)cerr<<"ERROR"<<endl;
    double th=ansth;
    if(th!=0&&y>800)
    {
        if(th>0)th+=5e-3;
        else th-=5e-3;
    }
    double ph=calc(x,y,th);
    int up=round(tan(ph)*400*1e3);
    int theta=round(th*180/M_PI*1e3);
    int Tm=ceil(y*2/cos(th));
    cout<<0<<","<<up<<","<<-up<<","<<theta<<","<<N<<","<<Tm<<endl;
    elapsed+=N*500+Tm+1700;
    //cerr<<elapsed<<endl;
    usd[id]=true;
    S.push_back(th);
}
int main()
{
    for(int i=0;i<10;i++)
    {
        XY[i]=make_pair(XYin[i*2],XYin[i*2+1]);
    }
    vector<pair<double,int> >FST;
    for(int i=0;i<10;i++)
    {
        int x=XY[i].first,y=XY[i].second;
        double th=atan2(x,y);
        bool fn=false;
        for(double t:S)if(abs(t-th)<0.03)fn=true;
        if(fn)
        {
        }
        else
        {
            usd[i]=true;
            FST.push_back(make_pair(th,i));
            S.push_back(th);
        }
    }
    for(int i=0;i<FST.size();i++)
    {
        int Tm=0;
        if(i+1==FST.size())
        {
            double th=FST[i].first;
            Tm=ceil(XY[i].second*2/cos(th));
        }
        disp(FST[i].first,FST[i].second,10,Tm);
    }
    S.push_back(M_PI/4);
    for(int i=0;i<10;i++)if(!usd[i])
    {
        disp(i,3);
    }
}