Codingame fall challenge 2020

こどげの秋チャレンジ2020をやりました。秋なので。
Goldまで行きました。

順位はこんな感じでした。

再提出後なのでちょっと順位が変わってるけど、画像でも乗せたかったので。

f:id:totori_nyaa:20201124005550p:plain

最初の方あまり覚えていないけど、思い出せる限り順を追って感想とかやったことについて書いていこうと思います。

ゲームのルールについては、説明するのが面倒なので知らないならツカモさんの日本語訳記事(あとでリンクを貼る)を読んでください。

追記

ツカモさんの記事を貼るのを忘れていたので、貼っておきます。

tsukammo.hatenablog.com

11/13~

こどげ開始

2時間後くらいにBronze昇格

流石に初日はルール通りにバグらない実装をできていれば上位に入れる。

最初の方は探索をせずに、そのターンで作れるポーションがあるなら作る、ないならいい感じのlearnができるか、できないなら何かテキトーにcastを唱える、くらいの動きをしていた。

何も考えずにひたすら実装をしていたら手首を痛めた。

コンテスト開始 11/15~

ポーション用のstructとcastとtome用のstructとinput用の関数を用意して、それ以外はすべてmainの中に書いていると、次第に無限場合分けからのほとんど同じコードのコピペが増えてきて可読性が無になりはじめたので、mainの外に関数を作成し始める。
この時点でlearn系が5種類、cast系が2種類あって、learn周りが地獄。
この辺りからDFSを使って5ターン以内に作れるポーションの探索を開始。めちゃくちゃバグらせた記憶がある。
invalidな動きをする系のバグから、invalidではないけど思った通りに動かない系のバグまで様々で、困っていた。HELP!

Silver解禁

解禁と同時にSilverに昇格。
その後熱烈研究によりしばらく触らなかったのでSilver下位をさまよう。

Gold解禁

Gold解禁と同時に昇格を目指してコーディングしていたが、間に合わず。
なんなら、この時点で方針を大きく変えるためにほとんど消していたので、inputくらいしかできない状態だった。

legend解禁

この辺りからやっと本格的に？手を付け始める。多分。何日か覚えてないけど多分この辺。
方針として、Silver昇格時の5ターンDFSを変更してBFSにする。
copyなどで定数倍が遅かったので、なるべく必要な情報のみ持たせたり、QCFium法や意味があるか分からないけどググったら出てくる様々な高速化を行った。
なんだかんだあって1日費やして満足のいくコードを書いて投げると、寝ている間にGoldに昇格。

初こどげで、長時間マラソンも本格的に参加したのがこの前のHTTF予選が初めてだったので割とこの辺りで満足していた。

その後、よく見ると大量のバグを埋め込んでいたりいなかったりなのを改善していた。

最終日

突然今までのBFSではなくビームサーチを実装し始める。
大量のバグが発生して困り、今までで一番順位の良かったBFSコードを最終コードにするか迷ったが、最後の自分を信じてビームサーチを投げて終了。

なお、バグっています。
お疲れさまでした。

BFS方針

BFSで各ポーションについて最速で何ターン目に作れるか(同じターンならよい良いinventoryの状態の方)を調べる。
ポーションを作った後2個目のポーション作成は考えない。
queueにpushする回数が自分は16000回、相手は5000回になるまで別々に探索をする。
この時、初期のCastは最初の1個以外の3個は無視する(inputの時点で飛ばしておく)。
inventoryの状態、Castの状態、各tomeについてlearnできるか(bitset)、restしても良いか(1個以上Castを使っている状態か)のboolをもって、探索。
探索後、各ポーションについてかかるターン数とその後のinventoryの状態とそのポーションの価格から最大効率のものを選んで行動する。
ただし、相手もそのポーション狙いで、かつ相手の方が先にできる場合は次点のポーションを選ぶ。

ビームサーチ方針

大体BFSと同じ。
幅を450で抑えて、自分はpriority_queueにpushする回数が9200回までになるように探索をする。
相手については、ビームサーチを行わず上記のBFSをpush 4000回で行う。
ビームサーチの評価としては、作成するポーションの価格、inventoryの変化、restにより再使用可能になるCastの個数、learnのtaxなどを適当に評価に含めた。
評価関数については、頑張る時間がなかったのでかなり適当なままになっている。
探索の後はBFSと同じ。

