TOUPC001に参加してきた

はじめに

2025-04-26に東京通信大学プログラミングコンテスト（TOUPC）というオンサイトコンテストがあったので、参加してきました。

イベントのページは こちら コンテストのページは こちら

もろもろのこと

今回のコンテストは

• 低難易度問題が多数含まれていてガチ勢以外もウェルカム
• 主催のuruzunyaaさんとmanabeaiさんに面識がある
• 近い
• いろいろと予定が合った

などの理由により行くことにしました。 やっぱり問題解けないとオンサイト行っても言うほど面白くないよねという正直な気持ちがある。

会場は国立オリンピック記念青少年総合センターという場所でした。場所的には新宿の近くです。 私は京王線で向かったのですが、京王初台という多分今後行くことのない駅が最寄りでした。

前日は早く寝よう早く寝ようと思って9時くらいに寝たら午前3時にすんごい目が覚めてしまい、そこからほとんど眠れなかったためすごく微妙な体調で臨みました。睡眠とかいうの本当にバカらしいですよね。生物の欠陥のひとつといっても過言じゃないと思う。

12時くらいに初台に到着して、お昼にカレーを食べました。

ターリー屋 というチェーン店らしいんですが、思ったよりいっぱい出てきて食べるの大変でした。これから3時間集中しようって時に何してるんでしょうか。 あと食べてるときお店に私しかいなかったんですがなんだったのでしょうか。（お昼時ではないのか？） いずれにしろ、体調がアレな時にドカ食いするのはやめましょう。（至言）

会場は建物の4階でした。

思ったよりも早く到着してしまい、運営の方を除いて3番乗りだったみたいです。 受付でゴリちゃんさんと間違われそうになったんですがなんだったんでしょうかあれは？

久しぶりにuruzunyaaさん、manabeaiさんと会いしましたが、変わりない様子でした。（情報量0すぎ！？）

TOUPCぼちぼち頑張りマス
若干眠くて参った😴

— In (@UU9782wsEdANDhp) April 26, 2025

これスカして若干とか言ってますけど結構ガチで眠くて焦ってました。

コンテスト

実は一週間ほど前にtwitter（鋼の意思）で DP学ぶマン さんからチームどうですかと声をかけていただいていたので、当日はteam_bloomとして2人チームで出ました。（余談なのですが、僕のInTheBloomというハンドルはどちらかというとInの方が本体なのです。名字だけ取ったみたいな気持ちですが、こっちのほうがかっこいいから結果オーライですね。） 僕が1600くらい、学ぶマンさんが1400くらいなので普通のオンサイトだと組めるかどうかギリギリのラインでしたがTOUPCは優しいので余裕でした。（なんならもう一人入れることもできた。）

言語何を使うか迷っていたんですが、なんとAOJのジャッジが2025年3月あたりにアップデートが入っており、D言語のほぼ最新バージョンが使えるようになっていました。神すぎる。 というわけで僕がD言語、DP学ぶマンさんがpython3という異色の構成で挑みました。

コンテスト開始

ここからは常体のほうがよさげだったので常体でいきます。

とりあえず先頭4問が簡単らしいので分担することに。僕がBD、DP学ぶマンさんがACを担当。

開始1分でDP学ぶマンさんがAをAC。さすがに早い。 僕はBを読む。 よくあるbool2つで出力を分岐するやつ。適当に場合分けしてACを獲得。 まもなくDP学ぶマンさんがCをAC。

Dを読む。結構難しそうに見える。dpするにしても状態が大きすぎて無理なので、多分何らかの貪欲戦略があるのだろう。 少し後に条件を「$k$個連続しない」に言い換えると連続部分を潰していくのが最適になりそうだとわかる。「自明な下界を達成できて～」のパターンだった。何回見てもこれ系は慣れない。9分時点でAC。

ここからは解けそうなやつを探していく。DP学ぶマンさんがFを考察。僕はMとNを見て様子をうかがう。

Nは$O(N \log N)$すら通らない制約だし、順列を決めていくのなんてどうせろくな方法がないだろうというメタ読みをしてARC的算数を考える。が、一向に見えない。一旦Mに行く。（あとで気づいたのだが、この時の方針はかなり正しかったらしい。2を置くときにすでに決定した奴と隣接させないといけないというのをなぜか見落としていたらしい。）

Mは明らかな$\Omega (2^{HW})$解法が見える。が、これ以上はかなり厳しそう。 例えばパスの方を固定して盤面を数え上げるとなっても重複の解消をしないといけない。dpとか難しい包除とかをやる問題に見える。

一旦諦めてIを見に行く。いつもの連結になったら消していくやつ（消してはじめて連結になるやつもあるよ！）だった。これ系はstackだと相場が決まっているのでその線で考える。普通に同じ色がたくさん並んでいるのを見たりすると死ぬが、何個連続しているかを持っておけばいつものカッコ列のやつみたいにできる。 最適性についてはそこまで考えていないが、取る順番を変えて状況が変わるような例も思いつかなかったので投げた。開始35分でAC。

