yukicoder で合同コンを開きました

yukicoder で noya2 さんと合同でコンテストを開きました. 全体Tester には Nachia さんに来ていただきました. 本当にありがとうございます!!

難易度は ★1.5 - ★2.0 - ★2.5 - ★3.0 - ★4.0 - ★4.0 - ★4.0 でした. Writer / Tester を除いて, 参加者は 152 人、各問題の正解者は
[A] 129人 / 145 ★1.5
[B] 116人 / 126 ★2.0
[C] 77人 / 99 ★2.5
[D] 36人 / 49 ★3.0
[E] 18人 / 19 ★4.0
[F] 9人 / 12 ★4.0
[G] 9人 / 9 ★4.0
でした.

yukicoder.me

再来週にもあります. ぜひご参加ください！

yukicoder.me

間に挟まった来週のコンテストは bayashiko さんによる単独コンテストらしいです. 出ましょう！

yukicoder.me

この記事では, 問題の裏話や, 人々がどんな感じで解いてたかを作問者が覗き見た感じ（？）を書いています.

A - Friday (★1.5)

ProblemId = 9326 - yukicoder

感想

「簡単な問題なくないか？」ということで生まれた問題です. 皿をどういう挙動をするかはかなり非自明ですが, エビがエビの皿にある個数を $t$ などと置いて数分触っていれば解けると思います.
こういうふうに代数的に文字を置くと考察がめちゃくちゃ進むの, 数学のすごさを感じますね

低難易度ながら考察要素がメインで良いですね～ $O(1)$ で解かされましたが多分コンテスタントのぼくは $O(\min(A, B))$ に逃げます.

【コンテスト中】
サンプルの弱さもあって WA がめっちゃでました. みんないろいろな方法を試しているようですが, 正解はちゃんと考えないと出ない式だと思います.
落ち着いて考えればいけると思います.

B - WAC (★2.0)

ProblemId = 9100 - yukicoder

感想

これは, ARC-A の 300 点問題でありそうな問題ですね　貪欲証明として「ある条件を満たすの方にスワップしても悪くならない」というやつは典型です（むしろスワップして悪くならないための必要十分条件を求めるとかもある）

貪欲としてはかなり証明しやすい方なので思いつけば確証が持てると思います
【コンテスト中】
実装の方針によってはかなり苦労したと思います. 想定解通りにやると簡単です.
フローを乗っける解法は正しいですが, TLEで落ちることを確認してます. ごめんね！
B で結構詰まっている人いました.

C - Reach 1 (★2.5)

ProblemId = 9135 - yukicoder

感想

君はまだ「本当のギャグ」を知らない. こんな問題は競技プログラミングといえるのでしょうか？と言いたい気持ちは分かります. ぼくもそう思っています. しかし、競技プログラミングは何でもありの競技だと思っているので, よし！

実装は非常に簡単で, エスパーで解くことができます. 証明で使ったオイラーのトーシェント関数は競プロ的には知っておいて損はないと思います.
想定WAは, $k=1$ のみを選び続けるものです. サンプルはそうなってます.

【コンテスト中】
★2.5 に設定しましたが, 不意打ちな問題で苦戦した人も多いと思います.
$k=1$ のみを選び続ける想定WAに引っかかってくれた人もたくさんいました.

D - Cities and Teleporters (★3.0)

ProblemId = 9044 - yukicoder

感想

まあダブリングなんですが, ダブリングはあまり ABC などでは青Diffあたりで見ない印象があります. あるとしても繰り返し検出か, LCA か, 何かです.
蟻本には巡回スケジューリング問題としてダブリングが載っています. 今回は若干異なる問題として典型でありつつも教育的な問題になったと思います.
ダブリングは始集合と終集合が同じの写像（または functional graph）に使えるんですが、今回はうまくダブリングに載らせることが出来るのですよ!
まあ問題はやや実装が大変で, バグりやすい問題でもあると思います. Chu! WA を連発させちゃってごめん
あと結構時間制限はPypy3使いにはきつめにしてます. Chu! タプルでソート, 遅くてTLEしちゃった人いたらごめん！

