CODE FESTIVAL 2016参加記

はじめに

この記事は，OIT Advent Calendar 2016 - Adventarの2日目の記事です．
OITとの関わりとしては現在IS科の3回生です．
つい先日CODE FESTIVALという競技プログラミングの大会の決勝に参加してきたので，大学の人への宣伝も兼ねて参加記をAdvent Calendarとして書きます．

本選まで

CODE FESTIVALではA,B,Cの3つの予選があり，大学生以上の学生のうち既に通過した人を除いてそれぞれ100位以内，60位以内，60位以内の人が東京で行われる決勝に招待される．僕は予選Bで60位以内に入れたらしく通過した．

予選A

ACM-ICPC国内予選ぶりに競技プログラミングの大会に参加した．結果的に3完早解きが予選通過ラインだったが，あまりコーディングが速い方でもないので297位で無事死亡した．

予選B

お昼開始のコンテストで，起きてご飯食べてお昼寝していたら15分寝坊して絶望しながら参加した．実験用の図を紙に書こうとしてもうまく書けなかったので，本当に寝ぼけていたように思う．C問題，D問題が貪欲法が想定解の問題で，うまくその解法に気付けたので171位といういい順位を取ることができ，予選を通過できた．

本選

会場まで

12時の開会式に間に合うように7時に家を出た．地元の在来線に乗った瞬間スマホの充電器を家に忘れたことに気付いて絶望．
新幹線で富士山や新橋で電通のビルの写真を撮影した．

昨年得た知見として早めに会場に到着することで，交通費精算列を回避でき任意のサイズのTシャツを選べることがわかっていたので，早めに会場に到着するようにしていた．

コンテストまで

Indeedのツアーで一緒だったStoneDotさんや，KUPCで会って以来だったomuさん，やざてんさんに会ってパーカーほしいよねって話をする(決勝で一定以上の成績を取るとパーカーがプレゼントされる仕組み)． テーブルには軽食が用意されていた． それとお菓子も去年同様用意されていてハッピー

コンテスト

A

やるだけ

int H,W;
string S[26][26];
int main() {
    cin>>H>>W;
    rep(i, H) rep(j, W) cin>>S[i][j];

    rep(i, H) rep(j, W) {
        if(S[i][j] == "snuke") {
            printf("%c%d\n", j + 'A', i + 1);
        }
    }

    return 0;
}

B

問題文に最大値の最小化が見えたので思考停止で二分探索．ACしてから二分探索部分あまり必要なかったのでは？と気付く．

ll N;
bool ok(ll i) {
    ll d = N - i;
    return i * (i - 1) / 2 >= d;
}
int main() {
    cin >> N;
    if (N == 1) {
        cout << "1" << endl;
        return 0;
    }

    ll lb = 0;
    ll ub = N;
    while (ub - lb > 1) {
        ll mid = (ub + lb) / 2;
        if (ok(mid))
            ub = mid;
        else
            lb = mid;
    }
    cout << ub << endl;
    ll d = N - ub;
    for (int i = ub - 1; i > 0; i--) {
        if (d - i >= 0) {
            cout << i << endl;
            d -= i;
        }
    }
    assert(d == 0);
    return 0;
}

C

問題文を読むと連結か判定する問題だとわかって，制約を見ると人を頂点にグラフを作るとTLEするとわかる．言語を頂点にグラフを作るとうまくいきそうな気がしてコードを書く．言語1が必ず入力の中にあると勘違いしたコードを書いて1WAを貰うが修正してAC．

int N, M;
int K[100005];

