yukicoder contest 412（基礎論コンテスト）開催記

2023/11/10

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

２ヶ月ちょっとぶりのコンテストです。ただしtesterさん募集は５月から、作問自体はもっと前からしていたので、このコンテストは半年越しで準備していたことになります。競技プログラミング歴が１年ちょっとなので、その半分くらいの期間もこのコンテストの準備をしていたと思うと感慨深いですね。

最近は典型アルゴリズムを直接分かりやすく問う問題を作るのが好きで、今回もD問題に素集合データ構造の典型問題を入れさせていただきました。これまで学んできたアルゴリズムの中で、単純な好みで言えばフェニック木が一番思い入れがあって好きですが、好みとは別に「頭の中でする数学」と「計算機に任せる数学」をうまく橋渡ししてくれていて凄いなと感じているのが、素集合データ構造と二部マッチングです。これらの魅力を数学者の方々にも伝えたいな、という思いを込めて問題を作らせていただきました。

またフェニック木が好きなせいで多くの区間処理をフェニック木に任せてしまっておりこれまでセグメント木を全然使わないで来たのですが、そんな中で平方分割に出会ったらフェニック木で処理しにくくてセグメント木で処理できるクエリも平方分割でも割りと処理できることが分かってしまい、ますますセグメント木を使う機会がなくなってしまいました。せっかくなのでセグメント木よりも平方分割で処理しやすい問題を作りたいな、と思ったのが今回のH問題作問のきっかけです。

勉強するとその概念が好きになる傾向が強く、そしてアルゴリズムに思い入れが出るとすぐ作問したくなってしまいます。結局同じノリで解析コンテストと幾何コンテストの問題も揃えてしまいました。まだtesterさんが見つかっていませんが、無事見つかれば近いうちにそれらも開催したいなと思っています。

今回も大きな事故はなく済んで良かったです。D問題でWAの割合が多くて少し焦りましたが、スペシャルジャッジ問題なので許してもらえる範疇だと信じております。参加者の皆様、testerの皆様、そして色々とご相談に乗ってくださった方々にこの場でお礼申し上げます。

今回は基礎論コンテストという趣旨でセットを組ませていただきました。一言に基礎論と言っても色々ありますが、競技プログラミングにおける代数構造の使い方がとてもおもしろいと思っている事情で論理演算の代数的性質を問う問題を多めに投入させていただきました。解説もかなり詳しめに書いたので、解けた人でもぜひお読みいただければ嬉しいです。

以下、各問題の雑感です。

A問題：⇒の実装練習
B問題：実行して解く停止性
C問題：対偶と否定でXOR
D問題：⇔と連結性
E問題：ド・モルガン
F問題：グランディ数∞
G問題：準同型で解く停止性
H問題：⇒∧∨が乗るデータ構造は？

A: No.2533 A⇒B問題 ★
問題リンク：https://yukicoder.me/problems/no/2533 tester：hiro1729さん
まずは論理の基礎の１つ、「ならば」の計算問題です。ただbool値を計算させるだけでも良いのですが、bit演算で論理演算が処理できることを解説で学べるように並列可能な問題にしました。 ★1にしてはやや読解が大変かなと思いましたが、正答率は十分高かったので安心いたしました。

A: No.2533 A⇒B問題 ★

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

tester：hiro1729さん

まずは論理の基礎の１つ、「ならば」の計算問題です。ただbool値を計算させるだけでも良いのですが、bit演算で論理演算が処理できることを解説で学べるように並列可能な問題にしました。

★1にしてはやや読解が大変かなと思いましたが、正答率は十分高かったので安心いたしました。

B: No.2534 コラッツ数列 ★☆
問題リンク：https://yukicoder.me/problems/no/2534 tester：srjywrdnprktさん、hiro1729さん
基礎論の重要な問題の１つが停止性問題です。最初に最も簡単な停止性問題の練習として、実際に停止するかを実行して有限ステップ試してみるタイプの実装問題を入れてみました。コラッツ数列と言えばshobonvipさんですよね、と思っていたらまさにその通りshobonvipさんがfastestを取っていてさすがだと思いました。