感想

めちゃくちゃ楽しかった。具体的には夜7時くらいに開始してそのあと朝の5時くらいまでぶっ通しでやったのが数日あるレベル。

おかげで研究が炎上していて困ったな！

サイコロ

国内予選直前にサイコロにハマっていたことについて書きます。
本当は国内予選の記事のコンテスト前のところに書き足しでいいかなぁと思っていたんですが、僕のサイコロ愛が深すぎて(？)長くなりそうだったので、分けました。
国内予選の記事はこちら

totori.hatenadiary.com

はじめてのサイコロ

偏りのあるサイコロです。この問題を解いたことでサイコロ芸人化が始まってしまった…

サイコロライブラリ作成

サイコロライブラリを作りました。

多分この時お酒を飲んでいて、勢いでやったきがします。

その後

模擬国内予選2020のアローダイス(F問題)

サイコロ職人

サイコロバチャ

(なお、サイコロスタンプしか解いていない)

などのサイコロ活動をしました。

また、紙でサイコロを作ったり、100均でサイコロを買ったりもしました。

おわり

終わりです。ツイートをまとめる以外にすることがなかったので。

ちなみにこれが僕が作ったサイコロライブラリです。
バグってたら、すまん github.com

ICPC国内予選2020

チームATELIERで参加しました。
5完24位、学内2位での国内予選通過です。おめでとう。ありがとう。
https://pbs.twimg.com/media/EmIpCypU4AAn7O3?format=png&name=large

チームメンバーは、
ととり(totori_nyaa) : サイコロ担当。生まれた時からいる。青。国内予選1週間前にチーム内レート1位の座をbinくんに奪われる。
くれそん(qLethon) : 構文解析担当。去年からいる。たまに水に落ちるけど大体青。
びんくん(bin101) : 幾何担当。今年から。青。国内予選時点でレートが一番高い。
でした。

コンテスト前

週1のペースでnowcowと合同チーム練をしていた。

1週間分くらいのツイート見返してたらめっちゃ冷え散らかしてて笑う(ｷｬｯｷｬｯｷｬ)

これは国内予選3日前に構文解析担当を疑う僕

これのおかげで(？)くれそんが構文解析の問題を埋めて、後述のD問題をちゃんと実装できたらしい。
やっぱりチームメイトには問題を埋めさせるべきなんですよね～(？)

前日までの精進量は、こんな感じ。 f:id:totori_nyaa:20201107114938p:plain

当日は昼食前に去年の国内予選のEを解こうとして破滅していた。
昼食後はだらだらとTwitterとかソシャゲとかで時間をつぶしていた。

これはコンテスト開始10秒前までTwitterをやっている人

コンテスト

まさかのコンテストページにアクセスできなくて困った、焦った、困り果てた。
自分のチームだけが繋がらないのではと思ってかなり焦っていたんですが、電話をしても繋がらなかったので他のチームもアクセスできないのかしらねと察した。
そうしている間に問題が見れるようになったのでAを開き、読み、通す。

戦略としてはととりがA、くれそんがB、binくんがCを担当し、Aを一瞬で終わらせたととりがDを読むという流れ。
Dを開くと構文解析が出て困った。とりあえず構文解析担当のくれそんに報告して、構文解析以外のパートの考察を始める。

D、わからん、困った。何も分からん。となっていると、BもCも大変そうなのでそっちを手伝うか～となった。
C、感覚的にできるだけ近いほうが良いので、3乗根付近の値をテキトーに探索するので良くね？と言い、実装するとWAが出た。すまん。 多分CでWAを出している間にくれそんがBを通していた。
え、Cわかんね～～とか言いながらごちゃごちゃやっていると、くれそんがよく分からないけど通していたのでヨシ！

Dがわからんので、とりあえずE~を見ることにした。
Eはよくわからん数え上げ、Fは読んでない(何故！？)、Gもしかしてワンチャンあるかと思ったので読むが、わからん、Hは図がやばそうだったので読んでない、をした。
Dを3人で考えていても何も分からんので、2人に投げて別の問題をやるか～となった。なお、別の問題をやることを報告していない。チームワークの無さ。
多分この時点で2時間で3完、100位くらいだったので心が完全に冷え切る、ピンチ！