int main() {
    cin >> N >> M;
    UnionFind uf(M);
    set<int> s;
    rep(i, N) {
        cin >> K[i];
        vector<int> vec;
        rep(j, K[i]) {
            int a;
            cin >> a;
            a--;
            s.insert(a);
            vec.push_back(a);
        }
        rep(j, vec.size()) if (j) { uf.unite(vec[j], vec[j - 1]); }
    }
    if (uf.size(*s.begin()) == s.size())
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

D

modで分類するのはすぐにわかったけど，二つの条件をどう使っていくかがわからなかった．とりあえず，二つ目の条件を先に使うのが正しいと思い込んでコードを書くが，modでまとめた後どうやってペアを見つければいいのかわからず，時間を溶かす．最終的に奇数のやつから使っていってそれでも足りないと偶数のやつを使うコードを書いた．

int N, M;
int X[100005];
int cnt[100005];
int mod[100005];
int pena[100005];

int main() {
    cin >> N >> M;
    rep(i, N) cin >> X[i];
    rep(i, N) cnt[X[i]]++;
    rep(i, N) mod[X[i] % M]++;
    int ans = 0;
    rep(i, M / 2 + 1) {
        if (i == ((M - i) % M)) {
            ans += mod[i] / 2;
            pena[i] = mod[i];
            continue;
        }
        int a = min(mod[i], mod[M - i]);
        ans += a;
        pena[i] = pena[M - i] = a;
    }
    int m = *max_element(X, X + N);
    rep(i, m + 1) {
        if (cnt[i] % 2 == 1) {
            cnt[i]--;
            pena[i % M]--;
        }
    }
    rep(i, M) {
        if (pena[i] > 0) {
            ans -= (pena[i] + 1) / 2;
        }
    }
    rep(i, m + 1) ans += cnt[i] / 2;
    cout << ans << endl;

    return 0;
}

E

この問題を解くと決めた段階で残り時間は50分程度だった．3時間コンテストはハマるとすぐに時間が溶けるので厳しい．TLEするDPは書けたけどここからどう計算量を減らすかがわからず時間を溶かす．終了10分前ぐらいににすれば良さそうなことに気付くけど状態の更新式がわからず終わり．

結果

4完で1500点の159位だった．あと100点でパーカーだったので悔しい．去年より順位を落として全体のレベルが上がっているのかなと感じた．

touristのトークライブ

2日前ぐらいにハッシュタグで質問したい内容を募集していたので，前から気になっていたことを投稿した．

競プロとの出会い#CODEFES_Question

— 154_odan (@odan3240) 2016年11月25日

プログラミングは，7歳の頃に両親からプログラミングを教わって始めたらしい．競プロは何か言ってたか忘れてしまった． あと競プロをやる上で重要なのは覚悟(日本語訳)って言っていたのは印象的だった．

夕飯

立食形式だった．取りに行ったのが遅かったせいか，残っている寿司ネタの偏りが酷くて笑った．美味しそうなやつを少し摘んで食べた程度

山本一成氏のトークライブ

モジュール化と高速化は両立しないってのは確かにそうだと感じた．また単体テストが重要だと聞いた時，Zebraの作者も同じようなことを言っていたのを思い出した．自分のオセロAI開発もそうだけど，研究にも役立てたいと思った．

iwi先生のペアプロ

全探索のコードの結果を眺めて考察することや図を書いて実験することの重要性を再確認できた．去年と同じで楽しくペアプロの様子を観戦できた．

エキシビションマッチ

今年はチーム戦だった．yurahunaさんと各スクリーンの前を行ったり来たりしていた．驚いたのはtouristのタイピングスピードで，途切れることなく滑らかに文字が入力されていって見ていて笑いがこみ上げた．僕がrepマクロ使ってforを書くより速いスピードで普通のforを書いているんじゃないかと思うレベル．反面autoとかrange-based forを使わずにコードを書いているのはなんでか気になったりした．

ホテル

今年は参加者が全員同じホテルではなく，幾つかのホテルに分散して宿泊することになったらしい．同じホテルの人について行って道に迷うことなく到着した．部屋にはスマホ用の充電器が用意されていて神だった．
このホテルは朝食も無料で用意されいて，特に僕の好物のいなり寿司が食べ放題だったのが嬉しかった．嬉しすぎていなり寿司10個食べたレベル．

トーナメント

テーブルには朝食が用意されていた． いなり寿司をたくさん食べたし賞味期限も先の方だったので後で食べた．
トーナメントの隣の席はpop_left さんで，2年前のRUPCで会ったことを覚えられていて感動しただけでなく，

勝手に同格視していたodanくんとの格付けを済ませるチャンスですねこれは

— おいおい瞬殺だよ (@pop_left) 2016年11月27日

こんなことまで言われてとても嬉しくなった．

Round1

A問題とB問題の両方に目を通す．部分点的にB問題の方が簡単だと思い400点ぐらい取れそうなDPを書き始めるもバグる．気づいた時には終了10分前になっていて，もっと低い部分点を取りに行こうとするも，うまくコードが書けず死亡．朝から太陽を生やした．去年の朝プロもそうだったけど朝は弱いらしい(?)

Round2以降

和エリアに移動してStoneDotさんとゆっくり問題を解いた．コンテストの間にまーすさんが来てテンプレートにINFは含めないほうがいいなどの有り難いお言葉をいただいた．
トーナメントのシールはRoundを通過するごとにもらえるらしく，それらをすべて組み合わせるとCode Festivalのロゴになってかっこいいと思った．

お昼

お腹が満腹気味だったが，"まい泉のとんかつ"というワードに勝てずトンカツ弁当を選んでしまう．
きついきつい言いながらも完食できた．
それと海外勢がお箸を使ってお弁当を食べていたことに驚いた．

LT

きゅうりさんが芸人していた．途中から見たので後で公開されると嬉しいなあ

挑戦状

今年も乱数で生成した色のRGB値を答える問題や，公式サイトの間違い探しなどへんてこな問題が多くてずっと笑い続けた．脳内で世界地図渡り歩けるのすごい．

リレー

去年は薄いピンク色だったけど今年は濃いピンク色だった．大学に来ていくか迷う．
本選の順位的にD問題を担当した．D問題は全探索するだけの簡単な問題だったが，チーム戦であることの緊張からかタイピングする手が震えていた．その結果配列の添字をtypoしていて一発AC出来ず，レプトンさんにもっと良い解法を教えてもらいそれでACした．
その後は他の人の担当している問題を一緒に考えて嘘解法を生やしたりして足を引っ張ってしまった．

表彰

ずっと立っていたせいか，身体がしんどくなったので地面に座って聞いていた．最近こういうことが多いので老いを感じる．
今年はサブイベント(?)に体力測定が追加されていたけど，これも何かデータ解析して発表したりするのかなと思った．体力測定は，中学の頃運動部なのに体力測定で学年最下位を取るレベルで運動は苦手なので上位は狙えないだろうし，大学の体力測定で腰を痛めたことがあったので考え軽めにやった．

閉会式

去年と同じく集合写真を撮った．
集合写真のために整列している時去年のことをふと思い出してしまい，あれからもう1年なのかと時間の速さを感じた．

帰路

NAIST勢の方と品川まで一緒に帰った．

終わりに

コンテストだけでなくサブイベントも楽しい大会でした． 今年は大学からは自分ひとりしか決勝に参加できなかったけど，来年も開催されるなら他の人と一緒に行きたいなあと思いました．
！！弊学の競技プログラミングチームは火曜5限と金曜5限に活動しているので興味ある人はぜひ声をかけてください！！

3日目はkeyakkoさんの「使用済Androidを適当にサーバ化して活用」です．楽しみですね！