トーナメントグラフの強連結成分について

有向グラフであって，全ての辺の向き付けを取り除いて無向グラフとみなすと完全グラフになるものをトーナメントグラフという．以下では をトーナメントグラフとして，その性質について述べる．証明についてはどれも冷静に考えたら簡単なので省略する．

• 性質1. トーナメントグラフを強連結成分分解してできる縮約グラフは 1 本のパスとなる．
• 性質2. の強連結成分をトポロジカル順に とする(性質1からこの順序は一意に定まる)．任意の および について， の出次数は の出次数より大きい．
• 性質3. とする．このとき頂点 の出次数が であるようなトーナメントグラフ が存在すれば，その強連結成分分解は一意である． の大きい順から見ていってよしなに処理することでこれを特定することができる．

ICPC 2022 Asia Yokohama Regional 参加記

チーム結成から2年半，ずっと待ちわびてきた大会だった．来年度以降のメモとして，大会に向けて準備してきたことや，当日に起こったことについて書いていく．

メンバーはいつもの nok0, zkou, kuma (私) の3人．

• 本番1ヵ月前

公式から横浜大会のアナウンス段々と出されてきた時期だった．このころに当日に選手が用いる計算機環境についての発表があった．

個人的に特に不安視していたのはキーボードで，自分はUS配列のHHKBを使っているのでキーのUS配列自体は問題ないのだが，自分のキーボードはキーバインドをかなり自分用に改造しており，普通のUS配列のキーボードを打つことに全く慣れていないので練習が必要だと思った．

そこで指定されていたLenovoのキーボードをAmazonでポチった．HHKBに比べると安物なので馬鹿馬鹿しい買い物にも思えるが，これまで競プロに費やしてきた時間を考えればまあこれくらいは良いかと思えた．(何ならアマギフもらったりもしたのでプラスまである)．

あと，本番の朝に起きられる気がしなかったのでこのときから生活リズムを22時就寝~6時起床に調整し始めた．おかげでABCやコドフォがかなり犠牲になったが，その分は AOJ-ICPC を埋めたりしてカバーした気になっていた．

• 模擬地区

届いたばかりのキーボードを引っ提げてオンサイトの模擬地区へ行った．私のキーボードのはずなのに nok0 はすいすいとタイピングをしていて，私は矢印キーの操作にまごついていて明らかに実装スピードが遅かった．キーボードを買って良かったと思った．

結果は10位．F いい問題だったから自力で思いつきたかったね．

• 12月上旬

模擬地区があまりうまく行かなかったこともあり，毎週練習しようと言っていたのだがチームメイトのコロナ感染が発覚する．他の知り合いが後遺症に苦しんでいるのを見ていたので怖くなり，さすがにしばらくは療養に専念してもらうことになった．

• 2週間前

チームメイトは無事回復したようで，念願の練習．ICPC運営から渡されていた仮想環境で練習していたのだが，VSCodium に補完もフォーマッタも入っていないことに絶望した．冒頭でまごついたものの最低限通さなければいけない問題は通せたので出来はまあまあ．このころにはキーボードにもそこそこ慣れてきていた．この不便な環境についてもやはり別途練習が必要だなあと言うことになった．今回は使わなかったけど来年は CLion 使ってみようかなあ．

この数日後に私のコロナ感染が発覚する．結局このせいで12月は練習が1回しかできなかった．あのさあ…．

余談だが，チーム紹介スライドが年賀状みたいになってたのは私のコロナ感染によって3人の集合写真が撮れなかったせいでもある．

• 1週間前

熱があった時期は昼も夜も寝まくったので整え続けた生活リズムがめちゃくちゃになった．起きているときは布団の中でずっと kactl の pdf を見ていた．知らないアルゴリズムや知識があったりして普通に勉強になった．

幸い症状は数日でほぼ消失した．サンプル実行用のbashファイルなどを準備したりして残りの隔離期間を過ごしていた．

• 前日

隔離が解除され，2週間ぶりに幾何学の授業に出たら何も分からなかった．復習する間もなくリハーサルへ向かう．

会場で英語使うべきなのか日本語使うべきなのか分からん．チーム紹介のときにチームメイトに「僕たち３人合わせて S! P! J! (1人1文字ずつ言う) でーす！」ってやらない？と誘ったのだが軽くあしらわれた．来年あそこで漫才やりたいけどそれは俺だけらしい．

家に帰るとぐったりして疲れた．SASUKE は最後まで見たかったが，適当なところで切り上げて寝た．

• 当日

なんだかやけに緊張していた．A 問題の実装を始めるときに手が少しかじかんでタイピングにもたついてしまい，カイロを持ってくればよかったと後悔した．

B までの速度は順調だったが，私が D で重い実装を選択してしまい，そこからは A と B の次に簡単なはずの D と G でペナを出し続けるという地獄のような展開だった．あのときの苦しい焦りは思い出したくもない．

なんとか E, F を通し，全く WA の原因が分からなかった G もダメ元で適当にリファクタして投げたら通った．最後は 2 人に言われて D をほぼ全部書き直したが，出来上がったコードはなぜかサンプルに対して意味不明な挙動をしていて，結局その原因も良く分からないままコンテストは終わった．

D も G も明らかに自分たちの実力帯よりは下の問題で，ここは通過点にしなくてはいけなかった．今振り返ると D で重い方針が思いついたときに一旦心を落ち着かせて考え直すべきだったのだが，焦りすぎていてそんな余裕がなかった．

焦っているときに解法らしきものが思い浮かんだ時の快感にも似た安堵の気持ちというのは強烈なもので，それのせいでこれまで何度も失敗しているのだが，今回の大会ではそれを痛感することとなった．

