yukicoder contest 372のF問題における想定解法の不備について

はじめに

　先日 2023/01/06、yukicoder にて yukicoder contest 372 が開催されました。当コンテストにご参加いただいた皆様、ならびに各問題でtesterを引き受けてくださったkoboshi氏、p-adic氏、mine691氏、taiga0629kyopro氏、Shirotsume氏、37zigen氏、そして本コンテストの全体testerを引き受けてくださったpotato167氏に心より感謝申し上げます。
　さて、本記事では、当コンテストの F問題 Comprehensive Line Segments で発覚した想定解法の不備について、Twitter 等で説明を行うには少々煩雑な内容となるため、この場を借りてその詳細を記そうと思います。

お詫び

　まず、Twitterの方でも謝罪しましたが、この度は想定解法に不備のある状態でコンテストに問題を出題してしまい、誠に申し訳ございませんでした。当コンテストにご参加いただいた皆様に改めて深くお詫び申し上げます。

@yukicoder
昨日実施したyukicoder contestのF問題（https://t.co/UadLMiXuuO）において、想定解に不備が見つかったため、当該問題を「未証明・不備あり問題」に設定しました。
当コンテストにご参加いただいた皆様にご迷惑をおかけし、誠に申し訳ございません。#yukicoder https://t.co/54qBIyoR9Y
— MasKoaTS (@MasKoaTS) 2023年1月7日

不備発覚の経緯

2023/01/06 21:20 ; yukicoder contest 372のF問題を、想定解法に不備のある状態で公開していた。
2023/01/06 23:50 ; 当該問題にclarが 1 件も来ないままコンテストが終了。
2023/01/07 02:10 ; Twitterにてhamamu氏より「F問題の解説が誤っているのではないか」という旨のご指摘をいただく（下記）。

ゆきこFの解説、間違ってないでしょうか…？
図の時、線分3つが答だと思いますが、2本目の線分はどうやっても点1つしか乗らないような？(解説にはどの線分にも2点以上乗せられると書いてある(と思う))
何か勘違いしてるかな… pic.twitter.com/eATYlXYDhK
— hamamu (@hamamu_kyopro) 2023年1月6日

2023/01/07 15:08 ; 当該問題のtesterであるShirotsume氏、potato167氏より連絡をいただき、私が上記ツイートを把握。至急確認を行ったところ、想定解法に不備があることが発覚。
2023/01/07 15:57 ; hamamu氏、toomer氏より、想定解法及び全コンテスト参加者の提出した解答に対する反例となるテストケースをご指摘いただき、当該問題へのテストケース追加とリジャッジを行う。

以下のご指摘にあるケースを当該問題のテストケースに追加いたしました。
ご指摘いただいたhamamu氏、toomer氏に感謝申し上げます。https://t.co/HZ31pGC6vu https://t.co/8STOfKSj97 https://t.co/X0vPC1MD2i
— MasKoaTS (@MasKoaTS) 2023年1月7日

2023/01/07 16:07 ; 想定解法を迅速に修正できる目処が立たなかったため、当該問題を「未証明・不備あり問題」に設定。Twitter上で謝罪を行う（前述）。

不備の詳細

　まず、想定解法に不備のあった yukicoder contest 372のF問題の概要は次の通りです。

　二次元平面上に $N$ 個の点 $P_{i} (1 \leq i \leq N)$ が与えられる。この平面上に $n + 1$ 個の点 $Q_{j} (0 \leq j \leq n)$ を次の条件（以下「包含条件」と呼ぶ）を満たすように配置するとき、 $n$ （正整数）の最小値はいくらか？
・任意の整数 $i (1 \leq i \leq N)$ に対してある整数 $j (1 \leq j \leq n)$ が存在し、点 $P_{i}$ が線分 $Q_{j-1} Q_{j}$ （端点を含む）上にある。

　この問題に対し、コンテスト開催時点での想定解法では、最初に次の定理を主張していました。

定理（※実は誤っている）
　本問題の答えとなる $n$ の最小値を $n^{\star}$ とする。二次元平面上に $n^{\star} + 1$ 個の点 $Q_{j} (0 \leq j \leq n^{\star})$ を配置する方法であって、包含条件と次の条件（以下「特定条件」と呼ぶ）を同時に満たすものが存在する。
・任意の線分 $Q_{j-1}Q_{j} (1 \leq j \leq n^{\star})$ について、点 $P_{1}, P_{2}, \dots, P_{N}$ のうち $2$ 個以上がこの線分の上にある。

　しかし、先のhamamu氏のご指摘にも合った通り、上記の定理は誤っており*1、実際にはどのようにしても 1 個の線分に対して 2 個以上の頂点を乗せられない場合が存在します。
　そして、本問の想定解法はこの定理が正しい場合にのみ有効であるため、テストケースによっては誤った解を出力してしまいます。
　今回、上の定理を正しいとしてしまった原因は、定理が正しいことを保証するために行った次の証明（本問の解説より一部表現を改めて引用）に誤りがあったためです。

