yukicoder contest 384開催記

2023/04/14

コンテストURL: https://yukicoder.me/contests/431

yukicoderで４度目のコンテスト開催です。そろそろ競技プログラミングの作問能力も少しは上がってきたのではないかと期待してはいましたが、コンテスト中には質問をいくつか受けることとなりまだまだ分かりやすさと正確さを両立させる技能が不足しているようです。

特に、「競技プログラミングの問題文では正解が存在することが保証される場合にその旨を明記すべきである」とご指導を受けたこと、そして入力制約では非負整数であるように書かれていたのに正整数と書いてしまったことの２点はとても深刻な問題だと受け止めております。今後このようなことがないようにこれら２点を作問時に入念にチェックするよう心掛けます。

ところで本コンテストを開こうと思い立ったのは2022年3月頭ごろでした。その時はyukicoderコンテストの予定が全然なくてちょうどいいかなと思っていたのですが、コンテスト開催を応募した時点で何故かコンテスト予定が６個になっていて１ヶ月待ちとなり驚きました。そして本コンテスト前日の時点では予定が１１個まで膨れ上がっており、なんと２ヶ月待ちのようです。3月頭は皆忙しかっただけなのか、予定が空いたからコンテストをしたいと思った人が沢山いたのか、何にせよ滑り込みセーフの開催となりました。心配性なため１ヶ月待ちでさえ開催までずっと不安がつきまとっておりまして、これが２ヶ月続いたらなかなか苦しかったかもしれません。

さて、本コンテストは数学の色々な分野を広めにカバーするものにしたいと考えておりました。これまで整数寄りの問題が多かったので、代数・幾何・解析・論理をバランスよく出題できてとても満足です。参加者の皆様、testerの皆様、そしてご質問をしていただいた皆様にこの場を借りてお礼申し上げます。

逆に１つの分野に集中させたコンテストも開いてみたいと思います。基礎論コンテストとか線形代数コンテストとか。その際もまたよろしくお願いいたします。

A: No.2267 群の公理 ★☆
問題リンク：https://yukicoder.me/problems/no/2267 tester：koboshiさん
群論です。定義域の要素数が小さいので、群の公理を証明または反証するためには全ての要素を探索して条件を確認するのが常套手段です。入れ子になった$\forall, \exists, \land$（および反証時にはそれらの否定）を正確に処理できるかどうかを問いました。

A: No.2267 群の公理 ★☆

問題リンク：https://yukicoder.me/problems/no/2267

tester：koboshiさん

群論です。定義域の要素数が小さいので、群の公理を証明または反証するためには全ての要素を探索して条件を確認するのが常套手段です。入れ子になった$\forall, \exists, \land$（および反証時にはそれらの否定）を正確に処理できるかどうかを問いました。

B: No.2268 NGワード回避 ★★
問題リンク：https://yukicoder.me/problems/no/2268 tester：Moss_Localさん
基礎論です。$N < 2^N$を構成的に証明できるかを問いました。対角線論法が想定解で、その他に全探索や乱択など何でも通るようにしてあります。数学では典型問題なので既出ではないかを気にしてtesterさんにもご存知でないかをお聞きしたりしていましたが、コンテスト参加者の感想的にも既出でなかったようで安心しました。 ……と思ったらなんと翌週のコンテストで出題される予定だった問題と被っていたとのことで、ギリギリセーフだったようです。

B: No.2268 NGワード回避 ★★

問題リンク：https://yukicoder.me/problems/no/2268

tester：Moss_Localさん

基礎論です。$N < 2^N$を構成的に証明できるかを問いました。対角線論法が想定解で、その他に全探索や乱択など何でも通るようにしてあります。

数学では典型問題なので既出ではないかを気にしてtesterさんにもご存知でないかをお聞きしたりしていましたが、コンテスト参加者の感想的にも既出でなかったようで安心しました。

……と思ったらなんと翌週のコンテストで出題される予定だった問題と被っていたとのことで、ギリギリセーフだったようです。

C: No.2269 eN!の整数部分の下１桁 ★★
問題リンク：https://yukicoder.me/problems/no/2269 tester：遭難者さん
実解析です。$e^x$のマクローリン展開を適切に応用できるか（ほぼ$e$の無理性証明）を問いました。ただし単純に和を取るとループ回数が大きくなりすぎるので適切にループを切る考察も必要となります。このように定理（今回は$e$の無理性）の証明を元ネタにした問題は色々と勉強になりやすいので好きです。コンテスト直後の感想的に驚いてくれた人も多かったようで嬉しいです。

