InTheDayDream

ICPC国内予選2025(Chofu Mai)

Published on 2025-07-05
Last Modified 2025-07-05

Table Of Contents

はじめに

ICPC国内予選2025に参加して、予選で敗退した。 正確にはまだ正式発表されていないが、同校3位で50位なのでまず無理だろう。

チーム

チームChofu Mai

二人は私が声をかけてくれたら快諾してくれた。 三人の実力がほぼ拮抗しており、得意分野もそんなに偏っていなさそうで良いチームになったと思う。

本番2カ月前くらいから週一回集まって問題を解く練習をしていた。 対面で問題を考える時間を取ったおかげで打ち解けられて、いろいろと連携がとりやすくなったような気がする。

チーム名はADさんが提案してくれた。 正直元ネタには詳しくないが、 調布のりこ 麻布麻衣 というキャラクターのキメラ語だったらしい。

国内予選模擬

模擬に出ていた。5AC、66位。 順位表

運よく同校一位だったため、ギリギリ予選通過できる位置だった。

ABはmidさんとADさんがAC、Cは私がAC。

D問題: 私とADさんがにらみつけるが、クエリ$N$回の制約がどうしても厳しい。 分割統治をはじめとしたいろいろな解法を検討するが、どれもうまくいかない。 どう考えてもYes以外の返事を活用するしかなさそうだが、全くわからない。

そうこうしているうちにEをmidさんが読解。こういうCS系みたいなのにおそらく一番強いので考察を詰めてもらう。 実装ができそうだとのことなのでパソコンを渡す。まだDは光明が見えない。

しばらくたって、「else」などのバケモノみたいな変数名があり得ることに気が付く。頑張って構文解析を書いてくれていた。

私とADさんでDを引き続き睨む。全然わからない。と思っていたが、ADさんが左から1ずつ伸ばしていき、そのYes/No判定で(か)を一発で判定できる可能性に気づく。 なるほど、確かに、、、

Eのサンプルが合うがTLE。ここでバトンタッチして私がDの実装をする。 少ししてサンプルが合うが、心配なのでテストケースを生成して試す。 ここでmidさんが落ちるケースを見事に組んでくれた。

括弧列の構造によっては左側の構造が崩れてしまうことがわかったが、これは左側として使える候補点を持っておくことで修正可能だった。これを直してAC。

midさんの実装の計算量が壊れていそうなことに気づく。修正できそうとのことだったので実装を見守る。 サンプルが合ったので提出。しかしまさかのrun errorが出てしまう。 みんなで実装を睨むがどう考えても実装はあっていた。どこにrun errorの要素が…

問題文を読み返していると、BNFの定義は数一つだけのリテラルも許容されることに気が付く。一同大横転。 これに対応すると無事AC。デカい声、デカ声が出てしまった。

国内予選

祭りは始まる前が一番楽しいというのは世の常であり、私はChofu Maiパソコン担当としていろいろと変な準備をしていた。

ドキュメント整備

変なライブラリを要求されたり、言語仕様がわからなくなって困らないように、

を完全にローカルで見れるようにビルドおよびホストをした。 competitive-verifierとjekyllを使ったが、如何せん細かい仕様についてのドキュメントがどこにも見当たらなくて苦労した。 そもそもcompetitive-verifier docサブコマンドで何が要求されるのかの仕様がよくわからなかったりしたが、一日中パソコンに向き合うことで何とか解決した。

docを生成できた後もjekyll無しでホストできるような形に改造するのにはかなり苦労した。 特に、Nyaan’s Libraryとkyopro_libraryはcompetitive-verifierで構築されていなかったため、細かい部分を調整するスクリプトを2つほど用意する必要があった。

これらのドキュメントはpythonのhttpモジュールを使ってlocalhostに公開して使った。結局本番で参照することはなかったが…

また、これらのページへのクイックアクセスを実現するために、ハブページのhtmlも用意した。ついついおふざけを入れてしまった。 今手元にあるのは本番用いたのと少し違うプロトタイプだが、それを公開する。

hubpage.png

平成初期のhtmlをイメージしてAIで生成したものを手直ししたものだが、本番ではここに使いそうなページのリンクを貼った。

テンプレート整備

ADさんのC++テンプレートをいろいろと魔改造したものを使った。魔改造というのは別に三人で協議して入れたものという感じではなく、私が勝手にごり押しして付け加えたものである。

