yukicoder No.406, 407コメンタリー(?) - はむ吉（のんびり）の練習ノート

f:id:hamukichi_nbr:20160805200902p:plain *1

8月5日から翌6日にかけて開催されたyukicoderのコンテストに、私が作成した二つの問題、「鴨等間隔の法則」(No.406)および「鴨等素数間隔列の数え上げ」(No.407)を出題していただきました。この記事では、作問の経緯や、考えたことなどを書きます。なお、両問題のネタバレを含むので、ご注意ください。また、両問題の解説は、この記事ではなくyukicoder上に記しています。

鴨等間隔の法則 (No.406)
鴨等素数間隔列の数え上げ (No.407)

鴨等間隔の法則 (No.406)

問題案ができるまで

作問ははじめてだったので、まずは易しい、★1程度の問題を形にすることにしました。その結果としてできたのがこの問題です。

この問題は、題材とするアルゴリズムを決めてから作り上げていったものではなく、思い浮かんだタイトルから発展させたものです。今となってはなぜだかわかりませんが、鴨川等間隔の法則が浮かびました。当初はその通りのストーリーにしようとしていましたが、あまりにも安易である気がして、カップルの代わりに鴨を登場させ、こじつけました。

テストケースの作成

この問題を作る際に少し難しかったのが、判定に用いるテストケースの作成でした。問題の性質上、疑似乱数を用いて適当に数列を作成すると、十中八九答えがNOになってしまいます。言い換えると、答えがYESとなる数列をつくるには、初項や公差の満たすべき条件をよく考える必要があります。実は、このときの取り組みが、次のNo.407へとつながりました。

解法

私が思いついたのは、解説のはじめに記した、集合を用いた $O(N \log N)$ 解だけでした。その後、Testerを担当してくださったbtkさんに、集合を用いないより効率の良い $O(N \log N)$ 解と、等差数列の性質を巧みに利用した $O(N)$ 解をいただきました。勉強になりました。

反省点

タイトルからやや無理やり作問したため、やや不自然な問題設定になってしまいました。また、必ずしも昇順や降順にはせずに数列を与えることで少しひねりましたが、そのために「隣り合う」の意味合いが分かりにくくなったかもしれません。

鴨等素数間隔列の数え上げ (No.407)

問題案ができるまで

先ほど書いたように、この問題は前問のテストケースを作成しているときに思いついたものです。新しくストーリーをつくるべきかと思っていましたが、最終的に前問と同様のストーリーとなりました。読み方は「かもとうそすうかんかくれつ」です。変なタイトルですみません。

想定解の作成と制約の設定

実は、当初は解説に記した解法ではなく、次の回りくどい方法を想定解としていました。制約も $L\le 5 \cdot 10^6$ 程度でした。

初項 $x_0$ のとりうる最大の値 $X'_\mathrm{max} := L - N + 1$ を求める。計算量 $O(1)$ 。
$D_\mathrm{max}(x_0) = \lfloor (L - x_0) / (N - 1) \rfloor$ と定め、 $D_\mathrm{max}(0)$ 以下の素数を列挙する。Eratosthenesの篩によれば計算量 $O(D_\mathrm{max}(0)\log\log D_\mathrm{max}(0))$ 。
得られた素数表から、素数計数関数 $\pi (k)$ の値を $k\le D_\mathrm{max}(0)$ について求める。計算量 $O(D_\mathrm{max}(0))$ 。
$M_{N, L} = \sum _{x_0 = 0} ^ {X'_\mathrm{max}} \pi (D_\mathrm{max}(x_0))$ を計算する。計算量 $O(X'_\mathrm{max})$ 。

テストケースを作り始めてから、現在の想定解に気づきました。制約も見直しましたが、やや軽率だったかもしれません。

反省点

前問の設定を引きずっていることも一因ですが、この問題の設定はかなり不自然になってしまいました。また、題材によるものなのかもしれませんが、問題文・解説ともに数式まみれになりました。

さらに、ご指摘がありましたが、制約を大きくしすぎたようです。想定解によれば一応PyPy3やRubyでも解けるようにしたはずなのですが、それでも時間制限等の面で厳しかったかもしれません。申し訳ありません。言語によっては、同じアルゴリズムでもコードの書き方（実装）により実行時間が改善されることがあるとはいえ*2、ギリギリだったのは確かです。もう少し慎重に制約・時間制限を定めるべきでした。ご迷惑をおかけしてすみませんでした。

標準ライブラリを使う例として、また一部の関数型言語でも通ることの確認としてScheme (Gauche)解も示しましたが、これは蛇足だったかもしれません。

おわりに

問題を解くことだけではなく、作問することも、競技プログラミングの勉強になると感じました。緻密に解法を組み立てる力や、計算量について考える力が少し養われた気がします。また、Testerさんとのやりとりを通じて、自分では思いもつかなかったような考え方に触れることができました。今後も、また機会があれば、作問させていただきたいと考えています。

それとともに、作問の難しさも認識しました。特に、入力値の制約や時間制限の設定には、十分注意を払う必要があると痛感しました。ご指摘ありがとうございました。

yuki2006さん、Testerのbtkさん、そしてこれらの問題に取り組んでくださったみなさん、ありがとうございます。

*1:かわいいフリー素材集いらすとやさんの素材を使いました。

*2:たとえば、Pythonの場合には、普通にfor文で書くよりも、内包表記を使ったほうが高速になりそうです（私の主観です）。Rubyでも同様のことがありそうです。