yukicoder contest 343 開催記
2022/05/13/21:20~23:20 に行われた yukicoder contest 343 の単独 Writer をしました。 134 人の方々が参加してくださいました。ありがとうございました！！！
全体感想
傾斜がとてもきれいになりました。
傾斜が完璧ですか？？？ https://t.co/hsNffCuZNX
— Noya2 (@noya2ruler) May 13, 2022
B 問題は丁寧な考察を求められ、コーナーケースでの WA が続出しました。E 問題がかなり解かれた印象です。全問題の FA は 00:23:33 までに出ました。最速全完は hos.lyric さんで 00:58:14 でした。 想定解法が簡潔にかける、意外なコーナーケースが存在する、数学的考察によって時間計算量を大幅に改善できる、などといった驚きを与えられるような問題セットにしました。いかがだったでしょうか？
高度な数学的考察を要する問題を tassei903 さんと共に考察し、C,E,F 問題の tester をしていただきました。ありがとうございました！
また、全体 tester を tatyam さんにしていただきました。ありがとうございました！
A 問題
FA : SSRS さん (00:00:31)
2019 年日本数学オリンピック予選の 9 番の問題から着想を得ました。xor で表せるというのは驚きです。
kotatsugame さんに tester をしていただきました。多言語での shortest 解の実装をお願いしました。ありがとうございました！
B 問題
FA : SSRS さん (00:04:29)
鳩ノ巣原理と周期性の相性はとても良いので問題にしました。「同じ状態が現れ、その後は周期性をもって遷移する」という方針で良いですが、何を「同じ状態」だと見るかをよく考えないといけません。 $n\bmod 4$ を持たない解法で大量の WA が出ていました。上位陣にも WA が多く出た印象です。
NatsubiSogan さんに tester をしていただきました。ありがとうございました！
C 問題
FA : SSRSさん (00:11:22)
有理数を分母を小さくして評価することを考えていたら衝撃的な事実に気づいてしまったので問題にしました。$P+Q$ ですって、すごくないですか？。とはいえギャグなので拡張ユークリッドの互除法で AC することも想定しています。ファレー数列というものがあるらしく（出題するまで知りませんでした...）、それを知っていればかなり有利だったのかもしれません。
SSRS さんが強すぎた。
kotatsugame さんに tester をしていただきました。こちらも多言語での shortest 解の実装をお願いしました。ありがとうございました！
D 問題
FA : googol_S0 さん (00:14:46)
実装が比較的重めの枠です。分割統治的な概念を学んだときに作った問題です。bitDP でも解くことができるみたいです。ただ、計算量に関してはかなり注意が必要です (TLE が量産されていました)。
chineristAC さんに tester をしていただきました。ありがとうございました！
E 問題
FA : hos.lyric さん (00:13:00)
ラグランジュ補間のラグランジュ補間みたいな概念を考えたくて問題にしました。解説では丁寧な式変形により共分散の形に帰着しています。どういう解釈をすればよいのかわからず困っていますが、とにかく形があまりにもきれいになりすぎたのでお気に入りです。$N^2$ 回の $\bmod$ 割り算を落とすための制約でした。ところで多点評価というものがあるらしく、$\Theta (N (\log N)^2)$ で解けるみたいです。
hos.lyric さん、解くのが早すぎませんか？(正直、1h くらい耐えると思っていました)
nok0 さんに tester をしていただきました。ありがとうございました！
F 問題
FA : hos.lyric さん (00:23:33)
ラグランジュの反転公式を ABC 222 で学んだとき、ちょうど括弧列と二分木の対応を知りました。括弧の概念を拡張すれば同じ方法でもっと強そうな問題が解けるということに気づいて問題にしました。反転公式、まるで魔法のようですね 。ところで $\Theta (N\log N)$ で解けるみたいです。
hos.lyric さん、解くのが早すぎませんか？(正直、1h くらい耐えると思っていました)2
hamamu さんに tester をしていただきました。ありがとうございました！
