ARC216 / AGC077 開催記

せっかく AGC を開催できたので開催記として残そうと思います．

とりゐについて

私は今年の 3 月まで医学生をしており，2 月には医師国家試験というものがありました．そのため，試験の数カ月前から競技プログラミングをちょっとだけお休みしていました．無事試験も終わり，4 月からは雇われの身になるので，3 月のうちに ARC と AGC をやりたいな～～と admin にわがままを言ったところ，やらせていただけることになりました．AGC については問題数が足りていなかったのですが，私と同期で 3 月に卒業する nok0 君と一緒にできないかと admin に打診したところ，いい感じに組むことができました．

ARC++216

ARC の体制に変更があった後の初めての ARC++ 回です．問題の原案は去年の夏あたりにはほとんど揃っていて，国家試験が終わった後から準備をしていました．

各問題について軽くコメント

ARC216A - Reversi 3

01 列の操作系の問題を作りたいなと思って作りました．差分を取った後に parity を加えるというのは何度か出題されているので簡単枠のつもりで置いたのですが，苦労した人が少なくなかったみたい？

milkcoffee さんが yukicoder で全く同じ問題を出していたみたいです．自分も昔解いていたらしいんですが，まったく記憶にありませんでした．すみません．

yukicoder.me

ARC216B - Range Mex Sum

順列の mex が min に言い換えられるのを利用して問題を作れないかなと思って生やしました．いろんな解法があると思います． tester の Nyaan さんによれば N, Q\leq10^{5} で解くことができるようです．

ARC216C - Count Power of 2

よくあるスライムの合成の問題（同じレベルのスライムを 2 体合成すると，レベルが 1 増えたスライムを生成できる）で何かできないかなと思ったら生えました．区間の最大値を固定すると候補が少なくなることに気づければ，自然と分割統治したくなると思います．小さい方から見ていく方針で tester の tatyam 君が通していましたが大変そうでした．

ハッシュ解法の確率評価まわりで準備が大変で，tester のお二方にいろいろ助けていただきました．ありがとうございました．

ARC216D - GCD of Product of Arithmetic Progression

お気に入りの問題です．問題設定がシンプルで，しかもマルチテストケースで解けちゃうのがすごい．解法には厳密に証明するのが難しいパートがいくつかあると思っていて，そこはコンテスト中はエスパーされる想定でした．実装もまあまあ軽いです．

この問題，もともと TUPC で別のバージョンで出そうと思っていたのですが，そのときの問題はあんまりおもしろくないなと思って投げずに寝かせていたらなんかすごい問題に進化してしまいました．もともとは ARC199 のボス問として出すつもりだったのですが，紆余曲折あって ARC216 で出すことになりました．

ARC216E - Swap or Reverse

数列に操作する問題を作れないかがちゃがちゃやってたら解ける形になってました．部分問題の，

長さ N の整数列 X がある． X_l=X_r となる (l,r) を選び X_l,\ldots,X_r を reverse するという操作を何回でも行えるとき，どのような X を作ることが可能か？

の結論がきれいでびっくりしました．この結論を利用した問題が CodeForces とかで出ていたことがあるようですが，日本の競プロ界ではあまり知られていなそう？

この部分問題が解けた後もうまい実装を引かないと実装量が膨大になってしまうと思います．writer 解 / tester 解はそれぞれうまいことやっていて，特に writer 解の実装量は少なく済んでいます．

ARC216 感想

大体予想していた通りの解かれ方になっていました．E 問題の AC が 0 人なのはびっくりしました． 次の週で一緒に AGC やることになっていた nok0 君がこの回で赤になっていておめでたいですね～～～．

同じ色で AGC の writer やるつもりでいたので，いきなり突き放されちゃって悔しかったですが，それでも自分が書いた ARC で友人が赤になってくれたのはとてもうれしいですね．

ARC 直後の私のツイートをさかのぼると，執拗に nok0 君の入赤に反応する私がいくつかでてきます（このときはまだ AGC writer が非公開情報だったので言及が難しかった）．

AGC077

念願の初 AGC writer です．学生のうちにできたこと，友人で同期でライバルの nok0 君と一緒にできたこと，とても光栄です． 自分は B, C, E 問題を作りました．各問題について軽くコメント（F 問題は解けなかったので E 問題まで言及）

AGC077A - Reverse A…B

nok0 君 writer．自分が Tester したときは N 手で構築することを要求されていました．操作可能な必要十分条件に気づくのに時間がかかってしまいましたが，気づければあとはすんなりできました．（ABBBBBAAAAAB にしたあと BAAAAABBBBBA にする．）その後， N/2 手でできることに気づいたので指摘したらこの制約になりました．難しい！

AGC077B - Long Increasing Walk

問題名から考えた問題です．Long Increasing Sequence を Walk にしたらどうなるかな？と思って作り始め，紆余曲折あって今の形になりました．想定解はオイラー路を陽に作らずに実装していますが，多くの人は最長オイラー路をベースにした解法で解いていそうでした．

構築可能な下界が K = N になることの証明がきれいだと思っています．

AGC077C - Reverse and DAG

nok0 君 writer． tester 時は 3 時間くらいかかったと思います．実験をひたすらすると K が偶数のときは常に可能で， K = 3 のときが分かればいいことに気づき，あとは No になるようなケースとひたすらにらめっこしたらパリティが重要なことに気づきました．これぞ AGC ていう問題ですごいですね～～～

K = N - 1 のときにも解けないのかあと思っていろいろ試していたんですが，どうやら NP-hard みたいでした．

AGC077D - Range Replace 2

唯一の数え上げ枠．

N 個の区画があります． N(N+1)/2 種類の色があるスタンプがあり，スタンプの左端と右端を決めるとそれに応じた色で区画の色を上書きします．色の並びは全部で何通り？