上記定理の証明（※実際は誤り）
　問題文の条件を満たすように $n^{\star}+1$ 個の点 $Q_{j} (0 \leq j \leq n^{\star})$ を配置できたとして、これらの点を適切に移動することにより、包含条件と特定条件を同時に満たせることを数学的帰納法で示す。
　各線分の上にある頂点が 0 個の場合は考えなくて良いので、個数が 1 の場合のみを考える。
　まず、線分 $Q_{0} Q_{1}$ において個数が 1 のとき、点 $P_{1}, P_{2}, \dots, P_{N}$ のうち線分 $Q_{0} Q_{1}$ 上にあるものを $p$ 、線分 $Q_{1} Q_{2}$ 上にあって最も点 $Q_{1}$ に近いものを $q$ とすると、点 $Q_{0}$ を点 $p$ 、点 $Q_{1}$ を点 $q$ と同じ位置に移動すれば良い。
　続いて、線分 $Q_{k-1} Q_{k}$ において条件を満たすと仮定し、線分 $Q_{k} Q_{k+1}$ において個数が 1 のとき、点 $P_{1}, P_{2}, \dots, P_{N}$ のうち線分 $Q_{k-1} Q_{k}$ 上にあって最も点 $Q_{k}$ に近いものを $r$ 、線分 $Q_{k} Q_{k+1}$ 上にあるものを $s$ とすると、点 $Q_{k}$ を点 $r$ 、点 $Q_{k+1}$ を点 $s$ と同じ位置に移動することにより、線分 $Q_{k} Q_{k+1}$ においても条件が満たされる。
　以上、数学的帰納法により示された。（証明終）

　上記証明を具体例に対して適用することにより、証明に誤りがあることを示します。以下、具体例として先のhamamu氏のご指摘にもあった次のテストケースを考えます。

　まず、包含条件を満たすように $n^{\star} + 1 = 4$ 個の点 $Q_{0}, Q_{1}, Q_{2}, Q_{3}$ を配置する方法のひとつとして、下の図のようなものがあり得ます。

　この配置方法に対して、先の証明手順を順に追っていきます。
　まず、線分 $Q_{0} Q_{1}$ において、この線分の上にある頂点の個数は 2 個以上なので、この線分に対して操作を加える必要はありません。

　次に、線分 $Q_{1} Q_{2}$ において、この線分の上にある頂点の個数は 1 個です。先の証明に従い、点 $Q_{1}$ を座標 $(3,0)$ に、点 $Q_{2}$ を座標 $(4,4)$ に移動します。
　この操作により、線分 $Q_{1} Q_{2}$ 上にある頂点の個数が 2 個になりました。

　続いて、線分 $Q_{2} Q_{3}$ に着目するとおかしなことが起こります。先程まで線分 $Q_{2} Q_{3}$ 上にあった 6 個の頂点が一気にズレた位置に来てしまっています。
　これは先の操作で点 $Q_{2}$ を移動したことにより、線分 $Q_{2} Q_{3}$ が破壊されたためです。この状態からは、どのように点 $Q_{2}, Q_{3}$ を移動しても包含条件・特定条件を同時に満たすことはできません。

　一般化した形で言い換えると、線分 $Q_{k} Q_{k+1}$ の上に 2 個以上の頂点が乗るように点 $Q_{k}, Q_{k+1}$ を移動したとき、これと連動して 1 つ先の線分 $Q_{k+1} Q_{k+2}$ が破壊されることになります。
　先の証明ではこれを考慮しなかったために、誤った定理を正しいと勘違いしてしまったのです。

不備を防ぐために何をすべきだったか

　まず、本問において、ある解法の正当性を機械的に保証する（愚直解を書く等）ことは非常に困難だと思われます。なぜなら、点 $Q_{j} (0 \leq j \leq n)$ を配置できる場所は二次元平面全体に及ぶ上、点の座標は任意の実数値をとるため、点の配置場所が無数に考えられるためです。
　また、厄介なことに先の定理は大抵の場合において成り立ってしまう*2ため、テストケースの個数を増やせば不備に気づけたかというと、それも怪しいところです。
　しかしながら、改めて先の証明に注目してみると、今回の証明における誤りは、先述のように具体例を考えることによって比較的容易に気付ける可能性のあるものでした。それにも関わらず誤りを見逃してしまったのは、証明の過程において具体例を考えることを怠り、一般化された図形のみに着目してしまったことが一因であると思います。
　したがって、今回の事態に対する教訓としては、想定解法がある定理に依存し、その定理の証明が数学的帰納法のような一般化された形式で表される場合、一般化された事物のみを見るのではなく個別の具体例に対して証明の操作を適用することにより、証明に誤りがある場合これに気付きやすくなり、定理及びその証明の正当性がより盤石なものになるのではないか、ということが言えると思います。

おわりに

　まず、改めて今回の不備に関してお詫び申し上げるとともに、コンテストにご参加いただいた皆様、ならびにtesterを引き受けてくださった方々にお礼申し上げます。そして、今回の不備をTwitterで指摘してくださったhamamu氏や想定解法の反例となるテストケースを追加で提案してくださったtoomer氏をはじめ、様々な方よりご助力をいただき非常に助かりました。こちらに関しても大変感謝しております。誠にありがとうございました。
　また、今回の不備の原因となった定理や証明には多少ad-hocな要素が含まれるため有用性は低いかもしれませんが、今回の事例及び本記事の内容が本記事をご覧いただいた皆様の一助となれば幸いです。
　ここまでご精読いただき、誠にありがとうございました。

*1:厳密に定理が誤りであることを主張するためには「定理が誤りである」ことの証明が別途必要になりますが、本記事では省略します。

*2:実際、コンテスト後に追加を行う前の 26 個のテストケースすべてにおいて先の定理は成り立ちます。コンテスト中にclarが 1 件も来なかったことも反証の難しさを物語っていると言えそうです。