B: No.2534 コラッツ数列 ★☆

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

tester：srjywrdnprktさん、hiro1729さん

基礎論の重要な問題の１つが停止性問題です。最初に最も簡単な停止性問題の練習として、実際に停止するかを実行して有限ステップ試してみるタイプの実装問題を入れてみました。

コラッツ数列と言えばshobonvipさんですよね、と思っていたらまさにその通りshobonvipさんがfastestを取っていてさすがだと思いました。

C: No.2535 多重同値 ★★
問題リンク：https://yukicoder.me/problems/no/2535 tester：kumakumaさん、hiro1729さん
ここから少し難しくなって、論理演算の代数構造を考察してもらう問題です。「同値である」という関係はbool値の二項演算だと思えて、そうみなした時にどんな代数構造であるかを考えることで問題を高速に解くことが可能となります。考察には対偶などのテクニックを使うことができ、良い頭の体操になると思います。代数構造の持つ性質を使って本来は計算量の重い処理を計算量の軽い処理に変換する、という考え方は累積和やフェニック木やセグメント木などを抽象的に学んでいく際に必要になっていくため、この問題でそういった意識を（特別なデータ構造なしで）学べればと思いこの問題を出題しました。毎度ながらfastestの速さに舌を巻きましたが、fastestだけでなく非常に多くの人達が恐ろしいスピードで解いていったのでひたすら感心していました。皆さんの考察のコツを教えていただきたいです。

C: No.2535 多重同値 ★★

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

tester：kumakumaさん、hiro1729さん

ここから少し難しくなって、論理演算の代数構造を考察してもらう問題です。「同値である」という関係はbool値の二項演算だと思えて、そうみなした時にどんな代数構造であるかを考えることで問題を高速に解くことが可能となります。考察には対偶などのテクニックを使うことができ、良い頭の体操になると思います。

代数構造の持つ性質を使って本来は計算量の重い処理を計算量の軽い処理に変換する、という考え方は累積和やフェニック木やセグメント木などを抽象的に学んでいく際に必要になっていくため、この問題でそういった意識を（特別なデータ構造なしで）学べればと思いこの問題を出題しました。

毎度ながらfastestの速さに舌を巻きましたが、fastestだけでなく非常に多くの人達が恐ろしいスピードで解いていったのでひたすら感心していました。皆さんの考察のコツを教えていただきたいです。

D: No.2536 同値性と充足関係 ★★☆
問題リンク：https://yukicoder.me/problems/no/2536 tester：hiro1729さん、遭難者さん
★2.5からはデータ構造の練習問題も入れていきます。この問題は素集合データ構造を用いる典型問題ですが、競技プログラミング未経験の数学者だと手掛かりがなく非常に難しい問題になると思います。一方で一度この手の典型問題の解法を学んでしまえば素集合データ構造が複数の等式の成否そのもの（各変数の値を決めた時点で即座に定まるもの）複数の等式の成否の実際の計算（各変数の値を決めても実行に無視できない時間がかかるもの）違いを埋めてくれるということの理解に適していると思い、今回も出題させていただきました。競技プログラミングに慣れている人にとっては典型問題の速解き練習として役に立ってくだされば幸いです。 ……と思っていましたがサンプルが弱かったのか、スペシャルジャッジ問題のデバッグの難しさが出たのか、出力の形式に従っていなかったのか（末尾に余計な空白を入れた人が多かったのかも？）、WA率が非常に高い問題になってしまい申し訳ございません。次からはスペシャルジャッジ問題では出力形式の指定通りに出力することや末尾に余計な空白を入れないことを強調して出題しましょうかね。。

D: No.2536 同値性と充足関係 ★★☆

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

tester：hiro1729さん、遭難者さん

