競プロさぼりすぎてた
個人的にはこの前の学生最強コン本選以来、1 か月ぶりのプロコン。rated に限ればほぼ 2 か月ぶりという堕落したありさまでしたが、なんかこれもオンサイトの権利が得られるかもしれないということで、参加してみました。
参加前
どうやら国内 200 位までが本選通過らしいとのこと。学生最強コンは国内「学生」200 位までだったので、やや通過基準が厳しくなってる？まあいいや。ひとまず通過を目指します。
配点は 1+3+6+6+7+14. 14 はしんどそうなので最初 5 問が勝負。これを全部解けばさすがに通過できそうだけど、進捗サボり野郎にはつらそう。1+3+6+6や1+3+6+7でお祈りできたらいいなぁ、普通に1+3+6とかもありそうだなぁ、とか思ってました。
試験の経過
A 見る。はい。書く→AC (1:15)
B 見る。300 で木の数え上げとかやめてくれ～。と思ったけど、例を見てなんだかけ算するだけかと気付く。実装もたもた→AC (11:11)
C, D, E見る。どれもぱっと見よくわからんが、できそうな見た目はしている。
C 考える。は？とりあえずソートしてマジョライズしてなければ終わりなのはいいけど、N-2 回はよくわかんね。まあいいや、一旦パス。
D 考える。グラフの最短路ならダイクストラか、でも辺数が多いやん、うまいこと減らせないかな。新しい頂点付け加えようとしたけどだめ。
やめややめ。じゃあ普通にDPできひんのかな。ん？最初の方から更新していけばよくね？区間全体で更新なんで、遅延セグ木でできそう！
ここからソート＆脳死遅延セグ木で通す。紙に添え字丁寧にメモったり、遅延セグ木の取扱説明書をまったり読みながら書く。通ってくれ～→通ったわ (46:01)
ここで順位表を見ると、C が全然解かれてなくて D がめっちゃ通されてるのを確認する。まあそうなるわな。そして、最近橙になった maspy さんが上位にいて、C をパスして E を通しているのを見る。タイプ的にこれ E ワンチャンあるのでは？と C に戻らず E に進むことに。
E 考える。全部足せば自明な全体制約あり。なのであとは構成できるか。ひとまず N=5, K=3 が境界のケースだけど、うまいことやったら一般化できそうな構成できた！N=7, K=4 でも同様にいくことを確かめ、これで N が奇数は勝利。あとは N が偶数のケースで、この場合は N=4, K=2 とかが境界だけど、これも奇数ケースみたいな感じで構成できた。一応 N=6, K=3 でもチェックしてよさそうとわかる。
あとは実装するのみ。というか真面目に構成した三つ組を書き下すのみ。紙に書いてもたもたしながらも実装。そしてお祈り→AC！(76:40)
この時点で順位を見ると 64 位。あれこれもう勝ったのでは？1+3+6+6に時間関係なく勝てるのが大きい。経験則的に、ここから C を通しにいってもうま味が少ないなぁと思いつつ、かといって F はさすがにしんどそうということもあり、モチベが大幅減少しながら C を考える。
C 再考。一応 N-2 回でできない反例として 2341/1234 などがある。要するにサイクルが 1 個だとダメ、2 個以上だと OK. ということを思いつく。でも実際は B の大小との兼ね合いがあって考えるのがだるいな～となり、ここで飽きる。ひどい。
このへんであと 20 分くらいだったけど、ここからは動画見たりミーム画像探してツイートの準備をしたりしてました。カス競プロerの鑑。
76分で1+3+0+6+7したぼく pic.twitter.com/J6b17pHfsO
— SP1 (@SP1_winter) November 9, 2019
↑準備したツイート
問題の振り返り
A はい
B なんか実装が遅かったのは、明らかにトレーニング不足です。すいませんでした。
D
遅延セグ木にたどり着いたのはよかった。ちゃんと書くと
・あらかじめ区間を、端点をペアにして辞書式にソートしておく (左端優先)。
・各点の距離 d[i] を d[i] = inf で初期化
・頂点 0 (0-indexedに置き換えた) について d[0] = 0にする
・区間を順に適用する。それぞれ、左端の距離を取ってきて、C を足し、左端以外に min を適用。
・全部やって、d[N-1] が答え (infなら到達不可能なので -1)
という手順。区間更新するので遅延セグ木ですね。
ソートはペアにしてmultisetを用いてやったけど、いまだにいいやり方はわかんない (これでできるならいい気もするけど)。
実は最小性証明してないけど、さすがにいいんじゃないかなぁという気がする。というか d[i] の単調性と区間ソートのおかげでさすがに最小か、そうか。
ところで、本番ではなんとなくダイクストラでできるかもなーと思ったものの断念してましたが、なんとやっぱりできるそうです。やり方は、L から R にコスト C の辺を張り、各 i から i-1 のコスト 0 の辺を張るというもの。天才か？コスト 0 の辺は重なるので個数が O(N+M) になると。なるほどな～逆辺を張るアイデアなかったわ～～覚えとこ～～～。
E
sum {a[i]+b[i]} <= sum {c[i]} なので、3N 個のうち後ろ N 個の和だけで全体の半分以上になる必要がある、というのがすぐにわかります。真面目に式を立てて計算すると K<= (N+1)/2 が得られます。本番は計算せーへんかったけどな！
これがわかれば後は構成するのみ。具体的に書き下すのはかったるいので省略しますが、一応境界での構成を書いておくと
N=5, K=3 で 3,5,7,4,6 と 10,9,8,12,11 と 13,14,15,16,17
N=6, K=3 で 3,5,7,4,6,8 と11,10,9,14,13,12 と 15,16,17,18,19,20
みたいにするとよいです。
C
まず A, B ともにソートしてから B が A をマジョライズしてないとダメなのはよく、一方マジョライズしているとして、A についてソートした順列への置換がサイクル 2 個以上に分解できるなら OK なのもよいです。
問題はサイクル 1 個の時の細かい制約。実際には、ソート後の列を SA, SB として、SA[i+1]>=SB[i] となる場所があればスワップを一回以上スキップできてOK, そういう場所がなければどうしても N-1 回必要となる、というものでした。こういう細かいところを詰めるのが今後の課題ですかね。なお実装はサイクルチェックがややだるそうですが、これも難なく実装したいところ。忘れたころにもっかい解いてみるか...
F は、もっと強くなってからのお楽しみ...
結果
ABDE の 4 完で 133 位、国内 95 位でした。やったね！
パフォーマンスも 2437 と過去最高、初の橙ぱふぉで、rate も 1931 で highest を更新しました。黄が見えてきた。
いいことずくめでしたが、勝因は問題セットの相性のよさでしょう。つまりは運。算数パズルありがとう！takayutaとmasさんありがとう！！お祈り力を鍛えよう！！！ ...というのはさておき、順位表をちゃんと眺めたのはよかったと思います。
最近の立ち回りは「人より実装が遅いことを受け入れ、着実にACを重ねる」というもので、考察を真面目にやったり添え字などもメモしたり、丁寧にやってるのがここのところうまくいってる気がします。参加回数は少ないけどね。なんというか、いままでパズルコンテストと思っていたものを、数オリだと思うようにしてから落ち着いて臨めるようになったというか。人は何歳からでも成長できる。
でも、まだまだ基礎力は足りない！精進あるのみ。あと、コンテスト中に飽きるのやめや自分。本番は真面目に考えようね。
というわけで本選通過やー！対戦よろしくお願いします！！めざせ 50 位！！！
