以下の内容はhttps://nononmath.hatenablog.com/entry/2025/05/01/232102より取得しました。

ACPC2025 参加記 & TUPC2024 開催記

ACPC2025 の参加記，兼 TUPC2024 の開催記です．

会津若松駅を庇い石にされてしまったあかべこ

去年の TUPC 開催記はこちらから:

nononmath.hatenablog.com

当日まで

今年の TUPC の開催を決めたのは去年の TUPC が終わった直後だったと思います．昨年とは異なり，自分がサー長になっていたので頑張らないとなぁとなりました．

スケージュールとしては昨年を参考に，国内予選が終わったくらいから本格的に動き出そうと思っていました．

すると，なんとビックリ！会津大がオンサイトコンテストを開催するという告知が出たのです．

昨年の感覚から，地方でのオンサイトは人が集まりにくいのでは？という気持ちがあったので，3 月に東北で 2 つもオンサイトがあると人が来なくなりそうです． 一人で考えてもどうしようもないので，その日のサークルで相談をし，会津大に共同開催を持ちかけることにしました．

会津大が快く引き受けてくださり共同開催が決定しました．

また，8 月の頭には会津大の方に行き，日程決めや会場の下見などをしました．ところで，この会場の下見には仮の人さんと在来線でゆっくりと行ったのですが，この間の会話で生まれた問題が今年の D 問題です．

それ以降は，基本的に問題準備をしていました．問題についての詳しい話は day2 のところに書きます．

そして，1 月の中旬に UCup 部分の問題を決めました（簡単枠はもう少し後でした）．その後は赤の tester に走ってもらったり簡単枠を完成させたり部内 tester に走ってもらったりしました．

部内 tester が青 2 人で簡単枠 300 点だったので，部分点を増やすことにしました．この時増えたのが C の 1 つ目と O の部分点です．コンテスト中に結構解かれていたので追加して良かったです．

後は問題文のチェックとか諸々をしていたらあっという間に ACPC 前日になってました．

day 1

ACPC の前後に実家で予定があったので実家の横浜から向かいました．新幹線は自由席でしたが，かなり空いていて快適でした．

お昼過ぎに会津若松駅に到着，そんなにお腹が空いていなかったのでコンビニでおにぎりと菓子パンを買って会場に向かいました．到着するとかなりの人がいてびっくりしました．

立命館大学からは 10 人以上が来てると聞き，これにもまたびっくり．部としてのシステム等が自分たちよりちゃんとしてそうで見習いたいなぁと思いました．

day1 コンテスト（立命館大学セット）

この日は kotatsugame さん，olphe さんとチーム kotatsugame_marunage で出場，クジで決まったチームでしたがチームに赤コーダーがいて緊張です．

特に難易度等の情報がなかったので自分が A から，olphe さんが E から，kotatsugame さんが L から読むことになりました．

コンテストが始まり A を読むと解けそうです．B を読むと強いデータ構造で殴れそうです．C は 3 乗まではすぐ分かります．チームメイトの実装 queue が空になってから A の実装を始めます．書きながら kotatsugame さんに B と C を共有，両方できそうだと言われます．

A でバグらせたので B を書いてもらい，A が通ったら C を書いてもらい，あっという間に 6 完です．

その後は D を考えます．N が小さいので列を全て見ることができ，各列はいい感じに区間に分かれるので境界が分かれば良さそうです．あとは olphe さんに実装を丸投げして AC を取ってもらいました．

残り時間は J と K を反復横跳びしながら椅子を温めていました．

結局 9 完で全体 4 位，オンサイト 2 位でした．

day1 コンテスト後

解説終了後は懇親を探してウロウロします．すると，駅前に集まると良いという情報が手に入ったので駅前に行きます．集まった人数が多かったのでいくつかのグループに分割することに，自分は kotatsugame さん，m_99 さん，んをさんと「桜莉紙」という居酒屋に行きました．

izakayaorigamiaizu.wixsite.com

店の雰囲気もよく，ご飯も美味しくて最高でした．特にソースカツ丼が美味しく，day2 以降もたくさん食べてました．

