L - Black Market（★3）
- FA：akakimidoriさん（11:15）
アドベコンの題材がなかなか生えなくて困っていたのですが，半分全列挙でいい感じに解けそうな数え上げの問題が生えたので，これを機に出題することにしました．
この問題，実装量が非常に多く，自分でも実装していてかなり大変でした*1．それに加えて，TLがかなり厳しいです．想定解の計算量が である時点でかなり厳しいのに，セグ木かBIT（または平衡二分探索木）を使う必要があり，特にPythonで通そうとすると実行時間ギリギリとなってしまいます．
かといって制約を小さくしたり実行時間を長くすればよいかというとそういうわけでもなく，安易にそうしてしまうと の愚直解が通されかねません．ここの調整が非常に難しく，特にPythonやJavaだと実行時間が厳しかったかと思います（申し訳ございません）．ただ，PythonでもJavaでもACは確認されたので，結果的に特に問題になるほどでもなかったかと思います*2．
このように，方針こそ見えやすいものの実装量多いわTLきついわということで，通常のコンテストで出題するのはけっこうしんどい問題だろうと思い，アドベコンで出題するで正解だったと思います．
解法としては，マージ部分を尺取り法＋セグメント木またはBITで高速化するのが想定でしたが，Binary TrieやWavelet Matrixなど，様々なデータ構造を使った解法がありました（むしろ出題者の私があまりよく知らなかったので勉強したいものです）*3．
当初は難易度は★3.5想定だったのですが，Testerが★2.5～★3を主張していたので★3にして出題することにしました．ただ，実装量の多さからか思ったほどACは出ず，もしかすると結果的に★3.5で出題するのが正解だったかもしれません．難易度調整は難しいものです......．
まとめ
アドベコンで一度は出題したいとは思っていたので，今回は参加できてよかったと思います．強い競プロerのたくさんの方に解いていただいて，私は非常に嬉しい限りです．
来年2～3月にはいよいよ初となる単独コンテスト開催も予定しています．開催できるのが非常に楽しみです．
