JAG 模擬国内予選 2021 参加記
模擬国内、正式名称なんだろう
JAG の模擬国内予選 2021 に参加しました。
具体的には、C と E の原案を提供したり、A から F までの解法や想定誤解法を書いたり、問題文に少しケチをつけたりしました。
C 問題
適当な無考察実装枠を置いておいたら採用されていた。 の bitDP あたりを想定にしてたけど普通にメモ化しない DFS も速くて間に合うらしく実装したらたしかに速かった。
模擬国内、C と E の原案でした
— りあん (@rian_tkb) 2021年10月24日
C は原案時は何のストーリーもつけてなかったけど出来上がった問題文を見てみたらこれ (https://t.co/3YBuUBtOWY) になってて笑った
E は元々 C くらいのつもりで原案を置いておいたらいつの間にか E に置かれていて心配していたけど、結果としては正しかったっぽい
E 問題
別の問題(これは嘘が見つかり爆発した)の部分問題として出てきた問題を切り出して置いておいたら採用されていた。C 問題くらいの難易度だと思っていて実際最初は C 問題に置かれていた気がするが、いつの間にか E に移動していた。
まぁ dp[i][j] = [0, i), [j, N) がそれぞれ両端でソートされている状態でのコストの最小
みたいな方針(これは嘘)に行ってしまうとなかなか戻ってこれなさそうなのもあるしこの AC 数は納得?
自分の書いた原案ページを見たら解法の欄に以下しか書いてなかった、おいおい
解法
- コスト k+1 払いある要素を右または左に k だけ動かす、と考えられる
- 動かす要素数を最小にすると嬉しい
- よって、p の転倒数 + (N - (p の LIS の長さ)) となる
その他の問題
G, H は気が向いたときに実装しようと思っていたら気が向く前に本番当日になってしまった
いつもの
ところで JAG では人材を募集しています。サイコロを転がす問題を作るのが好きな人やサイコロを転がす問題を作るのが好きな人ではない人などの入会をお待ちしています。