C++に関する自身の経験から、

  1. 変数のダンプがアホほどだるい
  2. 範囲外参照してしまった時に詰みになる

という点を解消することを目標に考えた。 前者は cppdump というヘッダライブラリをローカルのみincludeして利用した。 また、C APIのsleep()をラップしたSLEEP()マクロを導入し、無限ループなどでのログ速度を律速させて変数ダンプをまともに見れるようにした。(これはmidさんが発案してくれた。) あとはまたおふざけを入れたい気持ちが出てきてしまい、変なデコレーション用のマクロを導入した。

後者はstd::vectorをラップし、std::source_locationを利用したclass svsave vectorの意)を作り、導入した。

結局本番で利用したテンプレートは以下のようになった。

まずはclass svを紹介する。細かい部分はわからないので、AIに実装してもらい、それを私が実際に使ってテストした。

#include <iostream>
#include <vector>
#include <cstdlib>
#include <source_location>

template <typename T>
class sv : public std::vector<T> {
    static_assert(!std::is_same_v<T, bool>,
        "sv<bool>は動きません(ごめん)");

public:
    using std::vector<T>::vector;
    explicit sv(const std::vector<T>& v) : std::vector<T>(v) {}
    explicit sv(std::vector<T>&& v) : std::vector<T>(std::move(v)) {}

#ifdef CHOFUMAI
    T& operator[](size_t index) {
        if (index >= this->size()) {
            handle_bounds_error(index, std::source_location::current());
        }
        return std::vector<T>::operator[](index);
    }
    const T& operator[](size_t index) const {
        if (index >= this->size()) {
            handle_bounds_error(index, std::source_location::current());
        }
        return std::vector<T>::operator[](index);
    }
    T& operator()(size_t index, const std::source_location location = std::source_location::current()) {
        if (this->size() <= index) handle_bounds_error(index, location);
        return std::vector<T>::operator[](index);
    }
    const T& operator()(size_t index, const std::source_location location = std::source_location::current()) const {
        if (this->size() <= index) handle_bounds_error(index, location);
        return std::vector<T>::operator[](index);
    }
    
    T& front(const std::source_location location = std::source_location::current()) {
        if (this->empty()) handle_empty_error("front", location);
        return std::vector<T>::front();
    }
    const T& front(const std::source_location location = std::source_location::current()) const {
        if (this->empty()) handle_empty_error("front", location);
        return std::vector<T>::front();
    }
    T& back(const std::source_location location = std::source_location::current()) {
        if (this->empty()) handle_empty_error("back", location);
        return std::vector<T>::back();
    }
    const T& back(const std::source_location location = std::source_location::current()) const {
        if (this->empty()) handle_empty_error("back", location);
        return std::vector<T>::back();
    }

    [[noreturn]] void handle_bounds_error(size_t index, const std::source_location& location) const {
        std::cerr << "【範囲外アクセスエラー】\n"
                  << "  ファイル: " << location.file_name() << "\n"
                  << "  行: " << location.line() << ", " << location.column() << "文字目\n"
                  << "  関数: " << location.function_name() << "\n"
                  << "  配列サイズ: " << this->size() << "\n"
                  << "  アクセス添字: " << index << "\n";
        std::exit(1);
    }
    
    [[noreturn]] void handle_empty_error(const char* operation, const std::source_location& location) const {
        std::cerr << "【空配列アクセスエラー】\n"
                  << "  操作: " << operation << "()\n"
                  << "  ファイル: " << location.file_name() << "\n"
                  << "  行: " << location.line() << ", " << location.column() << "文字目\n"
                  << "  関数: " << location.function_name() << "\n";
        std::exit(1);
    }
#else
    T& operator[](size_t index) {
        if (index >= this->size()) {
            handle_bounds_error(index);
        }
        return std::vector<T>::operator[](index);
    }
    const T& operator[](size_t index) const {
        if (index >= this->size()) {
            handle_bounds_error(index);
        }
        return std::vector<T>::operator[](index);
    }
    T& operator()(size_t index) {
        if (this->size() <= index) handle_bounds_error(index);
        return std::vector<T>::operator[](index);
    }
    const T& operator()(size_t index) const {
        if (this->size() <= index) handle_bounds_error(index);
        return std::vector<T>::operator[](index);
    }