C: No.2269 eN!の整数部分の下１桁 ★★

問題リンク：https://yukicoder.me/problems/no/2269

tester：遭難者さん

実解析です。$e^x$のマクローリン展開を適切に応用できるか（ほぼ$e$の無理性証明）を問いました。ただし単純に和を取るとループ回数が大きくなりすぎるので適切にループを切る考察も必要となります。

このように定理（今回は$e$の無理性）の証明を元ネタにした問題は色々と勉強になりやすいので好きです。コンテスト直後の感想的に驚いてくれた人も多かったようで嬉しいです。

D: No.2270 T0空間 ★★☆
問題リンク：https://yukicoder.me/problems/no/2270 tester：遭難者さん、MasKoaTSさん
位相空間論です。単純に$\textrm{T}_0$性（良いbit列か否か）を判定しようと思うと入出力を除いた部分の計算量が重いので、数学側で考察して$\textrm{T}_0$性を$1$点ごとの条件に同値変形するか、実装側で工面して計算量を落とすかのどちらかまたは両方ができるかを問いました。転置やソートによる解法は非想定だったので勉強になりました。ちなみに原案はbit列ではなく集合の言葉で書かれており難読だったのですが、testerさんのご尽力により競技プログラミングの問題文らしく整えられたので大満足です。c++の愚直は実装面での非自明な高速化なしでは通らないようにしたく、かつPythonは処理系次第できちんと通るようにしたく、入力制約の調整にはtesterさん方のお力をたくさん借りさせていただきました。ちなみに整数型に上限があることが想定解では逆に利点として活きるところがこの問題の好きなところです。多倍長整数が万能ではないのは当然ですが、上限があることの利点に目を向けた問題は解いたことがなかったので、こういう問題もたまにはありかなと思います。

D: No.2270 T0空間 ★★☆

問題リンク：https://yukicoder.me/problems/no/2270

tester：遭難者さん、MasKoaTSさん

位相空間論です。単純に$\textrm{T}_0$性（良いbit列か否か）を判定しようと思うと入出力を除いた部分の計算量が重いので、数学側で考察して$\textrm{T}_0$性を$1$点ごとの条件に同値変形するか、実装側で工面して計算量を落とすかのどちらかまたは両方ができるかを問いました。転置やソートによる解法は非想定だったので勉強になりました。

ちなみに原案はbit列ではなく集合の言葉で書かれており難読だったのですが、testerさんのご尽力により競技プログラミングの問題文らしく整えられたので大満足です。c++の愚直は実装面での非自明な高速化なしでは通らないようにしたく、かつPythonは処理系次第できちんと通るようにしたく、入力制約の調整にはtesterさん方のお力をたくさん借りさせていただきました。

ちなみに整数型に上限があることが想定解では逆に利点として活きるところがこの問題の好きなところです。多倍長整数が万能ではないのは当然ですが、上限があることの利点に目を向けた問題は解いたことがなかったので、こういう問題もたまにはありかなと思います。

E: No.2271 平方根の１３桁精度近似計算 ★★☆
問題リンク：https://yukicoder.me/problems/no/2271 tester：遭難者さん
$p$進解析です。テイラー展開やニュートン法などを使って適切に代数方程式を解けるかを問いました。この他に桁DPで解くことも可能です。なお解を１つ求めてそれの大きさを評価するだけだと他の解の影響でWAになるように問題設定しています。この問題はyukicoder contest 373のI問題である平方根の下１４桁を作問した際にtesterさんに「平方根を求める問題でも良いかもしれない」とご助言いただいた時に「既にそれも作っておりまして・・」と追加でチェックのご依頼をさせていただいたものです。testerさんには多大なご貢献をしていただきとても感謝しています。ちなみに原案の段階では★3.5に設定していたのですが、解説でも引用したように解法に近い解説が既に存在し検索に引っかかりやすいこと、そもそもこのような再帰的計算が典型であるとのことで★2～2.5が妥当（純粋な考察難易度は★2で難読性を加味すると★2.5でも良い）とtesterさんに教えていただき、過小は避けたかったので★2.5に直させていただいた経緯があります。検索である程度近い内容が引っ掛かってしまう場合の難易度評価は難しいですね。ただF問題に有名問題を持ってきてしまったため上級者がこぞってE問題を飛ばしF問題を一瞬で解いていったという事情から、序盤からAC数反転が生じてしまいそれを見た他の参加者たちがE問題は何かヤバいと認識してしまったようで、どんどんE問題が飛ばされていき最終的にAC数反転のままコンテストが終わってしまいました。確かにE問題も境界ケースが厳しい問題ではあるので多少の反転は覚悟していましたが、ここまで一気にF問題に流れることは予想しておらず色々と課題が残る結果となりました。