というかなりシンプルな設定でしたが，完全既出ではないのがびっくり．（AGC067B がちょっと似ているらしい？）writer 解は操作と色の塗り方を一対一対応して頑張って O(N^2) に落としていますが，admin 解が簡潔ですごいです．一応 N\leq 2\times 10^5 でも解けます．

問題名は nok0 君が writer の ARC206A リスペクト．

AGC077E - Hamiltonian Path Inversion

実質 output-only の問題．もともと別の形で ARC199 で出そうとしていましたが，snuke さんが改題してくれて今の形に．問題設定も解法もめっちゃすごいです．今までの作問の中で一番のお気に入りです．解説見て驚いてください．

AGC077 感想

nok0 君と VC つなげて二人で観戦してましたが，世界トップランカーたちが自分たちの問題を解いていくのをリアルタイムで見れてずっと興奮していました． 私はちょうど TUNA というオンサイトコンに参加していて，AGC の配点を見た人々に「8 - 9 - 10 - 10 - 10 は可能枠たくさんありそうでいい配点だね～～」と言われていましたが，自分は配点の数字から受ける印象よりは難しいと思っていて（実際そうだったっぽい），全然そんなことないよ～～～と心の中で思っていました．予想では 5 完が出るかでないかくらいかなあと思っていましたが，実際は 4 完が 2 人だけでした．E 問題はなかなか AC 出ませんでしたが，simasima 君に解いてもらえてうれしいです！

この AGC でこれまた私と同期で 3 月に卒業する potato 君が自由色になって人間卒業を果たしていました．二週連続で自分が作ったコンテストで nok0 君，potato 君がそれぞれ色変してくれたのは感慨深いですね．

これからについて

冒頭で書いたように 4 月からは雇われの身となります．副業ができなくなったので，ABC / ARC / AGC の writer はしばらくお休みです．（3 月中にやってほしいとわがままを言ったのはこれが原因．ABC の原案大放出もしていたので，ABC / ARC / AGC は writer 6 連勤でした．）次いつ AtCoder で writer できるかわかりませんが，またコンテストを作ってみなさんと対戦できることを楽しみにしています．

最後に，ABC / ARC / AGC でお世話になった snuke さん，maroon さん，ありがとうございました！

Daily Akari 8/31 の解説

8/31 分の Daily Akari の writer をしました．

dailyakari.com

問題の形は車輪をイメージしています．解法も実際にぐるぐるすることになるので面白い（？）．

言い訳

今までの Daily Akari にはない ad-hoc な問題を作りたいと思い，「方程式を解かせる問題を作れないかな～」と考えながら作った問題です．解説通り解くなら dfs の深さはそこまで深くはなりませんが，気づくのはおそらく難しくて，深い dfs をする羽目になってしまって不快だった人もいると思います．すみません．

（問題を投稿したのが 6 月末で，そういうこともあって不採用になったのかと思っていたのですが，今更採用されてびっくり．）

（精度を気にしないなら 2 択を引き当てられるかどうかの運ゲーになります．たぶん）

運営の人との twitter の DM

日本語訳：数学的なアプローチが必要な問題を作りたくて，試行錯誤した結果このような形になりました．ただ，想定解が思い浮かばない場合，ただのバックトラッキング問題になってしまい，つまらなく感じるかもしれません。実際に採用するかどうかはお任せします．

解説

4 つの領域に分けて考えます．

左上

上の図において， A+B\in \lbrace 0,1\rbrace が成り立ちます．（Akari を置くなら 1 ，置かないなら 0 ．） A, B 両方に置くと真ん中の 1 に矛盾します．実際，以下のいずれかです．

右上

左上と同じ理由で C+D \in\lbrace 0,1\rbrace です．

右下

これも同じ理由で E+F\in \lbrace 0,1\rbrace です．

左下

G+H \in\lbrace 0,2\rbrace です．片方に置こうとするともう片方も置かざるを得ません．

まとめると

以下の 5 つの式が成り立ちます．

A+B \in\lbrace 0,1\rbrace
C+D \in\lbrace 0,1\rbrace
E+F \in\lbrace 0,1\rbrace
G+H \in\lbrace 0,2\rbrace
A+B+C+D+E+F+G+H=4

これより G=H=1 が分かります．これが分かれば残りはやればできます．

余談

作るのに 3 時間くらいかかった記憶があります．さすがに時間かかりすぎて大変なので，新しい問題を作る気は今のところありません． 他の人々はどのようにして作問しているのか気になります．

ICPC Yokohama Regional 2024 参加記

国内予選↓

toriidao.hateblo.jp

自分は Yokohama に参加するのは 2 回目．ラストイヤーなのでこれが最後．

去年の Regional の参加記を書いてなかったので軽く振り返っておく．

去年は CBT とよばれる医学部の進級試験のようなものが day1 とかぶっていた．CBT は朝 8:30 から夕方 18:00 まで試験会場に閉じ込められて，1 時間の試験を 6 セット走るという過酷スケジュールなため，ヘトヘトになりながら東京に向かったのを覚えている．

この試験は出題範囲が広いのである程度時間を割いて対策することが必須であった．もう一人のチームメイトが同じ医学科の同期であったこともあってチーム練をする余裕が全くなく，また US 配列に一度も触れることなく本番に臨まなければならなかった．試験の疲労が残り全く練習もしていない中での挑戦だったので、解くスピードはかなり遅かったが，事情を鑑みればこんなもんだろうと思って特に後悔は残らなかった．ほどなくして playoff というものが行われることを知った．60 チームが進出できる中で自分たちのチームは 61 位でボーダー落ちしていた．このときになって初めて多少ちゃんと準備しておけばよかった...とかなり後悔したが，数日後繰り上がりが発生したので 2~3 日以内に参加の意思を教えてくれというメールが運営から届いて無事 playoff に出場することができた．