ここでDP学ぶマンさんがFを詰め切れないということだったのでバトンタッチ。DP学ぶマンさんはGの考察へ。 うまいこと照らされているマスを数え上げることも考えたが、複数ライトに照らされている部分の処理が非自明に感じたので一旦スルー。どう考えても暗いところを数える方が楽そう。

結論から言うと、いつもの等差数列の総和になる。右端と左端のマリオのゴール前階段みたいなやつは別途処理するとして、そうでない場所の暗闇を考える。一番上の部分が長さ$A _ {i + 1} - A _ i - 1$で、そこから1段下るごとに$-2$されていく。何段になったら消滅するかはわかるので、合計何項足すのかは算数で求まる。 あとは適当に展開するといつもの$\sum _ {i = 1} ^ N i$の計算に帰着。これも結局算数ができて線形時間近くで解ける。 ただし、$A$の値が64bitぎりぎりなので多倍長整数を使わないと多分落ちる。適切に頑張れば64bitでもできそうだったけどそんなことをやるほどカツカツではなかった。 1時間6分時点でACを獲得。

Gはあまり見ていないが、開始1時間4分でDP学ぶマンさんがACを獲得してくれていた。

残りの問題はEHJKLMNだったが、明らかにAC数が少ない問題がちらほら。それらを避けて解けそうなやつを解いていく。

Hが解けそうだったので考察に入る。 互いに素な連続部分列をいくつかピックして得点を最大化する問題。かなりヤバいことをやっているように見える。 貪欲なわけがないのでdpを考察。 dpをするなら遷移一回につきひとつの連続部分列をガッと取ってしまいたいわけで（そうじゃない場合もあるけど今回は連続部分列のピックにも条件が課されているから今ピック中で～みたいな状態を入れると状態数が爆発する。）、そうするとdp[i]:=iまでの選択が済んでいて、最後にとった連続部分列の末尾がiであるような取り方の最大みたいなdpが自然に思いつく。

ここで連続部分列に対するテクニックが活きた。 こういうのは配るのではなく、変数分離してうまくデータ構造上で貰う形に直すのが典型だ。どういうことなのかというと、今回でいうと連続部分列$A[l], A[l + 1], \dots, A[r]$を選択できる条件というのは$\sum _ {i = l} ^ r B _ i \leq \sum _ {i = l} ^ r A _ i$である。これを変形して$0 \leq \sum _ {i = l} ^ r A _ i - B _ i$に持っていく。 ここからがキモで、あえてこれを累積和の形で書き直すのだ。 つまり、$A _ i - B _ i$の累積和を$D$としたとき、大体$0 \leq D _ r - D _ l$みたいな条件にまとまる。（off-by-oneは適当。） こうすることで、$r$側から見たとき区間の始まりがどこからだったかみたいな情報を全部無視して遷移先を選ぶことができるようになっている。 具体的には、各$l$たちはセグメント木などの$D _ l$の場所に値を積んでおくことによって、後ほど$r$側から見たときに条件を満たすやつだけを高速にピック出来るようになるということだ。

ピックしたときに得る利得がいくらか？というのを遷移に盛り込まないといけないが、これも同様の変数分離テクニックによって解決できる。$\sum _ {i = l} ^ r C _ i$の利得というのを考えるとき、あえて累積和を経由して$E _ r - E _ l$みたいな形にしておく。そして各$dp$値は値が確定してセグメント木に積み込むときにあえて$-E _ l$して積み込んでおく。こうすることで、$r$側から見たときにはmaxをピックして$E _ r$を足すだけで適切に更新ができるようになっている。まさにマジックだといえる。 というわけであとは適当に頑張ると1時間55分時点でACを獲得。

なんとHを解いている間にDP学ぶマンさんがKとN（N全然わからなかったので超ファインプレー！）を解いてくれていた。 Nは1を配置してからじっくり順列を観察できるかがカギだった。よく見るとそれ以降の数はほとんど置く場所に自由度がなく、せいぜい両端のどちら側に配置するかという2択を選び続けるという感じだったらしい。 Kはデバッグプリントのせいでペナっていたらしく、ウケた。

のこる可能枠はMしかないっぽいので再び向き合う。 いろいろ考えてみてもやっぱり到達不可能な盤面が生起する確率を考えるdpみたいなことをするんじゃないかと思う。よく考えると人は右と下にしか動けないのだから、人が動ける範囲の最新箇所がどうなってるのかがわかればそれに至るまでにどんな隕石の降り方をしたかは関係なさそう。 というわけでdp[i][S]:=上からi行目まで隕石の割り当てを決めて、到達可能場所がSになるような盤面が生起する確率というdpを組んだ。ここまで組んで、ようやく直接ゴールできる盤面の生起確率を考えてもよいということに気が付いた。