国内予選では 8 位だったし，正直言って 5 完 17 位というのは不甲斐ない結果だと思う．メンタル面が思いのほか大きな自分の課題であることに気付いたので，なんとかそこを改善できるようにしたい．

最後に，3年ぶりのオンサイトのアジア地区大会を準備して下さった運営の皆さま，交流して下さった選手の皆さま，コーチを引き受けてくださった okura さんとさかなさんに感謝申し上げます．ありがとうございました．

ICPC 2019 Asia Yokohama Regional-C Wall Painting (AOJ 1402, 800)

この記事は 帰ってきた AOJ-ICPC Advent Calendar 2022 の6日目の記事です．

問題リンク

onlinejudge.u-aizu.ac.jp

概要(0-indexedに変換後)

横に並んだ 個のマス目があり， の番号がそれぞれついている． 番目のロボットを作動させるとマス目 を色 で塗る． ロボットの動作後のそれぞれのマス目の得点は，そのマス目に塗られた色が0種類であれば0点，1種類であれば 点，2種類以上であれば 点となる．作動させるロボットを自由に選んで良いとき，得点の合計の最大値を求めよ．

制約

問題リンク先を参照．

解法

色の種類が少ないことは使いそう．

基本的に SWAG みたいな色の塗り方をするとして問題ない． の昇順に処理する の遷移はまあ明らかで，これをRMQセグ木で高速化する．塗りの重なる部分は，1マスにつき同色ならば ，違う色ならば だけ損をするので，セグ木の更新時にはこれをあらかじめ引いた値を突っ込むことで適切に大小比較できる．

自分のACコード

https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/1402/judge/7144496/C++17

公式解説 (pdf)

https://icpc.iisf.or.jp/past-icpc/regional2019/commentaries-2019.pdf

の値の昇順に処理するこちらの方が方針としては考えやすそうだ．

感想

の昇順でやろうとしたせいで微妙に考えづらくなって変なバグを埋め込んでしまった．普通に考えていけば解ける問題なので，こういう問題の実装と解法ちゃんと詰める練習をしないとなあ．

DDCC2022本戦参加記

終了から2日も経過してしまい，詳細に書くような暇もないので，勝負のポイントとなったと考える点を手短にまとめる．普段の競プロとはかなり毛色の異なるコンテストで，実装時間が特に短く，トライ&エラーの機会も少ないので戦略をその場で詰めるようなことはしづらい．実機では思わぬ誤差によるズレも頻発するので，そういう意味でも偶発的な事象がかなり結果に影響するコンテストだと感じた．

実装すべき課題の難易度に比べて実装時間が非常に短く，事前準備が全くないと本番で何もできないということも考えられる．勝ちに行くなら最低限過去問に目を通しておくべきだろうと思う．

なんでこんな運ゲーを本気で振り返っているかと言うと，運ゲーの割に賞金がやたらと高額だからである

今回の分も含む過去問はこちらから確認できる．(もう本戦の問題も上げられているようで助かる)

ルール概要

• 昨年と同じように長方形の盤面の一辺の中央に取りつけられた発車口から球を発射して穴に入れる競技．
• 1つの穴につき10個までの球が有効な球とみなされる．
• 発射する球は70個まで．
• 連射の際の時間間隔は0.5s．
• 制限時間が50秒で，非常に短い．すべての穴をまともに10発ずつ狙うと時間が足りなくなる．
• 得点は(有効な球の個数)*(1個以上の球が入った穴の個数) である．1個以上球が入った穴を増やすべく様々な軌道で穴を狙うことが肝要である．
• 今回追加された要素は盤面に鎮座する3本の巨大なバー．しかも発射の向きを変えるたびに面倒なルールに従って向きが変わってしまう．どこを狙うにもこれが非常に邪魔である．バーの隙間を狙う，台の傾きを利用してバーを迂回する，バーの回転の向きを調整するなどの工夫が必要．

シミュレータ実装中に考えたこと

• まずは入出力を実装する．どう見てもx座標とy座標が逆の方が計算しやすいし，回転角はなぜか時計回りに与えられるし，とにかく意地悪な問題文である．DDCCの社員の方は普段から回転角を時計回りで表記されているのだろうか．
• ひとまずはバーのことなどは忘れて，台を傾けずに各穴に直線軌道で10発ずつ打ち込むコードを書く．入力が正しく受け取れているかのチェックでもある．シミュレータで260点を得る．5ケースあるので平均すると7個中2個程度の穴に収まっているようだ．少しほっとしたがこの時点で30分ほど経過していた．
• バーへの衝突や他の穴に落下することを防ぎつつ狙った穴に入れるには迂回するような処理が必要だ． シミュレータ実装時間中にこの実装が間に合うとは思えなかったが，装置実装では必ず使う処理なので少しでも書き進めるようにした．また発車方向の傾きはどうせ計算できないので，左右方向の傾きだけを実装することにした．
• 台の各支点の高さと発車角度とx座標(問題文におけるy座標．自分のコードではここを逆にしている)を引数にとり，そこでの球でのy座標を返す関数を書いたあたりでシミュレータ実装が終了．熱烈準備勢はたぶんこの辺まで事前にやってたんだろうなあ．

会社説明を聞きながらこのあとの実装を頭で考える．デカすぎるバーのよけ方をどうしようか…

装置実装 (前半)

• 実装方針が固まってくる．
  • 手前の穴から狙う．
  • ランダムに台の傾きを決め．二分探索で発車角度を決める．
  • 狙った穴に落ちる前に他の穴に落ちたりバーにぶつかったりしたら探索をやり直す．
  • バーの角度の調整はいったん諦めて，常に真横を向いていると想定することにした．
• 終了20秒前くらいにバグが除去できて，ギリギリ提出完了．シミュレータは10点を返していた．

実機観察