ざっとこんな感じ．ここからは今回の Regional の話．

ベトナム playoff での経験で得られたものが多かったので，来年のシンガポール playoff にはなんとしても行きたいという思いが強かった．Yokohama と同じ US 配列を注文し，国内予選前から 3 人で土曜日に（秋ごろからは日曜日も）大学の図書館に集まって UC や CF gym の Regional の過去問で練習を重ねた．国内予選は 12 位で反省点がたくさん残る結果だったが，練習を積み重ねていくごとにチームメイトの特徴や役割をお互いに正確に把握できるようになり，連携がうまくとれるようになってチームとして安定するようになった．

UC を走っていると他の日本の ICPC チームが気になるようになっていた．SPJ, AMATUSKAZE, KUB1, Red Phobia, Anonyms, kotamanegi_hint_kureya あたりが気にしていたチーム．特に後ろ 3 つのチームと suzukaze は実力にほとんど差がないと個人的に思っていて，毎回彼らの順位をチェックしては自分たちの順位と比較して一喜一憂していた．

Day1

東北大のほかチーム Marines と同じ新幹線を取り，選手 + コーチ 8 人が東京駅で合流して横浜へ向かった．途中昼食を横浜駅で取った．

会場に到着して受付を済ませて中に入る．ちょうど真ん中あたりの席だった．Day1 は初めてだったのでちょっとワクワクしていた．チームメイトと適宜雑談をしながらルール説明やデモを眺めていた．デモで最初に WA を提出する茶番は恒例らしい？が，初めてだったので面白かった．Python で input() と input().split() だと型が違うので count の挙動が変わるみたいなことをしゃべったりした．

リハーサルではとりあえず事前に気になることを clar に投げた後，VS Codium の使い勝手についていろいろ試した．変数名の補間機能やシンタックスハイライトがあるかどうか気になっていたがちゃんとあった．去年にはなかった謎の補完機能が追加されていて使いづらかったが，設定をいじるのも怖かったので我慢することにした．問題を解かずにいろいろいじっていると運営の人に心配されて声をかけられたり周囲をうろうろされて様子を監視されたりしていた．

特に問題なくリハーサルが終わり，チーム紹介に移る．英語がまともに喋れないので日本語で日本人向けに TUPC の紹介をしたら怒られてしまった．すみません...

リハーサルが終わったら東北大 8 人で中華街で夕食を取りそのまま解散．suzukaze は 4 人一緒のホテルを取っていたが，ホテル代を安く済ませるためにやや遠くのホテルを取っていた．遠いことは認識していたが思っていたよりも遠く，身体への負担が大きかった．23 時に消灯したが，まったく寝付けられず最悪だった．寝ようにも寝られず，スマホで寝る方法を調べたり YouTube で睡眠用の BGM を流してみたりしたが全く効果なかった．結局寝れたのは午前 2 時頃だった．

Day2

6:10 起床．明らかに寝不足．ホテルの朝食を済ませて 7 時半出発．8時半ごろ到着し，コーチとお別れして入場．着席した後は初動について確認していた．コンテスト開始が急に 15 分繰り上げされてビビったが，コンテストまでの苦しい虚無の時間が苦手な自分にとっては助かった．

コンテスト

PC のセットアップを Dis さんがしている間に僕と仮君で A 問題を一緒に見る．何が書いているかさっぱり読めずぼーっとしているところに仮君が概要を伝えてくれる．区間 chmax する操作回数を最小化して与えられた数列を作ってくださいという内容で，操作を逆順に見ると簡単．制約が緩いので O(N\max(A)) かけて通す．(0:06)

続いて B 問題の概要を伝えられる． L 以上 R 以下の整数のうち popcount が最小になるものは？という内容で，セグ木の区間を意識すれば簡単．ちょっと実装に手こずったが AC (0:12)．

ここまでは想定通り．B 問題を書いているうちに Dis さんと仮君が残りの問題の分野を大雑把に把握してくれていた．ぱっと見自分は I 問題が得意そうだったので目を通すと，クエリ先読みをしたうえで l の降順にセグ木を使いながら答えを求めればよいことにすぐ気づく．Dis さんにセグ木の写経を発注して仮君に解法の概要を伝える．うまく伝えられず彼にはよく分からないと言われたが，割と自信があったしほかの問題も AC が出ていなかったのでそのまま I を書くことにした．ちょうど写経も終わった頃だったのでそのまま実装する．実装に詰まることもなく AC (0:29)．計算量をあまりちゃんと考えていなく，本番中は O(N\log N\log \max A) くらいで余裕だと思っていたが実際は O(Nd(\max(A))\log N) でそんなに余裕はなかった．

まだ I 問題に 2 チーム AC 出ただけで順位表に動きはなかった．ほどなくして E に AC が出たので二人に読んでもらうと簡単な構文解析チックな問題だった．実装は私がやったほうが良いと言われたので概要を聞いて問題文にある通りに実装して提出，AC (0:43)．

自分が E の実装をしている間に二人は K に取り組んでいて解けたらしい．仮君の実装を Dis さんが監視する体制にして二人が PC に向かう．自分は残りの問題を読むことにしたが，C 問題は問題文が何言ってるかわからず，D 問題は概要は把握したが何から手を付けていいか全くわからなかった．頭が全く働いていなかったので実装中の K の問題概要と解法を Dis さんから聞くことにした．ゼータ変換をして反転した bit を見ればよいと主張していて正しそうですねと言う．ゼータ変換をした後に自分自身が相手になってしまうことはないか？という疑問が湧いたので Dis さんに質問したらそこは大丈夫と言って確かにとなったが，全部 Y のときにコーナーになることに気づいた．全部 Y であるような index の配列を作ると楽そうと実装に口出ししてそのように実装してもらう．実装は全部終わったがそれでもちょっと怖かったので，ぺナを出さないことを優先して僕がランダムチェッカーを書くことにした．ちゃんとランダムチェッカーが落ちないことを確認して提出，AC (1:07)．

