ARC165を書きました - chineristACの日記

atcoder.jp

久々に作問記

問題の解法のネタバレを含むかもしれません。

A: Sum equals LCM
B: Sliding Window Sort 2
C: Social Distance on Graph
D: Substring Comparison
E: Random Isolation
F: Make Adjacent
全体の感想

A: Sum equals LCM

元ネタは箱さんのこの問題です。

yukicoder.me

「順列 $P$ を $N$ 回かけて $P_i=i$ が成り立つのは $P$ が長さ $N$ のサイクルからなるときのみ」が成り立つと思い込んで証明してみようとしたら全然嘘でしたがARC-Aっぽくなったので出しました。

なんで300じゃないの？って言ってた人を観測しましたが、これは自分のAがだいたい炎上しがちだったので怖くなって高めにつけたからです。testerには300評価の方もいました。

B: Sliding Window Sort 2

ARC-Aつくりたいな～と思って適当に作ったら難しくなっちゃった枠。自分で考えたときは割とすぐに後ろ $K$ 項ソートがつよいな～になって時間かけずに解けたのですが、難しかったらしい。B-Cのtesterの評価が分かれてたのでB=Cにしたけど自分は B > C 派だった。

嘘解法が通ってたのはマジですいません…

B問題

嘘解法:2番目未チェックかつ最後に後ろK項ソートした結果と比較しないかつ「N-K+1項目から」左にずらせるかを検証する

これを落とす方法:P_{n-k}<P_{n-k+1}かつ2番目の条件を満たさないものをケースにいれる
— 私はゴミカステストを作りました (@ChineristA) 2023年9月17日

postしたように $P_{n-k} \gt P_{n-k+1}$ のケースしかなかったのが1つの原因です（これを解消するテストケースは追加したがそれでも落ちない嘘解法があるらしい…）。

こういうミスはシステム的に防ぎたいのですが、マルチテストで小さいケース全部いれるなど小手先の対策以外に思いつかないので厳しい。

…と思ったけどこれ条件追加したりすれば数え上げにできたしそれなら嘘考察は通らなかったかもしれませんね。今度からARCは6問全部mod 998244353にします。

適当に作った枠。Social Distance ~ っていう題名の問題をちょくちょくみかけたので自分も名前から作ってみました。二分探索から考えれば素直な考察だと思うし、同じ点数のBとばしてC解く人多いんじゃないかな～と思ったけどそこまで解かれなかった。JAG合宿で他の人に話を聞いたところ序盤だとさすがに解かなきゃダメだろという気持ちになって飛ばしずらいらしい。なるほどなあ。

D: Substring Comparison

お気に入り枠。「部分文字列の辞書式順序比較によってminimum cyclic shiftを求めよ」というインタラクティブ問題を考えた後 adaptive にできるかな～と思ってでてきた問題です（元問題は非想定が強くて廃案）。最初は比較が定まる位置を決め打つとかして解けるわけね～ってなった後考え直したら解けてびっくりしました。

白状すると自分は500点ぐらいかな～と思い「考察要素ないかも…」っていうコメント付きでadminに投げました。adminからは「考察要素あります」というコメントが返ってきました。冷静になるとそれはそう。

解法が全然見たことない感じの問題でどれくらい解かれるかは全然わからなかったですが、想像よりは解かれました。

E: Random Isolation

適当に作った枠2。AGC058F をみて指数個状態がある期待値問題作ってみたいと思って作ってみた問題です。期待値の線形性は指数個に分けても最終的に状態をまとめられれば計算できるんだな～というある意味教育的な問題にもなったかなと思います。Dと比べるとこっちのほうが典型的だしmod998だしAC数多くなるか？と思っていましたが結構差がでました。

余談ですが $N\leq 1000, K\leq 10$ とかで出題する案もありました。 $\Theta (N^2(N-K)^2)$ を $\Theta (N^2K^2)$ にしてね～という意図の案で、本質からすこし離れた改善を要求するのでめっちゃ文句いわれそうだと思いやめました。ただ $\Theta (N^5)$ をやっている人が多かったのを見るとこれもありだったかもしれない。