• この時点では，他の人はあまり台を傾けずに直線で狙っていた気がする．みんな手前のバーで弾かれていた．手前の穴に40発くらい入れていた人もいた．
• 初手で一番奥の穴を直線で狙って入れていた人がいて，これを自分も真似することにした．
• 自分の番について．
  • バーにぶつかりまくって散々だったが，まぐれで5個の穴に入った．これは意外と適当に傾ければチャンスがあるのではないかと思った．
  • 110点を得て中間順位は4位となった．
  • 軌道の計算がうまく行っているように見えた部分があり，手ごたえを得た(ただし，後から見返すとこれは勘違いだった．どのタイミングでどの穴を狙うのかを把握しながら観察すべきだったと反省している)．
• シミュレータ15位以降の人はそもそもまだまともなコードが完成していなさそうな人も多かった．このあたりから他の人の観察をやめて自分の録画を見返しまくって残りの30分で書くべきことを頭で考え続けていた．

装置実装(後半)

• 穴を狙う順番や探索を打ち切るかどうかの判定をより洗練させた．バグをいくつか直した．あまり覚えていないけど，優勝できるかもと思いながら書いた．
• 一番奥だけでなく右側の穴も直線で狙うつもりだったが，なぜかシミュレータ上でうまくいかなかったので仕方なく放物線を探索する方針に切り替えた．
• 2番目の穴はどういう軌道でも入らなかったので最後の10発は適当に打つことにした．

本番

• 直線で狙った奥の穴に10発中2発しか入らず真っ白になった．誤差大きすぎるやろ．それでも全部外れるよりはかなりマシだが．
• 放物軌道が若干ずれていることによる取りこぼしがかなりあった．中間実装のときに見逃していた点だったので，今見ると少しもったいない．
• バーの回避はかなり上手く，そのおかげでいくつかラッキーを拾うことができた．この点は上手かった．
• 結果は5位．あと4発入っていれば賞金圏内だったので最初の取りこぼしが悔やまれる…．
• 2番の穴には1~9位の人は1発も入れていなかった．やっぱあそこ入れるのって運に頼らないと無理なのでは？
• 多分最適は直線で狙える4つの穴に40発打ちこんでから中央の3つを台の傾きで狙うことだと思う．最初の40発で台を傾けないことにより，待機時間を0にすることができるのも大きい．また当然だが直線の方が実機特有の誤差は減る
• どうしても入らない2番の穴だが，球が転がっている最中に台を傾けるなどの戦略に賭けることになりそうだ．

次回への教訓

• 問題文にある角度や座標の記法(時計回りなど)に気をつける．単位も．
• コードはある程度準備してから行く．今回はたまたまうまく行った方だが，初見の問題だと本当に何もできずに負けることもありそう
• シミュレータの点数がどのくらい参考になるかは問題による．今回は直線軌道の確認くらいしか参考にならなかった．
• 他の参加者のお試し実装を観察してヒントを探る．
• 自分のお試し実装を眺める際にはどの動きが何を狙っているのかを把握しながら見る(良さげな動きをしていると，それが非想定のものであっても見逃しやすい)
• 誤差が少なそうな方針を考える．
• 幾何ライブラリを出しておく
• あとはお祈り

提出したコード

なんとなくライブラリ使って良いかどうかが気になって，珍しく<bits/stdc++.h>から書いてしまった．他の方は普通に自前の幾何ライブラリとか使ってたらしい．ちょっと損した．

#include <bits/stdc++.h>

using namespace std;
const double pi = acos(-1);
#define rep(i, n) for(int i = 0; i < int(n); i++)
using point = pair<double, double>;
void point_in(point& p) {
    double x, y;
    cin >> x >> y;
    p = make_pair(y, -x);
}

point convert_point(point& p) { return make_pair(p.second, -p.first); }

double distance(const point& p) { return sqrt(p.first * p.first + p.second * p.second); }

const double speed = 500;

double time_to_run(const point& p) { return distance(p) / speed; }

double arg(const point& p) { return atan2(p.second, p.first); }

int convert_to_theta(double angle) {
    double deg = angle * 180 / pi;
    return -int(deg * 1000);
}

// pi rad = 180 deg
// ang rad = 180 / pi * ang

double rad_to_deg(double radian) { return 180. / pi * radian; }
double deg_to_rad(double deg) { return 1. / 180. * pi * deg; }

bool range_chk(int value, int low, int high) { return low <= value && value <= high; }

int counter = 0;
void print_ans(int ch, int lh, int rh, int theta, int nu, int tm, bool is_end = false) {
    assert(range_chk(ch, -5000, 1000));
    assert(range_chk(lh, -25000, 25000));
    assert(range_chk(rh, -25000, 25000));
    assert(ch * 2 >= lh + rh);
    assert(range_chk(theta, -45000, 45000));
    assert(1 <= nu && nu <= 70);
    assert(range_chk(tm, 0, 60000));

    cout << ch << ',' << lh << ',' << rh << ',' << theta << ',' << nu << ',' << tm;
    if(is_end) cout << ';';
    cout << '\n';
    counter++;
}

// unit: mm, second

double theta_to_acceleration(double theta) { return 5. / 7. * sin(theta) * 9.8 * 1000; }
double acceleration_to_theta(double a) { return a * 7 / 5 / 9.8 / 1000; }

double calc_y(double x, double theta, double a) {
    const double time = x / (speed * cos(theta));
    const double vy = speed * sin(theta);
    return vy * time + a * pow(time, 2) / 2;
}

double calc_theta(double x, double y, double a) {
    double theta_max = pi / 4;
    double theta_min = -pi / 4;
    rep(i, 100) {
        double theta_mid = (theta_max + theta_min) / 2;
        if(calc_y(x, theta_mid, a) > y) {
            theta_max = theta_mid;
        } else {
            theta_min = theta_mid;
        }
    }
    return theta_max;
}