★2.5からはデータ構造の練習問題も入れていきます。この問題は素集合データ構造を用いる典型問題ですが、競技プログラミング未経験の数学者だと手掛かりがなく非常に難しい問題になると思います。一方で一度この手の典型問題の解法を学んでしまえば素集合データ構造が

複数の等式の成否そのもの（各変数の値を決めた時点で即座に定まるもの）
複数の等式の成否の実際の計算（各変数の値を決めても実行に無視できない時間がかかるもの）

違いを埋めてくれるということの理解に適していると思い、今回も出題させていただきました。競技プログラミングに慣れている人にとっては典型問題の速解き練習として役に立ってくだされば幸いです。

……と思っていましたがサンプルが弱かったのか、スペシャルジャッジ問題のデバッグの難しさが出たのか、出力の形式に従っていなかったのか（末尾に余計な空白を入れた人が多かったのかも？）、WA率が非常に高い問題になってしまい申し訳ございません。次からはスペシャルジャッジ問題では出力形式の指定通りに出力することや末尾に余計な空白を入れないことを強調して出題しましょうかね。。

E: No.2537 多重含意 ★★☆
問題リンク：https://yukicoder.me/problems/no/2537 tester：hiro1729さん、遭難者さん
C問題（多重同値）の姉妹問題です。ただしC問題は「同値である」の定める二項演算の代数構造を調べるだけの問題でしたが、こちらは難易度が上がって「ならば」の定める代数構造（あまり性質が良くない）を別の良い代数構造に翻訳して処理する必要があります。そこで役立つのが、「または」を用いた「ならば」の言い換えです。「または」の定める二項演算は性質が良く、しかもド・モルガンの法則を使って「かつ」にも言い換え可能です。数え上げ問題では「または」の処理がやや面倒ですが、「かつ」の処理は比較的容易なので、後は余事象の数え上げ問題を考えれば良いことになりますね。というわけでこの問題は「ならば」の言い換えド・モルガンの法則による「または」と「かつ」の言い換え余事象の数え上げという基本テクニックの詰め合わせ問題でした。１つ１つは気付きやすいかもしれませんが、３つ合わさると骨のある考察になったのではないでしょうか。

E: No.2537 多重含意 ★★☆

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

tester：hiro1729さん、遭難者さん

C問題（多重同値）の姉妹問題です。ただしC問題は「同値である」の定める二項演算の代数構造を調べるだけの問題でしたが、こちらは難易度が上がって「ならば」の定める代数構造（あまり性質が良くない）を別の良い代数構造に翻訳して処理する必要があります。

そこで役立つのが、「または」を用いた「ならば」の言い換えです。「または」の定める二項演算は性質が良く、しかもド・モルガンの法則を使って「かつ」にも言い換え可能です。数え上げ問題では「または」の処理がやや面倒ですが、「かつ」の処理は比較的容易なので、後は余事象の数え上げ問題を考えれば良いことになりますね。

というわけでこの問題は

「ならば」の言い換え
ド・モルガンの法則による「または」と「かつ」の言い換え
余事象の数え上げ

という基本テクニックの詰め合わせ問題でした。１つ１つは気付きやすいかもしれませんが、３つ合わさると骨のある考察になったのではないでしょうか。

F: No.2538 2進元ゲーム ★★★
問題リンク：https://yukicoder.me/problems/no/2538 tester：hiro1729さん、ecotteaさん
ここから２問ゲーム問題が続きます。まずは２人プレイヤーのゲームで、ニムの亜種です。ニムと同様にグランディ数を処理する問題ですが、負数が成分に複数ある場合の考察が非自明です。ちなみにグランディ数のより高度な使い方をすれば、負数が成分に複数ある場合も統一的に処理でき考察を減らすことが可能です。この手の処理はより高難易度の枠で出題したことがありますが、★3を解ける人たちにもアウトリーチする機会があった方が良いと思ったのが出題のきっかけで、解説に別解として説明させていただきました。なので解けた人も是非解説をお楽しみください。

F: No.2538 2進元ゲーム ★★★

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

tester：hiro1729さん、ecotteaさん