その間に kotamanegi_hint_kuerya が C を解いているのを見て C を Dis さんが読んでいた．概要を伝えてもらい，主客転倒したら最短経路やるだけではないか？と言った．Dis さんも同じようなことを考えていたようだったが自信がそこまでなかったように見えたので，かなり正しい解法のように見えますと主張して Dis さんに正しそうなこと納得してもらい，Dis さんに実装を任せる．解法が簡単な割に開始 1 時間時点ではほとんど解かれていなかったのが不安だったが AC した (1:18)．

この時点で 6 完 2 位．Screenwalkers に 1 分差で迫っていた．再び順位表情報が無くなったので解けそうな問題を探す．この時間帯はしばらく順位表を眺めてほかチームの動向をうかがっており，その姿がライブ配信にも映っていた．最初に F 問題を取り組んでいたがあまり筋のよさそうな解法が思いつかない．Screenwalkers が F 問題でぺナを吐いていて沼りそうな予感がしたのでいったん切り上げる．Anonyms が L 問題に挑戦していたので概要を把握する．連続する区間であってその和を d で割った余りが r であるようなものを削除していく問題で，直感的にこの問題は解ける気がしたのでこの問題に取り組む．制約が N\leq 500 なので区間 dp が怪しそう．複数回操作することでごっそり削除できるような区間が分かると嬉しそうな気持ちになる．いつもの区間をマージする遷移は簡単にできるが，問題は操作が括弧列のように入れ子構造のとき．これを O(N^3) で解決するそれっぽい解法を思いついて，Dis さんに方針を伝えて監視してもらいながら実装する．サンプルがあったので提出するが WA (2:12)．ランダムチェッカーを書くと入れ子構造のときの遷移が全部カバーできていないことに気づく．今の方針だとかなりまずいことに気づいて一から考え直し．しばらく手が止まる．私は L を粘ることにして仮君と Dis さんは正解者が増えてきた D に着手する．

開始から 3 時間ほど経過．徐々に 7 完が増え始めそれとともに suzukaze の順位もずるずる落ちていく．だんだん焦りがでてきた．L が全く分からなくなってしまったのでいったん私も D に手を付ける．仮君と Dis さんは一緒に考えていて，私は一人で考えていたが，焦りのせいか考察が進まない．少しして二人が D を解けたと主張する．解法を聞いたが全く理解できない．二人はそこそこ自信がありそうに見えたので仮君に実装に入ってもらうように言ったら，実装は私がしたほうが良いと言われた．解法を詰めてもらって実装方針を伝えてもらい，再び Dis さんの監視の下で私が実装する．解法は通り掛け順に頂点に番号を振っていって得られた 2 つの木の頂点を対応付けたうえで適当な積を取るというもので，結局なぜその解法が うまくいくのかよくわからなかった．実装は割とうまく書けて，サンプルがあったので提出するが RE が返ってくる(3:37)．いくつか assert を付けていたところがあったので一つずつ確認すると入力の長さが 1 のときに壊れていることが分かった．それだけ例外処理をして再び提出して AC (3:39)．順位が 14 位から 5 位に上昇し一安心．

順位表的には FGL あたりが解かれていて，自分は L に専念する．ランダムチェッカーで落ちたケースをしばらく考えていると，区間の中で削除操作が何回できるかに注目するのがよさそうなことに気づく．ただこのままだと 区間 [L,R) の中で k 回の削除操作をすることができるか？という bool を dp に持たせることになるが遷移が O(N^4) くらいになって，bitset 高速化は不可能ではなさそうだが厳しそう．もう少し考察を進めると，ちょうど k 回削除操作ができるときちょうど k-1, k-2, \ldots, 1 回操作することも可能なことに気づき，結局区間ごとに最大で何回削除操作できるかを管理すればよい．Dis さんにまた監視されながら実装を進め，嘘解法で落ちたケースもちゃんと正しい値が返ってきており，ランダムチェッカーでも落ちない．今度こそ満を持して提出，AC (4:27)．

ここで playoff 進出を確信．一気に力が抜けた．L の考察・実装中に仮君が F を考えており，自信のない解法が生えたようで，残り時間も少ないのでダメもとで書いてもらう．その間に私と Dis さんは F と G を考える．G はそれっぽい解法が生えるが実装がやばそうで 30 分では無理と判断し F を考えると，いい感じに 3 点を選んで外接円を考えればよさそうなことに気づく．F を実装中の仮君は書いてみたがサンプルがあわないらしい．仮君に外接円の解法を共有し，Dis さんには幾何ライブラリを写経してもらう．仮君と二人で解法を詰めたがもう時間がほとんどない．ごちゃごちゃやっていたらサンプルがあったので奇跡を信じて提出したが WA．そのままコンテストが終了した．

凍結中の順位表を確認し，playoff 進出で間違いないことを確認．3 人で喜んだ．

その後，9 階に上がって Yes/No．KUB1 の最後の追い上げと Screenwalkers の圧倒的強さに感動した．自分たちは序盤のアドバンテージがそのまま残り 8 完最速で 7 位．企業賞はもらえなかった．6 位の Red Phobia には G を通して抜かされてしまった．順位としては 1 つしか差がないが大きな実力の壁を感じた．