    T& front() {
        if (this->empty()) handle_empty_error("front");
        return std::vector<T>::front();
    }
    const T& front() const {
        if (this->empty()) handle_empty_error("front");
        return std::vector<T>::front();
    }
    T& back() {
        if (this->empty()) handle_empty_error("back");
        return std::vector<T>::back();
    }
    const T& back() const {
        if (this->empty()) handle_empty_error("back");
        return std::vector<T>::back();
    }

    [[noreturn]] void handle_bounds_error(size_t) const {
        std::exit(1);
    }
    [[noreturn]] void handle_empty_error(const char*) const {
        std::exit(1);
    }
#endif

    std::vector<T> copy() const {
        return *this;
    }
};

#include <iostream>
using namespace std;

int main () {
    sv<int> v(5, 10);
    vector<int> x(10);

    cout << v[0] << v[1] << endl;
    //v[-1];
    v[5];

    sv<int> y(move(x));
    sv<int> p, q;
    swap(p, q);

    auto vv = v.copy();
    cout << vv[0] << endl;
}

テンプレは以下である。g++ -std=c++20 -I path/to/cpp-dump -D CHOFUMAIといったコンパイルオプションでデバッグ機能が利用できる。他のテンプレートに比べてユニークな機能があると自負している。是非手元で動かしてみてほしい。

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

#ifdef CHOFUMAI
#include <cpp-dump.hpp>
#define dump(...) cpp_dump(__VA_ARGS__)
#define PARTITION() cerr << "====================" << endl
#define START() \
    std::cerr << "\n╔══════════════════════════════════════╗\n" \
              <<   "║             START PROGRAM            ║\n" \
              <<   "╚══════════════════════════════════════╝\n";

#define END() \
    std::cerr << "\n╔══════════════════════════════════════╗\n" \
              <<   "║              END PROGRAM             ║\n" \
              <<   "╚══════════════════════════════════════╝\n";
#define SLEEP() sleep(1)
#else
#define dump(...)
#define PARTITION()
#define START()
#define END()
#define SLEEP()
#endif

using ll = long long;
using ull = unsigned long long;
using ld = long double;

using LL = long long; using ULL = unsigned long long;
using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>;
using VL = vector<LL>; using VVL = vector<VL>; using VVVL = vector<VVL>;
using VB = vector<bool>; using VVB = vector<VB>; using VVVB = vector<VVB>;
using VD = vector<double>; using VVD = vector<VD>; using VVVD = vector<VVD>;
using VC = vector<char>; using VS = vector<string>; using VVC = vector<VC>;
using PII = pair<int,int>; using PLL = pair<LL,LL>; using PDD = pair<double,double>; using PIL = pair<int,LL>;
using MII = map<int,int>; using MLL = map<LL,LL>;
using SI = set<int>; using SL = set<LL>;
using MSI = multiset<int>; using MSL = multiset<LL>;
template<class T> using MAXPQ = priority_queue<T>;
template<class T> using MINPQ = priority_queue< T, vector<T>, greater<T> >;

constexpr ll MOD = 1000000007;
constexpr ll MOD2 = 998244353;
constexpr ll INF = 1LL << 60;
constexpr int iINF = 1 << 30;
constexpr double PI = 3.14159265358979323846;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

// repマクロ(REPではなく...笑)
#define rep(i, n) FOR(i, 0, n)

#define EACH(e, v) for(auto &e : v)
#define RITR(it, v) for(auto it = (v).rbegin(); it != (v).rend(); ++it)
#define ALL(v) v.begin(),v.end()

vector<ll> x8={1,1,1,0,0,-1,-1,-1},y8={1,0,-1,1,-1,1,0,-1};
int dx4[4]={1,-1,0,0}, dy4[4]={0,0,1,-1};

namespace libs {
    // ライブラリペタリゾーン
} // namespace libs

using namespace libs;

bool solver () {
    dump("your solution here...");
    return false;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    // 浮動小数点のアレ
    cout << fixed << setprecision(20);

    SLEEP();
    START();

    int testcase_id = 1;
    while (true) {
        PARTITION();
        dump(testcase_id);
        bool next = solver();
        testcase_id++;

        if (!next) {
            break;
        }
    }

    END();
}

あとは、私とmidさんはvim使いなので、vimのキーバインドでvscodeを使えるようになる拡張機能を入れたりした。

本番

振り返るのは気が重いが、書こうと思う。

