diverta 2019 Programming Contest

kroton @kroton_pc

挿入DPとか考えると挿入によってすでに成立している関係をぐちゃぐちゃになってしまうけど、とりあえず後ろにくっつけてその後どれかとswapするとすれば動くのが2点だけになってかなりハッピーになる

kroton @kroton_pc

挿入DPもこのDPも1~nのランダムな順列から1~n+1のランダムな順列を作る方法から考えられそう これ以外にもバリエーションありそう

kmjp @kmjp_pc

ようやく先日のdiverta F通った。ゼータ変換周りとかはちゃんとできてたのに、英語版Editorialでいうsの遷移が求められなかったのが残念。

kmjp @kmjp_pc

ところでEditorial、黒玉につながる白玉は先に並べるんだよね、だとするとサンプルの並び順は5.8.4.9.6...ではなく8,5,9,6,4...じゃない？先に黒をおくと、白は左端におけないので置き方は(n+1)通りじゃなくn通りだと思うのだけど。

kmjp @kmjp_pc

AtCoderはたまにEditorialに変数の誤りや値の1ズレの誤りがあって、「Editorial通りのコードってあるのかな？」と気になる。そこらへんもあるので、本当はEditorial通りのACコード出してほしいんだよね。

kmjp @kmjp_pc

sの遷移がしっくりこず、けんちょん氏のブログ記事をしばらく眺めてて、黒玉のずれ分の総和がs増えることが理解できた（黒玉の位置＝左に白玉を置ける選択肢の数なのでs通りになる）。これ本番思いつく気がしないなぁ。

kmjp @kmjp_pc

Editorialの解説量の十分不十分は意見も分かれるとこだと思うけど、自分も（他のコードとか参考にしつつも）苦戦しながらもどうにかこうにか解けているので、結果的に最低限の内容は書かれているってことなのかな。

kmjp @kmjp_pc

AGCとかだと最近海外勢も多いので、高難易度帯でも色々コードを参考にできるんだけど、国内企業コンの高難易度帯がACコードほとんどなくてしんどいのよね。

kmjp @kmjp_pc

前も書いたけど最近でEditorial付でもしんどかったのはCode Festival 2018のComplicated Operations。Editorialがかなり省略されているし、参考コードはほとんどないし長くて何をやっているかわからないし…。

kmjp @kmjp_pc

Codeforcesのように、コンテスト毎にEditorialの誤りとか別解とか話せるようなコメント機能やページがあればいいのかもしれないけど、AtCoder本体でそういうの置く気はなさそうだしなぁ。

kmjp @kmjp_pc

「ほぼ先ほどと同様のDP」でキレかけるのわかる（自分もそこで詰まったので）

kroton @kroton_pc

SRM592 div1 Med - LittleElephantAndPermutationDiv1 community.topcoder.com/stat?c=problem… これ箱根DPで解けた 2つの順列をマッピングする問題は箱根DP使えそう

kroton @kroton_pc

箱根DP func(i, j, k) = 今 i 番目で, j = #(左側、i番目より下でまだペアになっていない箇所), k = 右側で とおいて左右のi番目を同時に考えるとfunc(i + 1, j, k), func(i + 1, j - 1, k - 1), func(i + 1, j + 1, k + 1) にしか遷移しないことがわかるので func'(i, j) みたいに計算すればO(N^2)

kroton @kroton_pc

LittleElephantAndPermutationDiv1 はこれに和も載せればいいので O(N^4) で解ける

kroton @kroton_pc

順列が絡む数え上げは、個数をベースとした状態に落としていかないといけないね

kroton @kroton_pc

2つの順列の組み合わせの作り方いろいろ 1. 順列1と順列2を並行して回す 2. 順列1を固定して順列2を回したあと順列1を回す 3. 順列1, 順列2を固定してマッピングを考えて最後に順列1 or 2を回す

kroton @kroton_pc

順列完全に理解した

kroton @kroton_pc

追加 - swap dp - 箱根DP

kmjp @kmjp_pc

はてなブログに投稿しました #はてなブログ diverta 2019 Programming Contest: D - DivRem Number - kmjp's blog kmjp.hatenablog.jp/entry/2019/05/…

kmjp @kmjp_pc

はてなブログに投稿しました #はてなブログ diverta 2019 Programming Contest: E - XOR Partitioning - kmjp's blog kmjp.hatenablog.jp/entry/2019/05/…