E: No.2271 平方根の１３桁精度近似計算 ★★☆

問題リンク：https://yukicoder.me/problems/no/2271

tester：遭難者さん

$p$進解析です。テイラー展開やニュートン法などを使って適切に代数方程式を解けるかを問いました。この他に桁DPで解くことも可能です。なお解を１つ求めてそれの大きさを評価するだけだと他の解の影響でWAになるように問題設定しています。

この問題はyukicoder contest 373のI問題である平方根の下１４桁を作問した際にtesterさんに「平方根を求める問題でも良いかもしれない」とご助言いただいた時に「既にそれも作っておりまして・・」と追加でチェックのご依頼をさせていただいたものです。testerさんには多大なご貢献をしていただきとても感謝しています。

ちなみに原案の段階では★3.5に設定していたのですが、解説でも引用したように解法に近い解説が既に存在し検索に引っかかりやすいこと、そもそもこのような再帰的計算が典型であるとのことで★2～2.5が妥当（純粋な考察難易度は★2で難読性を加味すると★2.5でも良い）とtesterさんに教えていただき、過小は避けたかったので★2.5に直させていただいた経緯があります。検索である程度近い内容が引っ掛かってしまう場合の難易度評価は難しいですね。

ただF問題に有名問題を持ってきてしまったため上級者がこぞってE問題を飛ばしF問題を一瞬で解いていったという事情から、序盤からAC数反転が生じてしまいそれを見た他の参加者たちがE問題は何かヤバいと認識してしまったようで、どんどんE問題が飛ばされていき最終的にAC数反転のままコンテストが終わってしまいました。確かにE問題も境界ケースが厳しい問題ではあるので多少の反転は覚悟していましたが、ここまで一気にF問題に流れることは予想しておらず色々と課題が残る結果となりました。

F: No.2272 多項式乗算 mod 258280327 ★★★
問題リンク：https://yukicoder.me/problems/no/2272 tester：hotman78さん
環論および体論です。プロス素数以外での畳み込みを適切に処理できるかを問いました。想定解は、ピアポント素数であることを利用した離散フーリエ変換のad hocな高速化と、中国剰余定理で３つのプロス素数での畳み込みに帰着させる有名手法です。恐らくほとんどの人が後者で解いてくださったと思います。有名問題を出題する以上、AtCoderLibraryをそのままでは適用できないように入力制約を緩めにしたり、その他のライブラリーを貼るだけで簡単には攻略されないように零多項式の次数を$0$に設定した上で境界ケースを強めてみたりと一応の工夫をしました。それでも上級者にはあまり通用しないとtesterさんに教えていただきまして、結果はその通りでAC数反転に繋がってしまいましたね。。ちなみに難易度調整のために何度か制約変更をしたり問題文を読みやすくしよう編集したりしていたのですが、制約違反を起こしたり問題文が矛盾したりとtesterさんに何度か指摘していただき危ないところでした。書いた文をもっとよく見直すよう気をつけます。

F: No.2272 多項式乗算 mod 258280327 ★★★

問題リンク：https://yukicoder.me/problems/no/2272

tester：hotman78さん

環論および体論です。プロス素数以外での畳み込みを適切に処理できるかを問いました。想定解は、ピアポント素数であることを利用した離散フーリエ変換のad hocな高速化と、中国剰余定理で３つのプロス素数での畳み込みに帰着させる有名手法です。恐らくほとんどの人が後者で解いてくださったと思います。

有名問題を出題する以上、AtCoderLibraryをそのままでは適用できないように入力制約を緩めにしたり、その他のライブラリーを貼るだけで簡単には攻略されないように零多項式の次数を$0$に設定した上で境界ケースを強めてみたりと一応の工夫をしました。それでも上級者にはあまり通用しないとtesterさんに教えていただきまして、結果はその通りでAC数反転に繋がってしまいましたね。。

