ICPC 2022 国内予選参加記 - xryuseix’s diary progress

概要

チームxmemskyxで参加して66位でした。

Bの考察・実装とCの実装、Dの考察を担当していました。

チームメンバー集め

チームは僕(xryuseix)、husky21stくん、M3_cpくんで出ました。

元々僕とM3_cpくん、僕とhusky21stくんがそれぞれ別のサークルで知り合いで、M3_cpくんが青コーダーだったので僕の方からチームに誘いました。勝つつもりでチームを考えていて、僕とM3_cpくんはアルゴリズム・実装寄りの人間で、husky21stくんは茶色でもかなり数学寄りなので誘いました。

本番の様子

環境はこんな感じでした。サークルで3部屋確保する必要があったので、僕のチームはRiSTさんに部室をお借りしてこちらで競技に参加しました。プロジェクターが雰囲気あって楽しかったですw

また、あまり写真には写っていませんが立命館大学情報理工学部サイバーセキュリティ研究室さんより大量のお菓子と飲み物をいただきました(中央右の黄色い箱)。非常に助かりました、ありがとうございます！

ここからはコンテストの様子を時系列順に記載します。

4:18 husky21st「Aとけた」

「おおおおお早ぇ🎉」って感じでした。husky21stくんの5分未満でノーペナは非常にありがたかったです。この時僕はBを担当(実はここ時点で問題文を8割型しか理解できていなかったのは内緒♡)していて、M3_cpくんはCとDを読んでいてくれていました。

Cが数学より問題だったので、husky21stくんとM3_cpくんで軽くCについて考察したのち、husky21stくんはそのままCに取り掛かり、M3_cpくんがDを考えます。

17:15 xryuseix「Bとけたうおおおおおお」

Bは例年のBにしては実装が面倒だったかなと思います。概要はこんな感じです。

N人の参加者が1~Nの数字が2枚ずつ書かれたトランプでババなしババ抜きを行います。隣の人から引くカード(必ず最小のトランプを引くことになっています)は何回ですか？

Nは1000ですが、各トランプに注目すると1周する前に必ずペアができるので、単純にシミュレートしてもO(N²)です。そのまま実装します。

こういう複数人がターン制のゲームに参加し、それをシミュレートする問題は競プロでよく出てくるので、普通に実装しました。

int main() {
    while (1) {
        int ans = 0;
        int n;
        cin >> n;
        if (n == 0) break;
        int left = n;
        vector<set<int>> s(n);
        rep(i, n) {
            int c1, c2;
            cin >> c1 >> c2;
            if (c1 == c2) {
                left--;
                continue;
            }
            s[i].insert(c1);
            s[i].insert(c2);
        }
        int turn = 0;
        while (left > 0 && s[turn].size() == 0) {
            turn = (turn + 1) % n;
        }
        while (left > 0) {
            int next = (turn + 1) % n;
            while (left > 0 && s[next].size() == 0) {
                next = (next + 1) % n;
            }
            ans++;
            assert(s[turn].size() > 0);
            int card = *(s[turn].begin());
            s[turn].erase(card);
            if (s[turn].size() == 0) {
                left--;
            }
            if (s[next].count(card) == 0) {
                s[next].insert(card);
            } else {
                s[next].erase(card);
                if (s[next].size() == 0) {
                    left--;
                }
            }
            turn = (turn + 1) % n;
            while (left > 0 && s[turn].size() == 0) {
                turn = (turn + 1) % n;
            }
        }
        cout << ans << endl;
        assert(left == 0);
        rep(i, n) { assert(s[i].size() == 0); }
    }
}

バグりそうですが、落ち着いて書いてAC。ここで順位表を見ると、多くのチームがまだBをとけていなくてガッツポーズしました。一応弊チームの実装担当として首の皮が繋がりました。(これでペナしてたら土下座するところだったぜ......💦)

あと今日実装しながら思いついたのですが、ICPCはローカル実装なので、できるだけassertは書いた方が良さそうですね。

51:31 xryuseix, husky21st「Cとけたいえええええええええええいい！！！👏」

実は僕がBを解いた17分ごろにhusky21stくんはCの解法を殆ど用意してくれていました。細かいところを軽く(5分くらい)考察して、僕が実装しました。

Cの問題概要はこんな感じ

n+m日のうち、n日間練習を行い、m日間休憩を行います。k日間連続で練習を行う場合はk日目にスコアを2k-1加算し、k日間連続で休憩を行う場合はk日目にスコアを2k-1減算します。スコアを最大化してください。

解法としては

休憩(約k日) 練習休憩(約k日) 練習 ... 休憩(約k日) 練習練習練習練習練習練習休憩(約k日)

のように休憩をできるだけ等しく分割し、その間に練習を挟み、1箇所に大量練習を入れます。また、休憩の分割数を全探索しました。

実装は僕がしましたが、この問題は僕よりhusky21stくんがMVPでした。解法の方針だけでなく、等差数列の和や、幾つかの数式の変形を聞いたら一瞬で答えてくれて助かりました。

あと提出直前に「これ、m==0で落ちません？」って言ってくれたのも神でした。

int main() {
    while (1) {
        ll n, m;
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        vll div(m + 1);
        for (ll i = 1; i <= m; i++) {
            ll a = m / i;
            ll mod = m % i;
            ll b = m / i + 1;
            ll b_num = mod;
            ll a_num = i - mod;
            assert(a_num >= 0);
            assert(b_num >= 0);
            ll score = (-a * a * a_num) + (-b * b * b_num);
            div[i] = score;
        }
        ll ans = -LLINF;
        if(m == 0) {
            ans = n * n;
        }
        for (ll i = 1; i <= m; i++) {
            if (i <= 2) {
                if (i == 2 && n == 0) {
                    continue;
                }
                ll tmp_ans = n * n + div[i];
                chmax(ans, tmp_ans);
            } else {
                if (i - 2 >= n) {
                    continue;
                }
                ll one_num = i - 2;
                ll lest = n - one_num;
                ll tmp_ans = lest * lest + one_num;
                tmp_ans += div[i];
                chmax(ans, tmp_ans);
            }
        }
        cout << ans << endl;
    }
}

提出すると一発AC。この時点(51:31)でノーペナ3完30位。これにはチームメンバー総拍手でした👏 (高速ノーペナ3完はマジでマジでマジで×998244353偉かった)

51:31 ~ 3:00:00

ここからが地獄です。大量の嘘解法を生成するマンと人の解法を撃墜するマンを担当しておりました。

僕はDPを推していて最終的な列になるような列の分割の仕方というのは普通に求まりそうで、その中から元の列に復元できるパターンを経路の数え上げに帰着して計算する手法を考えていました。ただ、これの問題はノードが最大N²、エッジがN²くらいあり、枝刈りしてもノードはN * (定数)くらい、エッジがそこそこあり困っていました。

チームでは割と最初の方にM3_cpくんが「必ず区切らなきゃいけないラインがあるよね」という話をしており、そこの共有はできていたのですが、「区切っても区切らなくても良いライン」というのが思い付かず(正確には出ていたが、その解法の判定と正当性が証明できなかった)、想定解法のように行かず残念でした。

このチームなら普通に解けた難易度だったので非常に残念でした......。