void solve() {
    counter = 0;
    const int n = 7;
    vector<point> holes(n);
    rep(i, n) { point_in(holes[i]); }
    sort(begin(holes), holes.end());
    const double bar_halflen = 100;
    point alpha, beta, gamma;
    point_in(alpha);
    point_in(beta);
    point_in(gamma);

    const double xmin = 0;
    const double xmax = 1000;
    const double ymin = -400;
    const double ymax = 400;

    int count_ball = 0;
    int time_remain = 100000;

    auto convert_bar_angle_to_my_plane = [&](double value) { return pi / 2 - rad_to_deg(value); };

    auto alpha_angle = [&]() -> double {
        int div_count = 0;
        for(int i = 1; i < count_ball; i++) {
            if(count_ball % i == 0) div_count++;
        }
        // return pi / 2 - rad_to_deg(double(div_count) * 30);
        return convert_bar_angle_to_my_plane(double(div_count * 30));
    };

    auto beta_angle = [&](double ch, double lh, double rh) { return convert_bar_angle_to_my_plane((ch + lh + rh) * 100); };

    auto gamma_angle = [&]() { return convert_bar_angle_to_my_plane(counter * 35); };

    auto in_range = [&](double a, double low, double high) { return low <= a && a < high; };

    auto calc_a = [](double lh, double rh) {
        const double sin_steep = (rh - lh) / 800;
        const double a = theta_to_acceleration(asin(sin_steep));
        return a;
    };

    const double hole_radius = 20;

    auto in = [&](double ch, double lh, double rh, double theta) -> int {
        int ret = -1;
        const double a = calc_a(lh, rh);
        rep(i, n) {
            const auto& hole = holes[i];
            double go_y = calc_y(hole.first, theta, a);
            if(in_range(go_y, hole.second - 20, hole.second + 20)) {
                ret = i;
                break;
            }
        }
        if(ret < 0) return ret;
        if(abs(alpha.second - calc_y(alpha.first, theta, a)) < bar_halflen) {
            return -1;
        }
        if(abs(beta.second - calc_y(beta.first, theta, a)) < bar_halflen) {
            return -1;
        }
        if(abs(gamma.second - calc_y(gamma.first, theta, a)) < bar_halflen) {
            return -1;
        }
        return ret;
    };

    const double theta_max = rad_to_deg(pi / 4);

    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    swap(order[0], order[1]);
    order = {
        6, 0, 5, 3, 2, 4, 1,
    };

    for(int i = 0; i < n; i++) {
        const int id = order[i];
        const auto& hole = holes[id];
        // cerr << id << ' ' << hole.first << ' ' << hole.second << '\n';
        int ch_miq = 0;
        int lh_miq = 0;
        int rh_miq = 0;
        double theta = arg(hole);
        if(theta > theta_max) {
            theta = theta_max;
        } else if(theta < -theta_max) {
            theta = -theta_max;
        }

        int nu = 10;
        int tm = (hole.first) / (speed * cos(theta)) * 1000 + 10;
        if(i < 2) {
            ch_miq = int(rad_to_deg(pi / 2 - theta) * 10 / 3);
            lh_miq = ch_miq;
            rh_miq = ch_miq;
        } else {
            rep(loop, 100000) {
                ch_miq = rand() % 1500 - 1000;
                lh_miq = rand() % 40000 - 20000;
                rh_miq = ch_miq * 2 - lh_miq;
                double ch = double(ch_miq) / 1000.;
                double lh = double(lh_miq) / 1000.;
                double rh = double(rh_miq) / 1000.;
                double a = calc_a(lh, rh);
                // debug(ch, lh, rh, a);
                theta = calc_theta(hole.first, hole.second, a);
                // debug(theta);
                if(abs(theta) < theta_max) {
                    if(in(ch, lh, rh, theta) == id) {
                        break;
                    }
                }
                // ch_miq = 0;
                // lh_miq = 0;
                // rh_miq = 0;
                // theta = arg(hole);
                // if(theta > theta_max) {
                //     theta = theta_max;
                // } else if(theta < -theta_max) {
                //     theta = -theta_max;
                // }
            }
            tm /= 2;
        }

        print_ans(ch_miq, lh_miq, rh_miq, convert_to_theta(theta), nu, tm, i == n - 1);
        count_ball += nu;
        time_remain -= tm;
    }
}

int main() { solve(); }

提出した解答

235,235,235,-19358,10,1970
300,300,300,0,10,410
-164,-13495,13167,29837,10,930
-566,10364,-11496,-28749,10,623
79,13976,-13818,6875,10,655
-990,19857,-21837,-35769,10,655
-344,-7294,6606,7039,10,505;

感想

普段書いているコードは実機で動いたりしないので，新鮮で思いの外楽しい経験だった．マラソンは経験がほとんどなくて下手なので5位だったのは想定よりかなり良かったが，入賞できなかった悔しさが残った．来年は今年の経験を生かして勝てればと思う．

ICPC2022国内予選・Kite_kuma(チームSPJ)視点

無念の11位敗退から1年．今年こそは，である．

チームメンバー

nok0

AtCoder: nok0 (橙)

Codeforces: nok0 (薄赤)

東大工学部物理工学科3年．アカウント名はノックゼロと読む(嘘)．タイピングがチームで最も速く，主に重実装問題を担当する．最近だとABCやARC140のwriterをやっていたりして，3人の中では一番名前が知られてそう．最近デスクトップPCを購入し，競プロ全力なのかと思いきやよくAp〇xをやっているところをDiscordで目撃されている．3年になってからは大学で物理学の実験を楽しそうにやっている．