ご飯を食べたり，お話をしたり，kotatsugame さんの ABC を見守ったりしながら 23 時すぎまで店にいました．帰り道で kotatsugame さんが歩きながら div2 に出ていました．

自分はホテルについてそのままベッドに突き刺さっていました．

day2

この日は東北大セットです．自分は writer なのでドキドキとワクワクが半々くらいの気持ちで会場に向かいます．すると，用意された admin ルームのなんと広いことか．快適な順位表観戦が保証されていてワクワクです．

昨年まで司会をしていた milkcoffee さんがいないので自分が司会を引き受けることにしました．特に大きなトラブルなく進行できたのではないでしょうか（そもそも話すことが少ないので，それはそう）．

以降ネタバレ注意です．

問題の感想

writer/tester をした問題だけ書きます．

A - Inversion PQ and QP

tester とユーザー解説の執筆をしました．いきなりですがこのセットで一番好きな問題です．パズルっぽい構築に見えて，ゴリゴリの数学問なのがめちゃくちゃ好きです．

仮の人さんから問題概要を聞いた直前の週の群論の授業で共役類についてやっていたので驚きでした（実は去年の 012 Grid も問題を聞く直前に LGV 公式について勉強していたので，それも含めてびっくり）．群論パートの後の考察も実装もかなり大変だと思います． 実験をすると実は swap と 3-point-rotate しか使わなくて良さそうという部分をエスパー＆最大化が貪欲でできることが分かればあとは頑張るとなんとかなります．最後の復元も簡単じゃないと思います．自分は授業ノートとにらめっこしながら書きました．

仮の人さんがエスパーパート頑張って証明していたので（すごい）それの査読をしました．

本番は riano_ さんが解いていてびっくり（0AC になりそうだと思っていたので）．すごいですね...

D - Swap Counter

writer をしました．これは上にも書いた通り会津大学に行く途中の電車内で生まれた問題です．最初に考えたのは（辞書順最小とは限らない）構築でしたが，少し考えると次の 3 つが全て解けそうだとなりました（実際解けます）．

  • $ B $ が与えられるので $f(P) = B$ なる $ P $ を構築せよ
  • $ P $ が与えられるので $ f(P) $ を求めよ
  • $ B $ が与えられるので $f(P) = B$ なる $ P $ を数え上げよ

後日，丁寧に解説を書くと辞書順最小ができたので，問題セットとの兼ね合いでそれを出題することにしました．上手く書くと python 解が 20 行を切ってびっくり（https://atcoder.jp/contests/tupc2024/submissions/62430681）．

本番では全然解かれませんでしたがそんなに難しくないので是非 upsolve してみて下さい．

F - Another Long Sequence Inversion

writer をしました．原案は次のものでした．

$L \oplus X, (L + 1) \oplus X, \dots, R \oplus X$ のうち $ M $ の倍数はいくつですか（$R, X, M \lt 2^{60}$）

これだと XOR 区間の分割の知識すぎると言われたので転倒数に変更，さらにとりゐさんからクソデカ制約でも二進数出力でも解けると指摘を受けて今の形になりました． 解法自体は典型（らしい）ですが実装をちゃんと詰めるのが結構大変に感じました．

コンテスト中の提出が 0 で悲しいです．全然不可能じゃないので是非解いて下さい．

I - Small Steps

tester をしました．自分が原案を見たときは $K = 1$ のとき（ただの木についての問題）でした． ただ，直径 like なパスの隣接する葉の個数の階乗積で書けるのを出題したいなぁと提案，仮の人さんが考えた今の出題形式によってガッツリした数え上げになりました．場合分けが多くて大変な問題なのでマルチテスト＆部分点なしを提案しました．

これもコンテスト中の提出が 0 でしたがめちゃくちゃ面白いので是非解いて下さい．

L - Square Connection

writer をしました．最初は構築なし（長さのみ出力）だったのですが仮の人さんに一瞬で（構築込みで）解かれたので構築込みで出題しました．

また，原案段階では「無限グラフ上の最短経路を求めよ」という形だったのですが，ジャッジの都合で入ってしまう $u \leq 4 \times 10^{18}$ という制約を上手く問題文に入れるのが大変だったので今の形に変更しました．