ここから２問ゲーム問題が続きます。まずは２人プレイヤーのゲームで、ニムの亜種です。ニムと同様にグランディ数を処理する問題ですが、負数が成分に複数ある場合の考察が非自明です。

ちなみにグランディ数のより高度な使い方をすれば、負数が成分に複数ある場合も統一的に処理でき考察を減らすことが可能です。この手の処理はより高難易度の枠で出題したことがありますが、★3を解ける人たちにもアウトリーチする機会があった方が良いと思ったのが出題のきっかけで、解説に別解として説明させていただきました。なので解けた人も是非解説をお楽しみください。

G: No.2539 スライムゲーム ★★★☆
問題リンク：https://yukicoder.me/problems/no/2539 tester：ecotteaさん
続くもう１問目のゲーム問題は操作選択権のあるプレイヤーが存在しないゲームなので、停止性問題の一種となります。ただしB問題（コラッツ数列）と違って最大ステップ数は$10^{18}$と大きく、単純に実行してみる解法では実行時間制限内に解くことができません。代わりにゲームを他の分かりやすい等価な処理に変換して解けばよく、そのような変換をより一般化した概念が準同型です。準同型は競技プログラミングで頻繁に出くわす割にあまり明示的に言及されないので、作問で使うたびになるべく解説で触れるようにしています。

G: No.2539 スライムゲーム ★★★☆

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

tester：ecotteaさん

続くもう１問目のゲーム問題は操作選択権のあるプレイヤーが存在しないゲームなので、停止性問題の一種となります。ただしB問題（コラッツ数列）と違って最大ステップ数は$10^{18}$と大きく、単純に実行してみる解法では実行時間制限内に解くことができません。

代わりにゲームを他の分かりやすい等価な処理に変換して解けばよく、そのような変換をより一般化した概念が準同型です。準同型は競技プログラミングで頻繁に出くわす割にあまり明示的に言及されないので、作問で使うたびになるべく解説で触れるようにしています。

H: No.2540 同値性判定 ★★★☆
問題リンク：https://yukicoder.me/problems/no/2540 tester：CuriousFairy315さん
最後は「ならば」と「かつ」と「または」と「同値である」が総動員された問題です。C問題（多重含意）とE問題（多重同値）で示唆したように、論理演算の代数的性質に注目することで未知を切り開くことができます。とはいえ複数種類の論理演算を同時に区間処理で扱うには非自明な計算が必要なので、それら２問よりは格段に難易度が高くなっていると思います。この問題は想定解がマグマから集合への作用を用いたもので、モノイドからの作用にのみ慣れている人には多少目を引くものになってくれたのではないでしょうか。またAtCoder Libraryのドキュメントで遅延セグメント木に不要な要件が（恐らく分かりやすさのために）色々とついていたので、遅延セグメント木や双対セグメント木や平方分割による区間作用ではそういう条件を外せるという学びを提供できればと思い今回作問させていただきました。それにしてもちゃんとコンテスト中に解かれて安心しました・・。

H: No.2540 同値性判定 ★★★☆

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

tester：CuriousFairy315さん

最後は「ならば」と「かつ」と「または」と「同値である」が総動員された問題です。C問題（多重含意）とE問題（多重同値）で示唆したように、論理演算の代数的性質に注目することで未知を切り開くことができます。とはいえ複数種類の論理演算を同時に区間処理で扱うには非自明な計算が必要なので、それら２問よりは格段に難易度が高くなっていると思います。

この問題は想定解がマグマから集合への作用を用いたもので、モノイドからの作用にのみ慣れている人には多少目を引くものになってくれたのではないでしょうか。またAtCoder Libraryのドキュメントで遅延セグメント木に不要な要件が（恐らく分かりやすさのために）色々とついていたので、遅延セグメント木や双対セグメント木や平方分割による区間作用ではそういう条件を外せるという学びを提供できればと思い今回作問させていただきました。

それにしてもちゃんとコンテスト中に解かれて安心しました・・。

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