その後は懇親会．ベトナム playoff で仲良くなった阪大と京大の方々や，SPJ，審判団長の Y.Y. さんなどいろんな人と交流した．kotamanegi さんは早速 playoff が確定したチームに声をかけて discord を作っており頭が上がらない．シンガポールでまた会いましょうと挨拶をして会場を後にし，その日中に仙台に戻る人たちと一緒に帰った．

反省

コンテスト全体を振り返ってみると，序盤はこれ以上ないパフォーマンスが出せたが，中盤・終盤は実力不足を感じた．ここから順位を上げるためにはもう 1 完増やす必要があるが，正直今の実力だと厳しい気がする．L 問題が最初から正しい解法を引けていれば G 問題の実装に手を付けられた可能性はあったかなあ． 7 位という結果は上振れも下振れもせず実力通りかなと思う．国内予選では不甲斐ない結果だったが，そこから練習を積み重ねた成果が出せてそこそこ満足いく結果が得られたのはよかった．チーム力はだいぶ上がったが，個々の実力不足を感じる結果だったので，2 カ月後の playoff にむけてそれぞれの実力をパワーアップさせて東北大初の WF に行けるように頑張りたい．

さいごに

このような素晴らしい機会を提供してくださっている運営の皆さん，本当にありがとうございました．Yokohama に選手として参加することはなくなりますが，今後は JAG として運営をお手伝いできればと思っています． 一緒にシンガポールに行くみなさん，引き続きどうぞよろしくお願いします．

ICPC国内予選2024 参加記

torii + karinohito + Dispersion の 3 人で suzukaze_Aobayama として出場．12 位．

チームについて

suzukaze_Aobayama は今年で 4 年目．3 年前は mugen + sotanishy + karinohito，去年と一昨年は sotanishy + karinohito + milkcoffee だった．今年は karinohito 君以外の 2 人がいなくなってしまったので僕と Dispersion さんが加わった．

各メンバーのレート(Highest) は橙・橙・黄で，割とバランスがいいチームだと思っている．特に僕と karinohito 君はお互いの苦手な部分を補い合っていて，隙があまりない．毎週末に大学の図書館で 3 人で集まって 5h コンを走っているが，練習では失敗したことがなく，日本の他大学のICPC強豪チームに勝つことも少なくなかった．

模擬国内まで

チームが確定したのが 4 月下旬で，そこから可能な限り毎週末に集まって UC や Gym を走った．国内予選はまあ突破できるだろうと思っていたので，Regional やその先を見据えた練習をしていた．模擬国内までに 3 人でのチーム練は 8 回行っていて，どの回も冷えたことがなかった．解くべき問題をうまく分担できていたし，チーム戦のムーブが失敗することもなかった．一度も失敗を経験しないのが逆に怖くて，本番前に失敗したときのムーブとか雰囲気を経験しておきたかったので，練習のときに「失敗しないかな～～」とか言ってた（これがフラグ回収になってしまった...）．ほかには AOJ-ICPC の 国内予選/模擬国内 埋めを 3 人でやり，進捗状況を共有（監視）し合った．

模擬国内

3 位．この日も順調だった．軽く感想を書いておく．

初動について．A 問題は僕が担当．B 問題の問題文が短いなら僕に投げてもらうことにしていて，その判断を僕が A 問題を解いている間に k と d に任せる．C 問題は k と d．D 以降はその時に応じてという感じ．

というわけで A 問題を解く．

A問題 AC(00:02:10)

k と d に B 問題の実装を任せられたのでやる．微妙に実装をバグらせて時間がかかってしまった．

B問題 AC(00:10:39)

B 問題を僕が書いている間に二人が C 問題の考察が終わっていたので実装を d に渡す．実装方針について軽く助言をした．

C問題 AC(00:27:06)

先に D 問題にまで目を通していた k から問題概要を教えてもらう．このときに誤読をしていたみたいで，状態数が分割数になってしまう DP になってしまい，コードは書けたものの実行時間が遅く，しかもサンプルが合わない．ようやく誤読に気づき，正確な問題文を理解したら解法がすぐに降ってきたのでコードを書き直す．

D問題 AC(00:47:31)

k と d が E 問題の考察を終わらせていたので k に実装を渡す．そのうちに F 問題を読むと，これもあまり時間がかからずに解法が降ってくる．d を呼んで僕の解法の正当性を二人でチェックし，実装方針もある程度固める．そうこうしているうちに，k が E 問題の実装がある程度終わらせたがサンプルが合わないらしい．コードを discord にペーストして，実装をもらう．F 問題はバグらせることなくすぐに AC．

F 問題 AC(01:06:10)

E 問題のバグが見つかったらしいので E 問題に実装を戻す．無事 AC．

E 問題 AC(01:12:22)

全員で G 問題を考える．最初は CHT 方針を思いつたが，上位 K 個の最小値を持つ方法は知らないのでいったん別の方針を考える．お絵描きをしていると想定解の遷移を priority queue で管理する方法を思いついたので僕が実装する．愚直解もちゃんと書いて落ちないことを確認．

G 問題 AC(01:43:38)

この時点で 1 位．かなり順調

その後は H 問題を全員で考えていたが 1 時間かけても何も解法が思い浮かばず終了．結果は 3 位．

感想

手ごたえとしてはいい感じ．ちゃんと分担できていたし，大きく詰まることもなかった．特に上振れを引いたという自覚はなくて，ちゃんと練習した成果が出せたかなという感触．ひとまず安心．

国内予選

14 時に研究室にサークルメンバーと集合して席決めをした．東北大では AtCoder じゃんけんで勝った順に席順を決めていくという慣例がある．今年は1チームだけ個室のvipルームを用意されていた．じゃんけんに勝ったのでこの部屋を選択．