zkou

AtCoder: zkou (黄色, max: 橙)

Codeforces: zkou (薄橙)

東大工学部計数工学科3年．アカウント名はズコウと読む(嘘)．チーム内で唯一メイン使用言語がPython．最近はC++で書くのも頑張ってるけどまだ不慣れな様子．もともとあまり実装しない立ち位置だったが，最近の作戦会議の結果全く実装をしないことになった．この人とつちのこが協力して数え上げをやると仕事が本当に速い．学業ド真面目勢．閃き一発の構築問題がかなり得意だがICPCにあまり出ないのが辛いところ．しかし…？

クマー

AtCoder: Kite_kuma (橙)

Codeforces: Kite_kuma (薄赤)

東大工学部計数工学科3年．アカウント名はキテクマと読む(嘘)．筆者．Kita_masa氏とはアカウント名が似ているだけで特に関係はない．3人の中で最もAtCoderのレートが高く，かつコンテストの爆死が最も少ないので一応安定枠っぽい感じの人．構文解析と幾何を担当する．幾何の実装時にぼっちになりがち．日本語を読むのが苦手なので(?)ICPCの難読問題はあまり好きじゃなかったりする．実装速度は普通~ちょっと遅いくらい？学業はゆるふわ勢．

記録

2週間前あたりからずっとICPCのことを考えていて，眠れなかったり授業やレポートに集中できなかったりしていた．特に今週後半は特にひどく，ほとんど全ての授業が上の空だった気がする．

当日．体力温存のために昼まで寝てから家を出た．大学に着いて，3限が上の空になりながらリハーサルを済ませた．今年の鎖中経路チャレンジは20分くらい．これやっぱ実装難易度がほどほどでいい幾何問題だよな．こういうの本番でももっとくれ．ここで昼食をとっていないことに気付く．3限が終わり，事前に借りておいた部屋に移動した後，パンとおにぎりを買いに行って食べた．これが15時すぎくらい．競技開始が16時半だから，腹が満たされて眠くなったりしたり嫌だなとか思ったりもしたが，腹が減ると全く集中できない人間なので仕方なく食べた．

本番前最後の作戦会議をした．自分たちより格上っぽいチームを列挙したら10チーム以上あって普通にげんなりした．(へのさんいつまでいるんですか？)特に今年の東大は層が厚くて，模擬国内で東大内順位が5位以内のチーム(我々は東大内6位だった)との争いが苛烈になることは必至に見えた．冷静に状況を書き出してみると少し自信が減退して，通過率は3割くらいかなーと思い始めた．具体的なチームの動きを確認した後にちょっと横になったりしながら開始を待った．

16時30分．どうせ今年もサイトが落ちるんだろうな…と思って完全にそのつもりでリロードしたら，なんと普通にトップページが表示されている．逆に面食らってしまった．今年からサーバー強化したとかならそう言ってくれよ(逆ギレ)．予定通りnok0がA，私がB，zkouがCを見る．ババ抜きのシミュレートで，もう見るからにめんどくさい．もう少し易しい日本語で書いてほしいと思った*1．計算量がO(N²)で収まっているのかが少し怪しい愚直が思いついた*2．このあたりでつちのこが慎重にAを通してCでzkouと合流していた．Bの計算量だが，3乗になっていたとしても で定数倍も軽く，国内予選ルールならさっさと回すのが早いと思ったのでその方針で書き始める．Cも2人の会話を聞く限りほとんど出来ていそうだ．私はBの実装を続ける．B問題だし大した実装量ではないが，ペナを生みそうでかなり緊張した．しょうもないミスを挟みながらもなんとか15分くらいで通した．さすがにCは2人で十分と言われてDに行く．日本のICPCでがに使われたことに驚きつつ*3，今年審判団に入ったDEGwerさんのことを思い出す．解法の方はというとすぐには分からなかった．考えているうちに2人が合流して，順位表がCで固まっていることからも，このD問題で早くも3人投入することが良いということになった*4．色々具体例を試して考えてみる．を前から見ていくと，区切りを入れなければいけない場所，区切りを入れては行けない場所が分かる．この情報はどうせ使うのでつちのこにその判定を書いてもらう．ではそれ以外の場所は任意に区切りを入れて構わないのだろうか？zkouと話す間に，それが正しいことが分かった．ここまでくればO(N²)のDPは自明だ．実装も簡単なので，nok0とzkouにEに行ってもらって私はDの実装を始める． 制約がN<=10⁴で50ケースくらいあったので20秒くらい待った*5．ヒヤヒヤしながらも一発でAC．このとき開始から1時間弱であった．順位表を見たら一応暫定圏内だった気がする*6．順位表を見るとほとんどが4完以下で，2人はEで苦戦していそうだったので，私も合流することにした．問題を把握して，あまりにもAtCoderっぽい内容だったので笑ってしまった*7．やっぱりICPCの出題傾向かなり変わってないか？そんなことはどうでもよくて，解法に全く見当がつかないので困った．じわじわEとFのACが増えてくるうちに，Fに行った方が良いのでは？ということをnok0が言い始める．Gは幾何らしく，とりあえず簡単かどうか私が確認したほうが良いだろうということになる．10分ほどGを考えて，おおまかな方針は分かったものの，細部について詰められなかったし，実装で沼って結局4完止まりになってしまう未来が容易に想像できたので切り上げてEに戻った．しばらくしてzkouが，文字列AとBの先頭と末尾が全て0の場合は構築可能であることを示していた．しかし他のケースについては分からず，16通り場合分けをするのは困難であるように見えた．私とnok0はこの辺りでEに難色を示しており，Fに行っていた．zkouはEに残って考えていた．私とnok0がFでDPができるかもという話をしていたところ，zkouからEが解けたと言われる．えっ…？このときは40分以上全く進展がない状況だったので，藁にもすがる気持ちで解法を聞いた．確かに全てのケースが尽くされている．少し私が実装方針に注文を付けつつ，得られた解法は以下の通りだった．