ここでようやくFを読むと、105だったので「ICPC的に1010はセーフ！！！」と叫んで愚直解を生やして実装をする。

C++を信じろ。

愚直に実装をすると時間よりメモリの方が爆発する可能性があったので、それに気を付けながら丁寧に実装し、サンプルを合わせたところでようやくチームメイトにFをやっていてサンプルが合ったことを報告する(チームワークの無さ)

投げると落ちて、キレる。
自分の出力をよく見ると、1行だけ何も出力されていない行を見つける。
そのケースを確認すると、m=0のコーナーケースであることが判明、1010にコーナーケースを置くなよとキレる(想定解は確実に1010ではない)
コーナーの処理をして再び5分回して投げるとACでテンションが上がる。さらに5分回してAC、キタコレ！！！！！！！

これが5分かかるやつです。 github.com

この時点で残り20分くらい、くれそんがDを通すことを全力で祈りつつEを読む。

その5分後くらいに、くれそんがDを通していたので天才～～～～！！！って叫んで軽く盛り上がった後、Eの方針(嘘)が浮かんだので急いで実装→嘘が判明して撤退をした。
コンテスト終了までnowcow(農工大から出ているもう1つのチーム)がつえ～～～という話などをして終了。

おわりに

国内予選突破出来て良かったぜ！！！！！！！！！！
横浜でもよろしくな！！！！！！！！

模擬国内予選2020

5完16位でした。

f:id:totori_nyaa:20201025230244j:plain

農工大から出ているもう1つのチームにペナの差で負けた。悲しい

自分はA,Dを担当しました。
ライブラリの準備をしていたが、なんと環境構築以外で使わなかった。
チームとしては僕(AtCoder Highest黄色だけど最近は1900くらいで停滞)、くれそん(Highest青だけど今多分水)、binくん(青で最近レート抜かれた)の3人でした。
チームメンバーのレートの割には上位に食い込めたので結構うれしいのですが、勝っていると思っていたチームに抜かれてたり個人的に意識しているチームに負けていたりだったので悔しさはあります。

コンテスト

連絡手段はDiscordの通話+DM。

開始直後、Aを読む。問題を理解したのでエディタの環境構築をする。{}にするべきところを[]にしていて1分くらいロス。
環境構築後一瞬でAを通してDに向かう。

Dを読む。括弧文字列系は個人的に苦手なので嫌な気分になるががんばる。
制約的にこれは貪欲じゃないと無理だとエスパーして、頑張って睨んでいると、(と)で別々に挿入する数を調べられそうなことに気づく。
この間にCがえらいバグっていて2人でデバッグをしていた。大変そうだなぁと思っていた。
とりあえずコードが書けたので提出するとWA。
困ったのでとりあえずテキトーに手作業で怪しそうなケースを作って試すことを5分くらいやると、落ちるケースが見つかる。
落ちるケースから間違ってる原因がわかったので修正してAC。
僕がDをやっている間にBが通っていた。

Bを通したくれそんがEを読んで2-SATっぽいと言う。問題を読んで、せやなと言う。
2-SAT誰も持ってなかったので手元の蟻本で調べると存在したのでそれを伝える。
解法を聞くとかなり激ヤバな計算量のように感じたので(気のせい)、他の問題と並行で計算量落とせないか考えていた。
かなり計算量を改善できそうな解法を思いついたのでとりあえず書いてみるが、サンプル合わない、終わり。
そうしている間にくれそんがEを通していた。実は計算量は(ICPC的に)そこまでヤバくはなかった。

残りFGHの3問で、Fは明らかに実装がヤバそうだしサイコロの復元パートもよくわからん。
Gもヤバそうな幾何で、ヤバそうなので放置。
というわけで残り時間的にも比較的ワンチャンがありそうなHを考える。
様々な嘘を生やしたりしているとコンテストが終了した。終わり。

コンテスト後

1時間くらい感想戦をしたりTwitterを見たり自分の解法でEとかHをやってた。
Eの嘘に気づく、Hはサンプル以外全滅+せぐふぉなど。

TODO

  • 国内予選までにちゃんとライブラリを整備する

  • stack overflowにならないようにどないかする