30分前に会場についた。私は二番乗りで、既にやきとりさんが来ていた。結構ギリギリに来た感じでいたのだが、「30分前に来る人はまれですよ」みたいなことを言われてしまった。 普段オンサイトとかは1時間前くらいに来てるので、客観的に見てバケモノだったのかもしれない。

本番が始まる前に下準備をした。数日前にADさんの環境でドキュメントサーバを立ち上げ、tmuxセッションをデタッチしておいたが、当日見たらプロセスが死んでいた。仕組みがよくわからないが、気を取り直してプロセスを立ち上げなおした。

戦略はあまりなくて、とりあえず早解きがうまい人にAを見てもらって、あとはまあ適当に…みたいなノリで始まった。 Aはとりあえずmidさんに読んでもらう。まあさすがに簡単なのですぐにAC。

別に交代する必要もないのでmidさんに続投でBをやってもらう。 この時nafmoさんからA問題のプリントが島に回ってくる。あの…もうACしており…になった。

一瞬誤読していたようだが、すぐ題意を把握。さすがに制約が小さいのでpythonでAC。

このとき裏で私とADさんでCを読む。$m$がデカいが$n$が小さいので$a _ i$が通常の休日に重なるかどうかだけ注意すれば後はすべて算数になるところまで見えた。簡単そうなのでADさんに任せて私はEへ。

このとき、

という感じでなかなかいい感じだった。ストールが少ないパイプラインという感じ。

midさんがD結構ヤバそうという感じのことを言っていた。ADさんはそれほど経たずにC実装を終え、私と細かいコーナーがカバーできているかチェックし、投下。AC。

midさんがDを書いてみたいといったのでパソコンを渡し、私とADさんはEの考察へ。 木なことと$n \leq 1000$がかなり匂う。すごく貪欲な感じがする。

少したって次の解法を思いつく。

  1. 確定済み頂点に0を割り当て、BFSで距離を算出する。
  2. 各頂点の「スコア」を$e _ i - \mathrm{dist} _ i + 1$で定める。
  3. 最小スコアへと進む。

悪くなさそうだったので、midさんに「解けたかもなので15分くらい経ってまだ出来ていなかったら一旦バトンタッチしてください」と伝える。(あとでわかるのだが、これは嘘解法だった。この嘘考察によるペナルティがチームの致命傷になる。)

案の定Dがかなりヤバいということで、私の実装にバトンタッチ。 実装量は少なくなくて少し時間がかかってしまったものの、基本はBFSを書くだけだったので何とか書きあがる。 このとき用意したsvのおかげで不正な配列参照をすべて検出することができ、爆速でデバッグをすることができた。

サンプルがあったので投げる。Wrong Answerが出てしまう。どうしようもなさそうなのでmidさんにバトンタッチする。

midさんは引き続きDの細かいケースをチェックしながら実装し、私とADさんはEの再考察をする。(ソースコードを印刷したが、クソ長テンプレートのせいで6枚出てくる。)

どうやっても実装ミスが見つからなくて困ってしまった。midさんの方もいろいろなケースで落ちることが発覚したようで、かなり苦しそうにしていた。

Eのソースコードを何回眺めても明らかな瑕疵は見つからなかった。となると、最もスコアが小さい辺まで進め切ってしまうのが嘘という可能性が出てくる。 これはややこしいのだが、「スコアが0であるとき」には上記アルゴリズムは正しくなる。しかし、スコアが0出ないときにはいくらでも反例が出てくることが発覚。なぜ気が付かなかったのだろうか… 未証明ではあるが、一気にスコア最小の辺まで行ってしまうのではなく、一手ずつ進めていく方針なら見つかる反例が潰せそうだとわかった。

このあたりでmidさんがDのコーナーを潰し切り、submitする。ACとなる。ハマるとかなり面倒になりそうだと思っていたので本当にファインプレーだった。

ここで再びパソコンが空いたので改善案を実装。元の解法より簡単なことをやっているので、すぐに修正が終わる。これじゃなければもうどうしようもないのでsubmiする。ACしてしまう… $O(n^2)$時間書けて良いはずなのに変な解法に早とちりしてしまった。

が、この時点ではかなり良い感じだったので、「あと一問は通そう」となる。スコアボードを見る限りFに取り組むしかなさそう。 構築 + 文字列操作ということで私たちが比較的苦手とするad-hoc系問題で焦る。

