コンテストURL: https://yukicoder.me/contests/494
エイプリルフールコンに参戦させていただいたばかりですが、オムニバスコンの枠が応募締め切りぎりぎりまで空いていたため参戦させていただきました。
エイプリルフールコンは例外的なコンテストなので除くと、オムニバスコンへの参加はおよそ１年半前の998244353コンテストぶりです。オムニバスコンってお祭りみたいで楽しいですよね。当時が懐かしいです。
実は998244353コンテストは元々２問出題予定だったのですが、応募者が多数だったため２問のうち１問の登録を取り消し、他の方にお譲りした経緯がありました。取り消した１問もせっかくtesterしていただいたものなので第2回998244353コンテストに回すつもりでいたのですが、１年半近く経っても開催されなかったのでこの機会に出題させていただくことにしました。
ちなみにtesterを引き受けたB,C,F問題のうちB,Cはどちらも素因数の数え上げ問題だったわけですが、writerさんが別々なのでかぶっているという情報は伝えられないわけですね。そしてかたや素因数の個数と言ったら断りのない限り重複を数えない流儀で、かたや素因数の個数と言ったら断りのない限り重複を数える流儀、とそれぞれの暗黙の流儀が異なっているなかなかレアな状況でした。
もちろんwriterさんに同一コンテスト内の他の問題と用語の流儀が異なっていることを伝えることもできないので、事情は伏せながら後者には「重複を込めて」をつけてもらうという対応をしました。前者にも念の為「相異なる」をつけてもらおうと思ったのですが、後者の作問作業終了後（当日の割とギリギリのタイミング）の打診となったためコミュニケーションが間に合わず、結局そのままでハラハラしながらコンテスト開始時間を迎えました。混乱させてしまった参加者の方々にはお詫び申し上げます。
偶然の一致はそれだけでなく、H問題がG問題と同じく代数構造に関するグラフの連結成分数え上げ問題でこれまたビックリ。writer間でお互いに何を出題するか把握できないオムニバスコンならではですね。ただG問題はあまり提出がなかったのが寂しいところです。もっと分かりやすい問題文が書けるようになりたいですね。
それでは、ご参加いただいた方々、testerしてくださった方々、他のwriterさんの方々、運営さん、皆様、ありがとうございました！
そしていつか解析コンテストと幾何コンテストを開催予定です。解析コンテストは全問testerさんが見つかっておりますので、個別tester作業が終わり次第全体testerさんを募集したいと思います。幾何コンテストは2023/5/10現在まだtesterさん見つかっていない問題が残っていますので、testerをしてくださる方を募集中です。
A: No.2749 随伴関手入門 ★☆ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/2749 tester：Takaさん | ||
| 圏論の重要な概念の１つ、随伴関手の具体例に触れる問題です。とは言っても圏論の知識は不要で、問題文を適切に読み取ってフィボナッチ数列の法$N$計算を行えるかを問う問題です。 フィボナッチ数列の添字は$1$ずらすことも多いですが、今回は添字の約数関係を使うためこの添字の取り方をすることに意味がある問題設定なところが面白いですね。 計算量解析が非自明なので解説も楽しんでいただければと思います。 | ||
D: No.2752 文字列の数え上げ mod 998244353 ★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/2752 tester：箱さん | ||
| 等比数列の和の公式、法$998244353$繰り返し二乗法、法$998244353$逆元計算、といった★2相当の基本テクニックに加えて、★2からは必須となる計算量解析をきちんと行えるかを問わせていただきました。全体的に★2の中では基本中の基本を問いているため、慣れている人には一瞬で解ける問題だと思います。癒やし枠となってくださっていれば幸いです。 ちなみに普段は整数論的な背景から動的な法を出題しがちで特定の法を固定した問題はあまり出してこなかったのですが、先述したようにこの問題は元々taiga0629kyoproさん主催の998244353コンテストで出題予定だった2問のうちの1問だったので法が$998244353$固定です。taiga0629kyoproさんもtester一覧に入っているのはそのためですね。 今回は法$998244353$であるおかげで$25$での割り算が行えるのですが、動的な法を意識して割り算を避けた解法を投げてくださる人もちらほらいたようで嬉しいです。実は線形代数コンテストで実際にそのような考察が必要な問題を出題させていただいたことがございまして、もしかしたらこの問題を通じて思い出してくださった方もいるといいな、と思いました。 | ||
E: No.2753 鳩の巣原理 ★★☆ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/2753 tester：Moss_Localさん | ||
| タイトルの通り、鳩の巣原理の関わる問題です。ただし鳩の巣原理は抽象的な存在を保証するだけなので、具体例を得るためにはより構成的なアイデアが必要です。 そこで役立つのが、実解析でおなじみの区間縮小法の原理です。この問題を通じて区間縮小法が鳩の巣原理の無限版（もしくは任意精度近似版）の１つであることを新ためて認識していただき、ボルツァーノワイヤシュトラスの定理への理解へとつなげていただけたらと思います。 本来ならば解析コンテストで出したい題材ですが、解析コンテストで出題すると解析というテーマから解法が透けてしまうため、オムニバス形式での出題とさせていただきました。 さすが数値特定系のリアクティブ、なかなかのWA率でしたね。 | ||
G: No.2755 行列の共役類 ★★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/2755 tester：Shirotsumeさん | ||
| 競プロではあまり見ない、各連結成分が完全グラフの連結成分数え上げ問題です。各連結成分が完全グラフであるグラフは同値関係と等価であることを踏まえて、同値関係の商集合の数え上げにできるかを問いました。 商集合は集合論の初歩で現れ、競プロでも整数や多項式のmod計算でも頻出です。それでも抽象度は高く、相変わらず初学者を悩ませるものです。完全グラフとしての見方が身につけば商集合をイメージする解像度が上がるかもしれないと思い、こうして出題させていただきました。 問題文が難読だったためかあまり提出がありませんでしたが、ただの連結成分の数え上げだと思って素直に幅／深さ優先探索や素集合データ構造を使ってしまうとうまくいかない、というところがお気に入りポイントです。工夫して高速に処理しましょう。 なお制約がかなり厳しいです。これ以上緩くしたり出力上限の100をいじったりすると、高速な言語で愚直に幅／深さ優先探索や素集合データ構造を使うだけの解法が通ってしまったり、ほとんどのケースで上限に達してしまい「ある程度入力が大きい時は上限超え」みたいな判定が可能になってしまったりで面白みがなくなってしまうため、PyPy3が500[ms]余りでギリギリ通るくらいの調整となりました。 | ||