【コンテスト中】
★3.0 で典型味はあるのですが, あまり解かれませんでした. ペナが非常に多かったです.
みんないろいろなケースで落ちてました（02_corner_28.txt は強いかな？）
TLEは思ったよりいませんでした. 正しい解法で落ちてたらごめんなさい.

E - Coaching Schedule (★4.0)

ProblemId = 9079 - yukicoder

感想

みなさんは $998244353$ という数字大好きですか？自分は大好きです.
これはもともとボス問でした. やや典型要素があって5問目に来てしまったのだと思います. 包除原理を使うところは典型だと思います.
でも自分はこの問題に結構苦労しました. 終盤のFFTを思いつくところで数十分、序盤のgを計算するところで数十分です.

さて, 自分は g を計算するのに Multipoint Evaluation を使いました. これは C++ だと通りますが, 想定解の方が3倍程度速くなっています. Pypy3 の想定解が通るように時間制限を 4sec に設定してもらいました.
Pypy3 だと想定解は通りますが, Multipoint Evaluation が通りません. 8sec だと通るのですが, それだと $N, M \le 10^5$ が小さくて C++ の権力で通されてしまう可能性があり, 残念ながら Pypy3 の Multipoint Evaluation は許されませんでした. しかたないね

【コンテスト中】
通してる人が多かったです！難しいのにみんなすごいです！★4の3問の中では一番通してる人が多くて, この順番で良かったと思いました.
Multipoint Evaluation で通してる人もそこそこいました. 想定解の方が人数が多いですね.

F - Integer Complete (★4.0)

ProblemId = 9087 - yukicoder

感想

この問題はもともと「9*9」という名前で, 次のような問題でした.
「 $H$ 行 $W$ 列のマス目があり、 $i$ 行目 $j$ 列目 $(1\le i\le H,1\le j\le W)$ のマスには $i\times j$ の値が書かれています。このマス目に登場しない最小の正整数を出力してください。 $1 \le H,W \le 10^9$ 」
これは半分くらいは同じ考察で, いわゆる「素数のabundance」で殴る問題です.
しかし, これは Codeforces に同じ問題があり, 5年前とはいえ「整数論テクニック集」に載っている問題だったので爆破されました.
「Integer Complete」はそれの上位互換, かつ「ルジャンドル予想」を知っているか, 整数に対する感覚で通し切ることが追加で必要です. さらに, 考察も1段階くらい増えて気付きにくさは増したと思います.

「9*9」はもともと ★2.0～2.5（緑Diff）あたりと思ってましたがnoyaさんが ★3.0～3.5 を主張したので★3.5 で通してました.
「Integer Complete」では「9*9」の ★3.5 から ★3.0 に勝手に一旦下げましたが, さすがに ★3.5 に戻され, さらに全体testerのNachiaさんの助言もあって ★4.0 になりました（？？）
★2.0 から ★4.0 への進化です.

【コンテスト中】
全然通されてませんでした. そんなに難しかったのかな…
解法はおおむね一緒でした.

G - Second Smallest (★4.0)

ProblemId = 9050 - yukicoder

感想

これはボス問です. 最初は6問目(F)の ★3.5 でした. あまり見ない感じの期待値で, ぼくはとても好きな問題です.
同じ確率分布を $n$ 回やったとき, $k$ 番目に小さい数の期待値を求める方法は探せば見つかり, 積分で出来ることがわかります.
ベータ積分はガンマ関数（階乗の拡張）と関係があるので, 簡単に求められます. ぼくはここまで 15 分です.

次の考察がすごいです. 2番目という理由がわかると思います. これすごいです. これの数え上げを思いつくのに 30 分かかりました. でも, 競技数学erはすらすら解けてしまうかもしれません.
実装, 高速化はあわせて 25 分です.

【コンテスト中】
これは通してる人はちょこちょこいました！
やっぱり難しいみたいです.