• の末尾と先頭 に着目する．

  • このうち3つ以上が1であれば，構築不可能である．
  • のケースは構築不可能である．
  • のケースは左上をで埋めて，中央で市松模様を作ったりすると構築可能である．
  • のケースは上手く対称性を使用することで上のケースに帰着される．
  • それ以外のケース，すなわちのケースは，上と同じように頑張ると構築可能である*8．

理屈は難しくはないが，書く量が多いので添え字の1つでもずれたら修正に時間がかかる．時間がないので急ぎつつも，ペナは絶対に出せないので正確に慎重に書くしかない．この時点で残りは1時間強くらいしかなかった．VSCode Live Shareで3人で共有し，私が上記の場合分けの前半部分を，nok0が後半部分を，zkouが全体のコードの監督をするという3人同時実装を行う．zkouには大量に書き間違いを指摘されたし，理解があやふやな部分を教えてもらったりもしていた．nok0は実装が速くて，一瞬で自分のパートを終わらせていた．私ももたつきながら実装を終わらせて，サンプルを試す．RE．え，そんなことある…？と不思議に思っていたら最初の入力順序を間違えていることに気付く．この土壇場であまりにもしょうもないミスの修正に1~2分使ってしまった…．修正してサンプルを試すと，合わない．nok0の実装した部分が少し間違っていたようだ．nok0が直している間に，私は自分が書いた部分に誤りがないかもう一度確認する．抜けがあることをzkouに指摘されて，少し加筆する．nok0の修正も終わり，サンプルが合うことを目視で確認する．しかしサンプルが弱いため，私の実装した部分をチェックできるケースが入っていない．ペナは絶対に出せないので適当にケースを追加して試してみる．見えている範囲では正しく動いているようだ．緊張で高鳴る胸の鼓動を感じながら入力ファイルをダウンロードし，submitする．AC．興奮で少し叫んだ．nok0とzkouはここで順位表を見ていたが，私の動揺を避けるために私には何位か伝えないでいてくれた．冷静に残りを見ると30分強．ここまでノーペナで通し切ったのは大きいが，すでにDのACから90分が経っており，リードが守れているかかなり怪しい．高い確率でもう1問必要だろうと思った．解法が詰められるか不明だが実装量が並程度かもしれないFと，解法はほぼ分かっているが並列実装がしづらく，実装が重いG，そして全く手を付けていないHからの選択．Gのほうがマシだと私が言って，3人でGに行くことになった．しかし心の中ではこの残り時間で通せたら運が良すぎるとも思っていた*9．Gでやるべきことは単純で，2点の位置のペアを状態として持って適当に探索すればよい．幾何は他の2人が全くやらないので私1人の実装だったが，あまりの焦りから簡単な添え字ミスを2人に大量に指摘された．実装が一応終わって，サンプルを実行したらREになったり，答えが全部0になったりなどを繰り返しているうちに，zkouから冷静に終了を告げられて，コンテストは終わった．

Gが通せなかったことの不甲斐なさと，通過しているか分からないことによる不安でいっぱいになりながら順位表を開けた．

気付いたら叫び声を上げて，nok0と大はしゃぎながら喜びを分かち合っていた．Eの大部分を考えてくれた天才が，普段は声がでかいくせに，俺たちを見て静かに嬉しそうにしているのが印象的だった．5完最速なので，結果的には序盤のリードは守れていたようだ．

片付けたあとは渋谷でThe Raspberry Candiesの方々，DELIAIRのお二人，noimiさん，seguramuの人たちと喋った．ネット上だと分からないチームの結成秘話とか他のチームメイトの珍エピソードとかを聞かせてもらってすごく楽しかった．同じ趣味を通じて得る同志は本当にいいものだなと思う．

終電1本前で帰宅したら寮で先輩が祝ってくれて，そのまま先輩と朝5時半までドミニオンで遊んでから寝た．

---

というわけで悲願の通過となった．昨年がひどい落ち込み方をしていたのもあって，お祝いの言葉をたくさん頂いた．アジア地区までにもっと強くなって，東大代表争いに食い込めるようにしたい．

*1:今見るとこの内容を簡潔かつ厳密に書くのは無理なので仕方なさそうである

*2:今冷静に見たら普通に2乗だった．冷静じゃなさすぎる

*3:たぶん今回が初めてだと思っているが，直近2年のアジア地区の問題を見ていないのでそこでは登場しているかもしれない

*4:これは今振り返っても好判断だった

*5:あとからDPではなくて普通に二項係数の和を計算するだけでであると聞き，当時は本当に緊張していたんだなと思ったりした

*6:5位とか7位とか8位とか，1桁の順位をいくつか見た記憶があるのだが，どれを通した時点で何位だったかは正直全く覚えていない

*7:今見るとコドフォの方がこういう問題が出そう

*8:ここを私は実装していないので詳細が良く分かっていない

*9:あとから聞いたらFの考察も割と惜しいところまで行っていたのでFの方が良かったのかもしれない．解くべき問題の選択はいつだって難しい

3/12 ABC243 感想

たまには情報量ほぼゼロの短い記事でも．

問題一覧:

Tasks - AtCoder Beginner Contest 243

* A

A問題だからと1日しかないと思い込んで，じゃあ3人風呂入った後でシャンプー使い切らなかったら何を出力すればいいんだよって言ってた．ってかこれAなのマジ？本当に新規参入者いなくなりますよ．

* C

y -> xの順でソートして隣の2項を見る実装が楽だね．

* D