部分列のMEXをセグ木で計算する方法 (Codeforces Round #678 (Div. 2) E. Complicated Computations)

問題

codeforces.com

長さ N の配列 A が与えられる。
A の空でない任意の部分列のMEXからなる数列のMEXを計算してください。

解法

RMQのセグ木を使ってなんやかんやええかんじにする。

  • 数字をkey, index を value としてセグ木に乗せる(この表現でいいのかわかんない)

  • 配列を前から見ていく。

  • 各値について、最後に出てきた位置として-1で初期化しておく。

  • 部分列のMEXで a_i を作れるかどうかは、前回出てきた a_iの位置とiの間に 0から a_i-1が全て存在すればよい。

  • a_iが最後に出てきた位置を更新する。

  • 一番最後に、一番最後に出てきたiの位置からn-1の位置まででMEXをiにできるかを調べる

コード

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;

template < typename Monoid >
struct Segtree{
    using FM = function < Monoid(Monoid, Monoid) >;
    using FA = function < void(Monoid&, Monoid) >;
    int N;
    vector<Monoid> dat;
    
    const FM fm;
    const FA fa;
    const Monoid M1;

    Segtree(int n,const FM fm, const FA fa, const Monoid &M1): fm(fm), fa(fa), M1(M1){
        N = 1;
        while(N < n) N *= 2;
        dat.assign(2*N,M1);
    }

    void set(int idx, const Monoid &x){
        dat[idx+N-1] = x;
    }

    void build(){
        for(int i=N-2; i>=0; i--){
            dat[i] = fm(dat[2*i+1], dat[2*i+2]);
        }
    }

    void update(int idx, const Monoid &x){
        idx += N-1;
        fa(dat[idx],x);
        while(idx > 0){
            idx = (idx-1)/2;
            dat[idx] = fm(dat[idx*2 + 1], dat[idx*2+2]);
        }
    }

    Monoid get(int a, int b, int k, int l, int r){
        if(r<=a || b<=l) return M1;
        if(a<=l && r<=b) return dat[k];
        else{
            Monoid vl = get(a,b,k*2+1,l,(l+r)/2);
            Monoid vr = get(a,b,k*2+2,(l+r)/2,r);
            return fm(vl,vr);
        }
    }
    Monoid get(int a,int b){ return get(a,b,0,0,N); }

    Monoid at(int k) {return dat[k+N-1];}

    void debug(){
        for(int i=N-1;i<dat.size();i++){
            cerr << dat[i] << ", ";
        }
        cerr << "\n";
    }
};

// Range Minimum Query
auto fm = [](ll a,ll b){ return min(a,b); };
auto fa = [](ll& a, ll b){ a=b; };
Segtree<ll> seg(100010, fm, fa, 1e9);


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    int n;
    cin>>n;
    int a[n];
    bool one = true;
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i]--;
        if(a[i] != 0)one = false;
    }
    bool ans[n+5]={};
    for(int i=0;i<=n+5;i++)seg.set(i,-1);
    seg.build();

    // 0 以外があるならばMEXを0にできる
    if(one == false)ans[0] = 1;
    for(int i=0;i<n;i++){
        // 0 は、やばい
        if(a[i] == 0){
            seg.update(0,i);
            continue;
        }
        // 0, ..., a[i]-1 で、最も左にあるもの(出ていないなら-1)の位置を調べる
        ll mi = seg.get(0,a[i]);

        // 最後に出てきたa[i]の位置を調べる
        ll pre = seg.at(a[i]);

        // pre より右側でだけで 0, ..., a[i]-1を全て持っているなら、MEXはa[i]
        if(pre < mi)ans[a[i]] = 1;

        seg.update(a[i],i);
    }
    
    // 1,...,n+1 の全てで、一番最後に出てきた位置からn-1の位置までで、MEXをiにできるか
    // 0 は、やばい
    for(int i=1;i<=n+1;i++){
        ll mi = seg.get(0,i);
        ll pre = seg.at(i);
        if(pre < mi)ans[i] = 1;
    }

    // 最大でn+1 (0-indexed)
    for(int i=0;i<=n+5;i++){
        if(ans[i] == 0){
            cout << i+1 << endl;
            return 0;
        }
    }
}