もうFを通せば勝ちだと思っていたので、3人で取り掛かる。変な操作だったが、落ち着いて考えていく。 まず操作でabの数が変わらないことを共有。これで自明なnoが判明する。

私が「どうせこういうのはいつものARCみたいに妙な操作に言い換えると急に見通しが良くなるやつですよ笑」とみんなに伝える。 ということでそういう言いかえを探す。ほどなくして私が操作ABともに文字列の右rotateに言い換えられることを指摘。 このアイデアを基にしてADさんが後ろからなら任意の文字を持っていけることに気が付く。 あとはこれが10000回に収まるかが問題になる。

後ろ$x$文字を合わせている状態からなら$O(n - x)$回くらいで合わせられる。となると、いつもの$1 + 2 + \dots + n \approx \frac{n^2}{2}$に思いをはせると余裕がありそうなことがわかる。

実装は私が行った。どうせ操作に$O(n)$時間かけて間に合うと思ったので、チェック関数を書いたりした。 思いのほかすぐに組みあがる。 操作回数だけが心配だったのでmidさんにrubyでランテスを書いてもらう。どうやらクエリ回数は大丈夫そうだったのでsubmitする。AC!!!

勝った!と思い順位表を見る。

上にUECが2チーム居た…

この順位では予選突破は絶望的である。この時は本当にやられた…と思った。 残り30分を切っていた。しかしもう一問通さないと負けが確定するので何とか食らいつきに行く。

順位表を見るにGに特攻するしかない。幾何であった。Chofu Maiはチーム練含めこれまで幾何に取り組んだことはない。 二人はどうだったかわからないが、私には暗雲にしか見えなかった。

midさんが題意を把握、ワンチャンにかけて実装を開始。この時点で残り15分くらい。 実装してもらっている途中でようやく題意を把握。しかし解法は何にもわからない。(空間図形を頭に描く訓練をしていないのでどうなりそうか何も見えなかった。)もうmidさんが通してくれるのに賭けるしかない。

ラスト5分程度で実装ができる。最後のサンプル以外合った。 サンプルが合わない理由が浮動小数点に起因すると判断して、大急ぎで整数変換する。

残り2分、実装ができる。サンプルが全部合った。 submitする。。。

しかし、ACできなかった。。。

standing

最終的な順位表はこうなった。 UEC一位は全体47位のUEC25Atsumare、二位は48位のO1_Practice、そして三位が50位のChofu Maiとなった。 驚くほど接戦だった。私の安易なペナルティがなければUEC一位を取れていたことが発覚し、本当にまいってしまった。 あるいはDをあと数分早く出せていれば、あるいはBの誤読の時間消費がなければ、あるいはFのランテスをさぼっていれば。 ベストを尽くしたのだと信じたいが、後悔が出てきてしょうがなかった。

上位チームが7ACで通っていればまだあきらめがつくだろうが、 この負け方は飲み込むに飲み込めなくて一時間ほど椅子に座って助けてくれと言っていた。 夢を見せるだけ見せて取り上げるというのは一番残酷だと思う。SBRのジョニィはこんな気持ちだったのだろうか。

懇親など

正直、問題の解法についての議論をしたい気持ちは全くなかったので椅子でくねくねしていた。 助けてくれと言っていたら時間が過ぎてしまい、CodeWarriorsの三人とコーチをやって頂いたnafmoさんとで食事に行った。 誘っていただきありがとうございました。

HIKKYさん、stratempestさんと話すという珍しい体験だった。CodeWarriorsも来年リベンジするとのことだったので、負けないように頑張りたい。(CodeWarriorsは天才問題を倒せるタイプのチームなので、強い。)

その他

このエントリはもう少し冷静なときに書けばもう少しまともな内容になったと思う。 しかし、後回しにしたら多分書かないだろうと思ったのと、今書いておくことに価値があると思ったから勢いに任せて書き上げた。 いろいろと言葉選びが雑だったりすると思うが許してほしい。

負けた悔しさからいろいろと書いたが、全体的に見てチームChofu Maiはできることをしっかりできたと信じている。 あとは個々人の能力がほんの少し足りていなかったのだろう。 来年同じメンバーで出ることはできないが、midさんとリベンジをしたい。

負けたのが確定したときは「任意へのやる気、消失…」と思っていたが、落ち着いてきた今の気持ちとしては、まだ頑張れそうに思える。 これからも自分のペースで競プロをやっていきたい。