JAG夏 2018 Day2 準備記

！！！解法のネタバレが含まれます！！！でも解説ではないです！！！

yosupo, sigma, sugim, maroonでJAGの夏合宿を1セット作りました

経緯

petrozavodsk(ロシア)では、毎年競プロの合宿が行われています。ロシアなので人外ばっかりいるので、セットもそれ相応の難易度になっています。 そこにyosupo, sigma, sugimでセットを作って送ろうという話があったのが始まりです。全部で11問作りました。

そのうち8題を選んで、最初に2題追加したのがAPC001です。残りの3題に、最初に問題を8題追加したのが今回のセットです。 逆に言うと、APC001から最初の2題抜いて、今回のセットの3題(Knapsack And Queries / Construct One Point / ADD DIV MAX(petrozavodskの時点ではRESTOREは無かった))を足したのがpetrozavodskに送ったセットです。

とんでもない難易度に思えますがpetrozavodskだと9問解かれるらしいです→(http://karelia.snarknews.info/index.cgi?data=macros/day&menu=index&head=index&sbname=2018w&class=2018w&round=03)。 ロシアはすごいですね(上のアルファベットにカーソルを合わせると問題名が見えます)。

夏合宿

箇条書き

  • maroonはなんか流れで巻き込みましたが、結果的には相当作問してくれました。ありがとうございます。

  • インターンシップを始めたら全然時間がとれなくなって、Fのデータ作成が炎上しました

  • ↑は諦めるという手法を取ることにより鎮火しました、実はケースがクソザコです(ごめんなさい…)

  • 突然数日前に英語をつけよう！という話になり、英語がつきました。maroonが大量の英語を書きました。

  • 前日の夜にJAGに英文校正頼む！って言ったらしてくれて、かなり大量の指摘をいただきました。JAGの方々本当にありがとうございます。(修正前に問題文は印刷されたので、合宿に来た方は見比べると指摘されたところがわかります)

  • 風船はやっぱり配りたいなってなって、FAだけ配ることにしました。D以降は全部行けそうだったので全部配りました。

問題の感想

自分が関わった問題の感想を述べます。

Knapsack And Queries

Q=1ならばなんの変哲もないDPです。 クエリに答えるために要素を分割したくなるのですが、DPテーブルのmergeにminの畳み込みみたいなのが欲しくなります。そしてこれは厳しいことで有名です。ですが実は、DPテーブルが2個に分割されていても、高速にクエリに答えられるという性質が有ります(3個以上だとだめです)。

よって2個までなら分割できて、queueを2個に分割というと知っている人は知っているテクニックになります。僕は大学の授業でやりました。

これは解法ドリブンで作りました。queueを2個に分割というのは昔から出したかったテクニックなのですが、うまく出題できたと思います。

Point Sequences

数ヶ月前にひたすら幾何精進をしていた時期があります。 その時期に、幾何問題のepsの設定を、雰囲気submit連打ではなく理論立てて設定できないか色々考えたことがあります。 その結果として、この問題の漸化式のような単純な操作をするだけでも爆発するから、深く考えても仕方がないという結論になりました。

ですが逆手に取って、この漸化式から問題を作れないか(そして普通にdoubleで計算すると爆発するんですよ〜ってイキれないか)考えました。 直線の交点は連立方程式という昔習った知識を思い出し、連立方程式ならmodで面白いことが出来ないかと思い、問題が出来ました。

一発ギャグみたいな問題で、どのぐらい解かれるか予想できずに不安だったのですが、思ってたのと同じぐらいの解かれ具合だったのでよかったです。

Construct One Point

三角形の内側の点を一点構成するだけというシンプルな問題です。よく考えるとピックの定理を検索できないという条件下だと厳しかったかもしれません。

これは3人でいたときに適当にみんなで問題設定を考えて、うまく解けたので出しました。

ADD DIV MAX RESTORE

petrozavodskに出したときはADD DIV MAXでした。ですがpetrozavodskの中国ミラーで11分で解かれた(！？)ので、何かと思ったらsegment tree beatsというテクニックで解けたようです。11分で解いたのはsegment tree beatsの記事を書いた人のチームでした。なのでRESTOREがつきました。

今回作った中で、一番好きな問題です。一見不可能にしか思えないんですが、実は物事がすべてうまくいって、結局普通の遅延伝播segtreeを書くだけになります。 「長さNの数列が与えられます。以下のクエリをQ個処理してください。type1: L, Rが与えられるので〜」みたいな問題文で、しかも考察がボス問級に難しいという問題はずっと作りたかったので、作れて満足です。

AB Sort

とりあえず適当に操作を考えた後、sigmaとこれのいい性質無いかな〜って考えたらsigmaが見つけました。で、その性質を活かすために、クエリを追加しました。

クエリは何も考えずにAB反転にしたんですが、もう少し簡単なクエリでよかったかもしれません。

問題案が十分だったこととか、データ構造が多かったこととか、なんか近い問題が直前に出たとかで、petrozavodskには送らずボツ担ってた問題です。 準備はしてあったので今回は使うことにしました。