到達可能座標が1、不可能座標を0としたとき、初期状態では10000, 11000, 11100, …みたいなものだけを考える。 遷移は$\lbrace 1, 2, \dots W \rbrace$の任意の部分集合から任意の部分集合へを考える。 このdp定義は実は大ハズレ方針だった。想定解は「人がi回移動した際の」という定義だったため、行ごとに割り当てを決めるこのdpでは遷移可能かどうかの判定や、確定させないといけない隕石の決定にすごく手間取った。 例えばdp遷移が可能な座標集合かどうかを判定する関数possibleは以下のようになった。

bool possible (int X, int Y) {
    foreach (i; 0 .. W) {
        if (0 < (X & (1 << i)) && 0 < (Y & (1 << i))) {
            // Yの右側に連結なbitを全部消滅させる。
            int hi = i;
            while (hi < W) {
                if ((Y & (1 << hi)) == 0) {
                    break;
                }
                Y ^= 1 << hi;
                hi++;
            }
        }
    }

    return Y == 0;
}

これはdp[i][S]からdp[i + 1][T]が可能かどうかを判定するものだ。例えば

S: 1001001101
T: 0001110101

を考えたとき、S側とT側で両者立っているbitがあれば、Sから右下に動いてTの1のbitを出来るだけを潰すということをやっている。（この例は遷移可能。）

遷移可能がわかったら、次は各隕石について

1. 降らないといけない
2. 降ってはいけない
3. どちらでもよい

を判定することで遷移の係数を決定する必要がある。これもいくつかコネコネしないといけない。 最終的に以下のような関数を書いて32bitにその情報を詰め込むようにした。

Tuple!(int, int) check (int S, int T) {
    // T側で1は隕石が降らない。
    // T側で左にある1に隣接してる0は隕石が降る。
    // S側が1かつT側が0な場所は隕石が降る。
    // これで決まらないやつはどうでもいい。

    int fall = 0;
    int nofall = 0;
    foreach (j; 0 .. W) {
        if (0 < (T & (1 << j))) {
            nofall |= 1 << j;
        }
    }
    foreach (j; 0 .. W) {
        if ((T & (1 << j)) == 0) {
            if (j - 1 < W && 0 < (T & (1 << (j - 1)))) {
                fall |= 1 << j;
            }
        }
    }
    foreach (j; 0 .. W) {
        if (0 < (S & (1 << j)) && (T & (1 << j)) == 0) {
            fall |= 1 << j;
        }
    }
    return tuple(fall, nofall);
}

これらを丁寧に書いて出すとACを得ることができた。2時間54分時点だった。 途中で人が左に動けないことを忘れておりペナルティを食らった。（正直よく気づけたなと思う。）

11ACで全体18位だった。結局他の問題はほとんどACが出なかったため、かなり好成績を残せたと思う。

DP学ぶマンさんに大感謝(人’’▽｀)

TOUPC BDFHIMを解きました。祈って投げたやつ全部通る奇跡が起きてました。
運営の皆さんありがとうございました🙇‍♂️楽しかったです。

— In (@UU9782wsEdANDhp) April 26, 2025

無限人にいいねされてびっくり。

コンテスト終わった後

会場にはたくさん競プロ勢の方はいたんですが、いかんせん私がコミュ弱というのもありはじめましての人にたくさん声をかけに行く勇気もありませんでした。 今思うとけんちょんさんに話しかけてみたらよかったかもしれません。競技プログラミングをはじめたころqiitaやはてなブログなどですごくお世話になったので。（現在もお世話になり続けている。） でもけんちょんさんのまわりには強い競プロ勢がたくさんいそうで怖かったのでやめて正解だったかもしれない。

そんな時にcoindarwさんを発見したので、永遠にcoindarwさんに粘着していました。平衡二分木のmeldという概念を教えてもらってニコニコという感じでした。そろそろAVL木真面目に書こうかなと思います。 そのあとは新宿のサイゼリアに突撃して、10時前くらいに解散しました。 （ここで書くのはなんか卑怯な気もするんですが、もしよければまたご飯でもどうですか？僕は大体暇なので…）

11時前くらいに帰宅成功。驚くほど疲れていて、家に帰って上着を脱いでそのままおふとんに倒れこんでました。普段引きこもっているので少しアクティブに動くと後遺症がのこる…

翌日は午前中ずっと頭痛かったです。

昨日はしゃぎすぎて目と頭がやたらと痛い。体力つけたすぎる。

— In (@UU9782wsEdANDhp) April 27, 2025

なんか思ったこと全部ツイートしてるなコイツ！？

感謝

久しぶりにオンサイトコンテストに行きましたが、（難易度帯が僕にとってちょうどよかったというのもあり）とても楽しませてもらいました。 改めて、コンテスト企画、開催お疲れさまでした。

もし第二回があればまた行きたいです。