stackで2進整数を管理，なるほど…

自分はオーバーフローしそうなときにどの頂点から何回子の方向に移動したかだけ管理するようにしてた．まあ大体なんでもできる．

* E

これ自明だと思うんだけどTL見ると普通に悩んだって言ってる人いてそーなんだーってなった．たぶん前にこういうことを自分で考えたことがあって，それでほとんど思考が発生しなかったんだろうと思う．

* F

包除やりたくなるだろこんなん．50だからどうせ全部持つDP．40とかにされたら半分全列挙とか色々迷い始めたかもしれない．40だったとして，実はそういう感じの解法で解けたりしますか…？(あまり深く考えずに書いている)

* G

悩んだ．これEより簡単とか言ってる人いたけどそんなわけないだろって思ってる．せっかくならクエリO(1)要求すればいいのに，って個人的には思うが準備した人は蛇足だと思ったんだろうな(クエリO(1)の処理を書いたので負け惜しみを言っている)．

sqrt_floorをあらかじめ準備しておくか若干迷う．k乗根まで対応しておけばそれなりに仕事をするかもしれない．

* H

最小カットの数え上げとかできるわけねえだろ！！！ってみんな叫んだと思う．少なくとも俺は叫んだ．解説見たら宇宙だった．あの，これ通しとかないとダメ…？

* 全体

Gで時間使ったのはもったいなかったがそれまでの立ち回りは理想的で，24位という好順位だった．一方ABCで賞金稼ぎをするためにはもう少し上まで手が伸びるようになりたいところでもある．

模擬地区予選2021・チームSPJ視点

昨年11月に行われた2021年度ICPC国内予選から4か月が経った．あの日までチームとしても私個人としてもそれなりの量の準備をしていたため，敗北という事実は重く私の頭にのしかかった．あの日から2週間くらいは毎日敗北のことを思い返してはひどい喪失感に駆られていたし，今も月に1度以上はこのことで最悪の気分に陥る．私はこういうことをいつまでも引きずる人間である．

あの頃の自分達には何が足りなかったんだろう．ずっとそれを考えている．きっと運は足りなかった．運があれば行けるくらいの状況だったから．でももっと強ければそれでも行けたはずだった．今回はあの時以来のチーム戦だから，何か糸口が掴めるかもしれない．そんなことを考えながら模擬地区予選に参加した．

チーム名: SPJ

メンバー: クマー(Kite_kuma), zkou(zkou), つちのこ(nok0)

開始．つちのこが昨夜インドコンに出ていたことによって少し眠そうだった．問題が難易度順かどうか自信がないのでとりあえずつちのこがA，zkouがB，私がCを読み始める．Cがそんなに自明じゃなさそう．Bを見てzkouがASCII Expressionじゃんと叫んでいる．Aが通る．

Bを確認．ASCII Expressionの苦い記憶が蘇ってｳｯとなる．BCの難易度的に恐らく難易度順じゃないなーとなる．こういうときはいつも私が最後の問題から読み始めるようにしている．K問題を読んだ．同じような幾何の問題を以前に解いた気がしてきた．そうこうしているうちにBが続々と通される．特にThe atamaが8分で通していては？となる．冷静に見るとかなり単純な再帰降下で構文解析が行えるようだ．構文解析担当のzkouが書き始める．同じくらいのときにつちのこが易問のHを見つけて実装を始めた．

私はK問題に戻る．やはり既視感がある．この記事を書いているときに調べたが，感染時刻の復元以外は以前私が解いたEarth Observation with a Mobile Robot Teamの下位問題であるようだ．時刻の復元もアルゴリズムの中で自然に行えることなので，上に挙げた問題とほぼ同じ問題だが，それで実装をグダらせた苦い記憶が蘇って書くのを躊躇した．そもそもまだAしか通していないし，もっと自明な問題を見つけにいくべきだろうということで，discordにメモだけしてJを読み始めた．

J問題．なもりグラフの同型性判定．ループが1つだけあるから，各部分木についてハッシュを作ればよい．根付き木のハッシュは以前にこの問題で作ったことがある．各頂点 について，子の結果をマージして の結果を得るのだが，その際に子のハッシュ値をソートするようにすれば，マージに非可換な演算を用いることができるようになり，適当なハッシュ関数でも壊れにくくなる気がする．未検証だが．この方法はソートにより計算量に がついてしまうが，今回の入力の大きさなら問題ない．

ハッシュ関数を書いているうちにつちのこがH，zkouがBをそれぞれ通した．特にHはFAだった．運よく易問が早く見つかったのはあったが，チームで使用しているSCCのライブラリが縮約後のDAGを返す仕様になっていたことも地味に生きた．atcoder/scc はトポロジカルソートしかしてくれないので，少しだが時間の節約になっている．

国内予選の全方位木DPの問題についても思ったことだが，ライブラリの少しの工夫でミスの量や実装時間が抑えられたりするので，本番までにこういった部分についての整備も行っておきたい．もちろんそれを活かすためには，本番直前にはチーム全員で各ライブラリの仕様を確認する作業も必須だ．

Jのハッシュ関数が書き終わりそうになって，2つの数列をrotateして一致させられるかどうかの判定方法を考え始めた．ローリングハッシュがまず浮かんだが，正直1つの問題でハッシュを2回も使うのはなあ…みたいな気持ちになって少し嫌な気持ちになる．この抵抗感は以前に下のリンクの記事を読んだことも関係していた．

数列比較のRolling Hashは危険だよという話 - yukinote

そこで2人にいい方法がないか聞いてみると20秒ほどで「S+T+TでZ-algorithmやればいいよ！」と返ってきた．理解に10秒ほどの時間がかかったが，分かってしまえばあまりに手際の良い実装方針で感心した．サンプルも提出も一発で通って，FA．