ちなみに難易度調整のために何度か制約変更をしたり問題文を読みやすくしよう編集したりしていたのですが、制約違反を起こしたり問題文が矛盾したりとtesterさんに何度か指摘していただき危ないところでした。書いた文をもっとよく見直すよう気をつけます。

G: No.2273 一点乗除区間積 ★★★☆
問題リンク：https://yukicoder.me/problems/no/2273 tester：ecotteaさん
モノイド論または群論です。データ構造に載せるために$p$進付値を使って適切に$\mathbb{Z}/B\mathbb{Z}$と$\mathbb{Z}[B^{-1}]$の中間的なモノイドか群を構成できるかを問いました。抽象セグメント木でも抽象フェニック木でも解くことが可能です。ちなみにデータ構造を出題するのは地味に初めてです。データ構造問もよく作問していてストックが溜まっているのですがなかなか放出できていないので、データ構造コンテストとか開いてみたいですね。またデータ構造の出題が初めてなために難易度設定に自信がなく、もしかしたら★3.5は過大なのではと少し不安がありました。testerさんからは「考察難易度的には★3だけど実装が重めなので★3.5でも大丈夫」と太鼓判を押していただき、そしてコンテストが終わってみればAC数的にも★3.5でちょうどよかったみたいで安心しました。

G: No.2273 一点乗除区間積 ★★★☆

問題リンク：https://yukicoder.me/problems/no/2273

tester：ecotteaさん

モノイド論または群論です。データ構造に載せるために$p$進付値を使って適切に$\mathbb{Z}/B\mathbb{Z}$と$\mathbb{Z}[B^{-1}]$の中間的なモノイドか群を構成できるかを問いました。抽象セグメント木でも抽象フェニック木でも解くことが可能です。

ちなみにデータ構造を出題するのは地味に初めてです。データ構造問もよく作問していてストックが溜まっているのですがなかなか放出できていないので、データ構造コンテストとか開いてみたいですね。

またデータ構造の出題が初めてなために難易度設定に自信がなく、もしかしたら★3.5は過大なのではと少し不安がありました。testerさんからは「考察難易度的には★3だけど実装が重めなので★3.5でも大丈夫」と太鼓判を押していただき、そしてコンテストが終わってみればAC数的にも★3.5でちょうどよかったみたいで安心しました。

H: No.2274 三角彩色 ★★★★
問題リンク：https://yukicoder.me/problems/no/2274 tester：ecotteaさん
幾何、特に代数トポロジーです。単体ホモロジーの典型計算ができるかを問いました。普段は手計算で解かせられるタイプの問題ですが、実装難易度的にも競プロにあっていると思い競プロテイストのクエリ処理に翻訳して出題させていただきました。これまで★4枠には整数論絡みの問題しか出題していなかったのですが、整数論以外のストックも多いのでいつか出題したいと思っていた問題です。抽象的な幾何構造から単体ホモロジーという代数的対象を見出してそこから線形代数で具体的な整数（不変量）を取り出す流れは数学の王道的なアプローチなので、これを機に不変量に興味を持ってくださる競技プログラマーが増えれば幸いです。当初はテストケースがかなり弱かったのですが、testerさんに様々な解法と嘘解法を教えていただきテストケースを強めることができました。グラフを出題する時は嘘解法に強くなるようにジェネリックなケースだけでなくバイアスの強いケースも豊富に取り揃えないといけませんね。

H: No.2274 三角彩色 ★★★★

問題リンク：https://yukicoder.me/problems/no/2274

tester：ecotteaさん

幾何、特に代数トポロジーです。単体ホモロジーの典型計算ができるかを問いました。普段は手計算で解かせられるタイプの問題ですが、実装難易度的にも競プロにあっていると思い競プロテイストのクエリ処理に翻訳して出題させていただきました。

これまで★4枠には整数論絡みの問題しか出題していなかったのですが、整数論以外のストックも多いのでいつか出題したいと思っていた問題です。抽象的な幾何構造から単体ホモロジーという代数的対象を見出してそこから線形代数で具体的な整数（不変量）を取り出す流れは数学の王道的なアプローチなので、これを機に不変量に興味を持ってくださる競技プログラマーが増えれば幸いです。

当初はテストケースがかなり弱かったのですが、testerさんに様々な解法と嘘解法を教えていただきテストケースを強めることができました。グラフを出題する時は嘘解法に強くなるようにジェネリックなケースだけでなくバイアスの強いケースも豊富に取り揃えないといけませんね。

トップページ前の開催記親記事次の開催記