M - Divide Digit String

tester をしました．$K = 1$ かどうかで全く違う問題になる＆どちらも非自明・それなりに大変な実装になっていてすごいなぁと思いました．こういう問題を作れるようになりたいですね．

順位表では想定以上に解かれていて，人々は強いなぁとなっていました．

day2 コンテスト後

この日はかっつさん，m_99 さん，sotanishy さん，とりゐさん，仮の人さん，E49869826 さん，ripity に自分を合わせた 8 人で「権兵衛」という居酒屋に行きました．

www.instagram.com

人生で初めて馬刺しを食べましたが，創造以上の美味しさで最高でした．その横についていた辛子味噌も最高の味です．また，この人数なのでみんなでいろんな日本酒を注文して飲み比べることが出来ました．個人的には「写楽」と「一生青春」が美味しかったです．

後は「にしんの山椒漬け」がとても日本酒に合い，最高でした．

店を出た時間が 21 時を過ぎていたので，ARC を諦め夜の観光に行くことにしました．sota さん，仮の人さんと鶴ヶ城の方まで歩きました．

day3

最終日です．名残惜しい気持ちになりながらホテルをチェックアウトし，会場に向かいます．お昼ご飯を食べる時間がなさそうなのでコンビニでおにぎりと菓子パンを買って向かいました．

day3 コンテスト（会津大学セット）

この日は kotatsugame さん，かっつさんとチーム kotatsugame_arigatou で出場，この日もクジで決まったチームでしたが再びチームに赤コーダーがいて緊張です．

この日は A, B が簡単であることが公開されていたのでかっつさんが A を，自分が B をやることにします．B を読むと制約がすごく小さいのでやれば良いです．が，カスの実装ミスで無限分溶かした上に 2 ペナをつけてしまい大反省です．

なんとか通した後は C を読みます．max の寄与を少なくしたいので端に置くと，問題が小さくなるので同じことを繰り返せば良いです．同じ値の部分に気をつけながら実装し，AC．その直後に kotatsugame さんが N の FA を取り順位表を破壊していました．

このあと少しすると順位表情報が無くなったので kotatsugame さんと相談しながら色々と考えます．赤コーダーの考察速度が早過ぎて置いていかれまくり...

結局開始 2 時間と少しで I, K を除いた 12 完になり，残りも考察は終えている感じになっていました．K は kotatsugame さんが受け持っていたのでかっつさんに「I の実装どうしますか？」と聞くと「実装バトルでしょ」と言われたのでバトルスタート．途中からは K を通した kotatsugame さんも合流し 3 人でバトルすることに．

1 番最初にサンプルがあったのは kotatsugame さんでしたが提出すると WA．続いてかっつさんも提出しますが WA に．最後にサンプルを合わせた私が提出すると，なんと AC．大逆転勝利でした．

コンテスト終了まで 1 時間ほど時間があったので学食でお昼ご飯を食べました．

結局他に全完は出ず，優勝することが出来ました．

day3 コンテスト後

m_99 さん，仮の人さんが会津駅前でお土産を買うというので付いて行きました．途中で ripity も合流し 4 人で駅前へ．その途中に「かついち」というとんかつ屋さんで再びソースカツ丼を食べました．

tabelog.com

お土産は駅ナカのお店へ．

www.livit.jregroup.ne.jp

にしんの山椒漬け，辛子味噌，日本酒（山廃純米　末廣）を買いました．

最後に

信じられないくらい楽しい 3 日間でした．欲を言えばもっとたくさんの人にオンサイトに来てもらいたかったですが...

今まで話したことない方と話したり，夜遅くまでお酒を飲んだり，観光に行ったりと今まで自分が行ったことのあるオンサイトではなかった経験がたくさんできてよかったです．来年もやりたい〜

準備期間からお世話になった会津大学・立命館大学の皆さん，オンサイトに来てくださった皆さん，コンテストに参加してくださった皆さん，本当にありがとうございました！！



以上の内容はhttps://nononmath.hatenablog.com/entry/2025/05/01/232102より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14