そういえばコンテスト後に計算量 の根付き木の同型判定の決定的アルゴリズムを学んだ．まだ実装はしていないので，今後のライブラリ整備の課題としておく．ハッシュを使用しなければいけない今回のような問題もあるので，衝突確率の上界がある程度保証された根付き木のハッシュも作っておくことにしよう．

私がJを書いている間にIが書かれていて，JのACの2分後にこちらもAC．ここですぐできそうな問題が尽きて，順位表を見つつ各問題を見渡す段階に入った．確かこの時点では我々は2~5位くらいで，他チームが通している問題で我々が通していない問題はC，Gくらいだったと思う．

私が一番通されているGについて考えていたら，つちのこがCに興味を示し始めた．置換を制約とした最適化をしなければならないこと，制約が小さいことなどからフローであることは簡単に見当がついたので，どうせフローだよとだけ言っておいた．

私はGに戻る．10分ほど考えていたら隣接する2項をswapしたときのを影響が簡単に表せることに気付いて，そこからは早かった．最適化の典型的な手法なのでこれはもう少し早く思いつくべきだったとやや反省している．

つちのこがC，zkouがDをやっている間に，やれば絶対にできる問題であるK問題の存在を思い出し，私はそれの実装を始めた．SPJで幾何ライブラリの全貌をまともに把握している人間はたぶん私だけなので，幾何は私がやるしかない．先ほどこの問題はほぼ既出であると書いたが，人の軌道が直線なので過去問よりさらにやりやすくなっている．The atamaが38分でこれを通していたのには驚いたが，きっとokuraさんが経験を生かしてサッと書いたんだろうなと勝手に推測していた．

書いてみたら案外すぐ書けた．いつも思うが私は実装時間の見積もりが下手だ．誤差が若干怖かったものの，投げたらAC．チームメイトにはめっちゃ褒めてもらえた．やったぜ．正直そんなに大変じゃなかったけど．

1ペナを計上していたCも通り，これで8完となった．なんかよく知らないけどフローだったらしい．残るはDEF．

Dは面白そうな問題で，できそうな雰囲気があるもの，明確な方針は私にはよく分からなかった．Eが幾何だと聞いたのでとりあえずそっちを見ることにした．

Eを見る．多角形が凸なら円の存在領域は簡単な線形不等式で表せるので，計算が非常に楽になることに思い至る．…多角形が凸であるという制約がどこかにないか，目を皿のようにして探したが，特にそんな制約はなかった．

さて凸でないとなるとかなり大変である．当初は多角形を構成する各線分に対して円の中心の存在範囲がどのように制限されるかを書こうとしたが，やはり凸でないという制約が非常に邪魔だ．また が許容されるなら境界の点を全探索すれば円の中心が存在する区間が分かるが，今回の制約はそれを認めていない．その後も凸包を取ってみたりするなど思考は迷走を重ねた．色々考えた末にとりあえず円が内部に収まることと同値な条件が分かった気がしたので書き始めた．

私が幾何に悶絶している間，残りの2人はDの平方分割解を何とか高速化しようとしていた．いっぱいバグって大変そうだった．ペナも何回か出ていたが，結局2ペナACで助かったらしい．私はEはもういいと言ったので2人はFに行っていた．

ここでEの実装が複雑すぎて心が折れかかった．そもそも当初うまく書けたと思った条件が本当に正しいのか自信がなくなってきた．このままではまずいので，2人に現在の状況を共有しつつ実装を考え続けた．色々考えた結果，結局直線上を走査できることに気付いてなんとかACの目途が立った．30分ほどかけて書いて，AC．円を少しだけ小さくすると誤差落ちしづらくなることをzkouに教わったこと以外は全部自力だった．

私もFに加わった．区間Affine区間maxsumみたいな操作が必要っぽい．有志コンっていつもこういうわけ分からんクエリ問題が最後に残ってうちのチームが困ってる気がする．平方分割をまともに書けるようになるのも今後の課題だなあ，とか思いながらおやつを食べてたらコンテストが終わった．

結局AHBJIGKCDEの順で10完4位となった．

解いた問題のうちHJEの3問がFAで，これは全チームの中で最も多かった．難易度順でないセットでFAを取ることは運の要素も絡むし，的外れな順番で問題を解いた結果FAを得てしまうこともあるので，FA数の多さは戦略が優れていることの証左とはならないが，各問題で大きく出遅れることもなかったのでやはり結果としては上々だったと考えている．

コンテスト後に問題を振り返った感想．Cはフローを使うことはすぐ分かったが，愚直に辞書順最適を調べようとすると かかってしまい，そこからの進展が私1人では得られなかった．解説のように大きい定数を使うと複数要素の優先順位を定めることができるというのは1つの発見だった．まだまだネットワークフロー周りは練度が不足している部分が多いようだ．

Dでつちのことzkouがやった平方分割は頭いいし，解説の方針はもっと頭いいなって思った．こういう遅延処理みたいなの最近やってなくて全然思い浮かばなかった．

Fは今後の課題．こういうのを気合で通す経験がうちのチームの人間には足りてないのだろうと思う．二項間の差が定数以下だと分かっている場合に平方分割と相性が良い可能性があることが分かったのは1つの収穫ではある．

今回は練習試合だし，結果だけ見て国内4位だなどとそのまま素直に喜ぶわけにはいかないが，それでも確かな手ごたえを感じた．国内予選の時と比べても，我々は確かに強くなっている．FAを3つ取ったことで，順位表に頼らなくとも自分たちの実力で解くべき問題を見極められるのだという自信を得た．

あの頃の自分達には何が足りなかったんだろう．ずっとそれを考えている．きっとこれからも，競プロをやめるまではずっと．