そのあとはプリンターのチェックをして，時間をつぶしていた．毎年リハーサルから本番までの時間が長すぎるといっている気がする．その間に緊張して研究室のトイレにお世話になるというのも恒例になっていた．ヌルっとコンテストが始まった．

初動は基本的に模擬と同じ．僕が A 問題を読んで書く．昨年は python の強みを生かして FA 賞を狙いに行ったが，今年は事前準備が許されていて強みが活かせないので，冒険はしなかった．

A問題 AC(00:02:00)

B 問題の実装も頼まれたので引き続き実装．k にうまい実装方針を教えてもらったので言われたとおりに実装．

B問題 AC(00:05:49)

C 問題の実装を k,d に渡して，D 問題を読む．問題自体は簡単だが，実装方針を誤るとめんどくさくなりそうな問題．k を呼び寄せて実装方針について軽く相談．私はダブリングを提案して，k はループのサイズで割る方針を提案．k の方針の方がバグりにくいと判断したので後者の方針を取る．そのころには C 問題も解かれていた．

C問題 AC(00:09:09)

D 問題の実装をやる．途中で実装がミスりそうだなと判断したので，k を呼んでにコーディングを監視してもらう．実装で結構沼った気はするが無事 AC．

D問題 AC(00:36:28)

この時点で 8 位．模擬国内よりは低いが悪くはない．ここからが地獄だった．

僕が D 問題を解いている間に E 問題の解法が出来上がっていたらしい．解法は解説と違って，再帰的に貪欲に決めていくという方針で，結果的にはハズレ方針だった．実装を d に任せることにしたが実装がやばくなりそうな気がすると本人は言っていた．ほかに実装キューがたまってるわけでもないし，順位も悪くないのでそのまま任せた．

F 問題を僕と k で読む．コインから ４ 方向を逆にたどればいいと k が提案してくれてよさそうな方針だねと言う．僕は壁を折り返してボールの挙動を直線として扱う方針を提案したが，k は愚直にシミュレートする方針を提案．後者の方針を取り二人で細部を詰めた．実装が結構大変な気がしたが，k なら大丈夫だと思って k にお願いする．k は引き続き F の実装方針を詰めている間に僕が d に E 問題の実装を覗きに行くと，実装が爆発していそうだった．E は一応実装しきったものの，サンプルが一向に合わない．このあたりから焦りが出てくる．

E 問題の実装を続けているのはよくないと判断し，強制的に実装を F 問題に移す．F 問題も実装が爆発しやすい系の問題ではあったのでこの判断はかなり怖かったが，k の実装力を信じるしかなかった．僕と d は E 問題のコードを印刷してデバッグ個所を確認しようとしたが，コード量が多く焦りもあって全然頭に入ってこない．いくつか間違えている箇所を発見し，その都度いったん実装を F 問題からもらうが，それでも一向に合わない．ますます焦りが募のる．

ここで，E 問題の別の実装方針が思いついていた（解法は同じ）ので，思い切って今まで書いたコードを白紙にしてそっちの方針をとることにした．d に僕の実装方針について説明して間違いがないことを確認．F 問題の実装を優先し，それが終わってから僕が E 問題の実装を担当することにした．

E, F 問題でできることがなくなったので G 問題を考察する．全部偶数 -> 奇数 * たくさん + 偶数 * 1 -> 全部奇数 の順番に考察して，あっという間に解けてしまった．EFG の中でこれが一番簡単じゃん！かなりの確信度があった．実装も E, F に比べると部分和問題を解くだけなのでだいぶ軽い．余裕が少し出てきた．

ちょうどそのころ F 問題の実装が終わったらしいが案の定バグがあるらしい．G 問題を 15 分くらいで確実に通せる自信があったので，F 問題を印刷して G 問題の実装をもらう．d に実装を監視してもらいながらコードを書きあげた．バグもなく提出すると AC．

G問題 AC (02:20:49)

D 問題 AC から 100 分．本当に苦しかったしめちゃくちゃ焦った．順位表を見るとこの時点で東北大 1 位．安堵．

k が F 問題のバグの個所を見つけたので修正してサンプルがあったので提出するが WA．再び F 問題を印刷して，今度は E 問題の実装をもらう．実装方針はほぼ決まっていて，怪しいところは紙コーディングもしておいたので順調に進む．そのうち F 問題のバグを見つけたらしいので再び F に実装を戻して再提出．無事 AC．

F問題 AC (02:42:02)

これで予選突破がほぼ確信になり，だいぶ心の余裕ができる．残り時間はわずか．E 問題が残っているのでこれを終わらせることに専念する． 実装が終わり，サンプルや手で作ったテストケースがあったので提出するが WA．修正箇所を見つけたので書き換えて再提出するがまたもや WA．原因がわからないのでとりあえず解が valid かどうかを assert を付けてチェックすると落ちた．印刷して目視で確認していた k が決定的なミスを見つけてくれたので修正すると assert で落ちない．3 度目の提出でようやく AC．

E問題 AC(02:56:04)

残りは 4 分でもうできることはない．後半良く挽回したねと讃えあって振り返ってるうちにコンテスト終了．

感想

中盤はかなりひやひやした．結果的には 7 完 12 位で悪くはないがいろいろ反省が残った．初めて冷えるコンテストが本番だったのマジで困る．やめてくれ～～～．初めての冷えでたくさん反省点が見つかったので，Yokohama までに克服せねば．

potate さんの実況で suzukaze の挽回に言及されていて，中盤死んだ状態から 3 問とも通したのは偉いと言っていた．自分でもそう思う．終盤はチーム練の成果が出ていたと思う．

今後

国内予選は相性が悪かっただけで 5h になると安定していると思っているので，Yokohama ではこれよりいい順位取りたいなー．

AGC066-B 解法

自分のコンテスト中の解法

N=4 の場合を考える．次のような数を考える： 5^0, 5^1, 5^2,5^3,5^4 を並べる．ただし，お互いが干渉しないように適宜間に 0 を追加する．

ここでは，間に 0 を 10 個追加して x=10000000000500000000002500000000001250000000000625 とする．

このとき， x,2x,4x,8x,16x は次のような振る舞いをする．

 10000000000500000000002500000000001250000000000625
 20000000001000000000005000000000002500000000001250
 40000000002000000000010000000000005000000000002500
 80000000004000000000020000000000010000000000005000
160000000008000000000040000000000020000000000010000

例えば x から 2x への変化に注目すると， x から 625 を削除して，新たに 2 を追加したものとみることができる．同様に， 2^{i-1} x から 2^{i}x への変化は 5^{5-i} を削除して新たに 2^{i} を追加したものとしてみることができる．したがって， 5^{5-i} の桁和が 2^{i} の桁和より大きくなっていればよい．

このままでは不十分だが，次のように問題を一般化してみる：

5^{0}, 5^{1}, \ldots, 5^{M-1} の間に適宜 0 を追加した数を考える．このとき，各 i=1,2,\ldots,N に対して 5^{M-i} の桁和が 2^{i} の桁和より大きくなっているか？

これを厳密に紙面上で判定するのは難しいが， 2^{i} がそこまで大きくない（せいぜい 10^{15} ぐらい）ため， 2^{i} の桁和も雑に見積もっても 15\cdot 9 にしかなりえない．よって， M を比較的大きめにとることで 5^{M-i} の桁数が増え，結果的に 5^{M-i} の桁和を 2^i の桁和よりも大きくすることが（期待）できる．

実際に，例えば M=100 ，間の 0 の個数を 20 個（これで十分干渉しない）にすることで AC が得られた．

TUPC2023 開催記

TUPC2023 を開催しました．

atcoder.jp

準備記録とか運営記録とかは他の運営の子たちが書いてくれてるのでさぼってそちらに譲ります．各問題について感想など．

A - Namboku / Tozai Line

Welcome 枠．

B - 012 Grid

LGV 公式を知らず解説 AC．結構面倒だと思って取り掛かったらシンプルになって感動．ABC 上位勢たちがたくさん通してくると予想してたがハズレ．

C - Topological Sort

Writer．設定がシンプルで考察もちょっとあってそこそこ面白枠だったんじゃないかなと．サンプルで人々をだまそうと思って答えが 2 べきになるケースしか置かなかったらみんなだまされててにこにこしてた．線形で解けるのが地味に推しポイント．

D - Shift Puzzle

Writer．去年 7 月の AGC063 で大敗した後に嫌になって作問してたら思いついた問題．3 点 rotate を利用して 2 点 swap が実現できるのがびっくり． N^3 回っていう制約が想定解だとちょうどぴったりになる．FA の zkou さんが想定で解いてくれたらしくうれしい．非想定解法もいくつかあるみたい．

E - And DNA

自分は実験・実験・OEIS で解いてしまったのでこの問題は面白ポイントがまだわかっていないが，ちゃんと解くと面白ポイントがあるらしく評判は良かったみたい．問題名の DNA が何なのかずっと分かってなかったが解説スライドを見て納得した．

F - Hotel

横から首出してコードを投げたらそれが想定解になってた．題材が無限ホテルだったので，だったら最初から長さ無限にしませんか？と提案したが厳密性が怪しくなると数学のプロたちに言われて却下されちゃった．

G - Min Nim

渡されて 2 分で解けたのでこれは簡単ですね～って言ってたが，他の人はすんなりはいかなかったみたい．

H - Count Pseudo-Palindromes

最初の提案時からわからず解説 AC．最初 O(N \log ^2 N) 解法が想定で，そのときは長さが良い擬回文の列挙に帰着して列挙に O(N \log ^2 N) かけるというものだった．その後まったく方針の違う O(N\sqrt{N}) やら O(N \log N) 解法がたくさんでてきたので改めて元の想定解の列挙パートを考えてみたところ，線形に落とせることに気が付いたのでそれを報告．なんやかんやあって今の形式に落ち着いた．K の満点を除けばこれが最難問だと思っていて，本番は正解者が出るかどうか怪しいと思っていたが実際は 1AC 出ていてすごい．線形で解けるのが地味に推しポイントその 2．

I - Maximize Array

Writer．簡単枠が足りてなかったみたいだったで適当に考えてたら案外よさげなのが生えたので提案．簡単だけどちゃんと考察をしないとペナしやすい問題になってよかった．

J - Colored Complete Graph

もともと N\leq 200 とかで，そのときは乱択で雑に通してしまった．ちゃんと想定解の考察を要求しましょうということで N\leq 50000 に．AtCoder のインタラクティブの問題で質問回数が 10^5 回以上ある問題が見つからなかったので心配だったが特に指摘されることはなかった．

K - (mod HW+1)

この問題が 100 点の部分点も含めて誰にも解かれない問題になってしまった．100 点の部分点はすごい難しいというわけではなく正解者も出るだろうと予想していたのでびっくり．101 点の存在にみんなビビっちゃったのかなあ．準備段階で，もともと W が H=W バージョン（部分点 100 点）の問題を提案していて，それはそこそこ時間はかかったが自力で解けた．お正月の帰省中に H\neq W バージョンをふと考えてみるとなんか解ける気がしたので，W/T に解けるかもしれないと報告．実査にはその後がめちゃくちゃ大変で，ひたすらコーナーケースつぶしをしていた．特に (H,W,R)=(11,13,0) が不可能なことの証明が大変で，この証明にかなりの時間を割くことになった．最終的に自分はプログラムを書いて枝刈り全探索をすることで証明した．

L - Random Mex

制約を無視すればいろんな解法がありそう．実際自分は各テストケースに対して O(M \log N) の解法が最初思いついていたし，他の準備陣からもいろんな解法が出ていた．しばらくして，答えがスターリング数を用いると簡潔な式で表現できることが分かったので，だったらそれを要求するような制約にしませんかと提案．結果的に今の制約になった．一応 OEIS を使えばエスパーすることができることは確認していたし，数え上げ得意な人多いからもうちょっと解かれると予想していた．

M - Vivid Colors

自分が問題を渡されたときは，題材に倣って r,g,b\lt 256 の制約だった．最初の式変形は wolfram alpha に投げるとやってくれて，あとは選ぶベクトルを乱択することで犯罪 AC をした．他のテスターも乱択で通していたので，しぶしぶ制約を強化して乱択を通りにくくするように．想定解は実装も含めてかなり難しいと思う．sotanishy 君の別解はすごい．

N - Do Not Turn Back

サークルの活動の後に問題を教えてもらい少し考えて分からず，すぐに解法を聞いてしまった．典型っぽさはあるが難しいと思う（自力では無理な気がする）．この問題を BMBM で解けちゃうのはびっくりした．

O - 0100 Insertion

判定問題を 5 時間位考えたが分からず解説 AC．必要十分条件がすっきりしていてすごい．その条件が前から見ていかないとダメだったので，じゃあ最初からひっくり返しておきませんかと提案した．結果 1AC になった．

P - Sub Brackets

この問題が参加者の中で一番評判が良かったんじゃないかなと思う．見た目（制約も含めて？）は区間 DP っぽさがあるが想定解はフローで，そのギャップに驚いている人たちがたくさんいた．自分も区間 DP にまんまとハマってしまったし，コンテスト中に実際にハマっていた人もいたようだった ． N の制約は何でもよかったが，区間 DP っぽさを出すために N\leq 500 ということに．

自分がやったこと

  • C：Writer
  • D：Writer
  • H： O(N) 解法の提案
  • I：Writer
  • K： H\neq W バージョンの提案
  • L： O(N^2) 解法を要求することを提案
  • M： r,g,b の制約を強化することを提案
  • O：0010 を 0100 に変更することを提案

その他

TUPC の前の ARC で無事 karinohito 君が入橙していた．これにより toam, sotanishy, karinohito 大学同期 3 人が揃って橙の状態で TUPC を迎えることができた．sotanishy 君が来月からいなくなってしまうので，その前に全員が揃う瞬間ができて本当に良かった．

以上，ご参加ありがとうございました．

AHC028 参加記

11 位．

懇親会 + 賞金 1.5 万円ゲット！やったぁ

 

開始 30 分で考えたこと

  • 作る文字列があらかじめ決まっていたら，DP で最適解が作れる
  • 文字列の長さを最短にするのが必ずしもいいとは限らない
  • 作る縁起の良い文字列の順番を決め打ったら，DP で最適解が作れる
  • いい感じの順番を探したい -> ビームサーチ？焼きなまし？
  • 2-opt がうまくいかなそう（T1 -> T2 の相性は良くても T2 -> T1 の相性は良いわけではない）
  • 他の近傍が思いつかないので，とりあえずビームサーチにしよう
  • ビームサーチだと，もともと作りにくい文字列たちが残っちゃわない？ -> 各文字列に対して，"作りやすさ" （値が小さいほど簡単）を定義して，ビームサーチ中にはコストから作りやすさを引くことにすればちょうどいいのでは？

あとはひたすら実装．ビームサーチは速い言語の方が有利なので c++ で書くことにした．

（上に書いた考察は解説放送で大体同じことを言っていた（作りやすさは解説放送の base cost みたいなもの））

 

実装

まずビームサーチを高速化するのを念頭に， T_i の次に T_j を付けるときに必要な遷移コストを前計算した． dp\lbrack i\rbrack \lbrack j\rbrack \lbrack (x_i,y_i)\rbrack \lbrack (x_j,y_j)\rbrack で「 T_i の末尾の文字がマス (x_i,y_i) で終わっていた場合に， T_j の末尾の文字をマス (x_j,y_j) で終わらせるために必要なコスト」みたいな感じで DP を定義した．

ビームサーチの状態としては，「すでに決定している T の順序，および最後のマス」を持った．

文字列 t に対する作りやすさ（base cost）は，とりあえず「マス (x,y) から始めたとき文字列 t を作るために必要な最小コスト」を N^2 個すべての (x,y) に対して求め，それらの平均値とした．

 

いつもは python を書いているため，慣れない言語でかなり実装にてこずったが，2:07:14 に初提出 (1081686 点)．このとき 10 位．

初提出のビーム幅を間違えて 2 にしていたので，70 にしてから再度提出 (1092374 点)．6 位に浮上．

 

残り時間は高速化と base cost の計算方法を変えたりしていた．base cost を平均値の 0.8 倍くらいにすると 1097399 点．これがコンテスト中最高点だった．

 

解説放送を見ると，base cost は「全ての (x,y) に対する最小コスト」の最小値としていて，これに変えてみると 1099433 点になってコンテスト中順位 8 位まで上がった．コンテスト中にこの計算方法も思いついていたので悔しい．seed=0,1 でよくならなかったので諦めていたが，とりあえず出してみればよかった．

 

感想

自分の解法がちゃんとはまり，AHC 過去最高順位も取れてうれしい．とても面白い問題だった．懇親会楽しみ～