はじめに
yukicoder contest 291 ご参加ありがとうございました! ご参加下さったみなさん、testerを引き受けて頂いたみなさん、本当にありがとうございました!
以下では各問題の講評を記します。ネタバレが含まれるので注意してください。
A.esreveR dna esreveR
原案,解法:PCT
FA:tuteさん(1分45秒)
割とシンプルで個人的には好きな問題です。1問目としてちょうどいい難易度だと思います。
B.Lamps on Graph
原案の原案:2020年度麻布中学入試数学第5問
原案,解法:nok0
tester:むかでさん
FA:uwiさん(6分49秒)
久々に算数の問題を見てたらめちゃくちゃ競プロっぽかったので改題して出題しました。 やることはただの貪欲なのですが、割と面白いと思います。
2問目にしてはやや難しかったかも?ごめんなさい。
C.Simple Sugoroku
原案,解法:nok0
tester:おてらさん
FA:SSRSさん(11分38秒)
すごろくとか考えてたら生えた問題です。Sugoroku 2より前に思いついたので、ABCですごろくが出てびっくりしてました。 後ろから全探索していくことで線形で解けます。(実はQCFium法で Ο(M2) が通ります)
最初の1時間、全然ACが出なくてびびっていました。
D.Matrix Eraser
原案:fairy_lettuce 解法:nok0
tester:ながたかなさん
FA:tabrさん(11分6秒)
writerの解法が嘘貪欲だったので(!?)、解法を提供しました。THE 典型枠ですがとても好きな問題です。知らなかった人は最大流で出来ることについて色々調べてみるといいと思います。
E.Many Complete Graphs
原案:PCT 解法:PCT
tester:蜜蜂さん
FA:NyaanNyaanさん(7分32秒)
沢山の組に辺を貼る時は超頂点っていうのはかなり典型的な気がします。
DとEでどちらが難しいか悩んでいたのですが、いい感じにD<Eになったようでよかったです。
F.Rotation ABC
原案,解法:nok0
tester:chineristさん
FA:tatyamさん(22分56秒)
Ad-hocだったり実験だったり枠。難易度評価が難しかったです。実験すればわかると思います(多分)
G.Swap Many Permutations
原案:nok0 解法:nok0,PCT
tester,賢い解法:tatyamさん
FA:hitonanodeさん(101分54秒)
むずめの数え上げ枠。必要十分条件をエスパーして頑張って式変形すると畳み込みに帰着できます。 全然解かれないと思ってたのですが、結局5人もの方に解いていただきました!すごいです!!
なんと実は線形で解けます。 tatyamさんに畳み込みを使わない線形解を教えていただきました、ありがとうございます〜
H. Many Graph in Namori
原案:PCT 解法:PCT
tester:beetさん
全完阻止枠。誰も時間内には解けないと予想しています(beetさんが10時間掛かったらしいので)
↑結局ACは出ませんでした Ω\ζ°)チーン
まとめと感想
優勝はSSRSさんでした!!おめでとうございます!! 参加していただいたみなさん、並びにtesterを引き受けてくださったみなさん、ありがとうございました! セットとして出題するのは今回が2回目ですが、共同作問はいつもとは違った刺激があり、またお互いに問題を強化したりできるので凄い楽しかったです。 作問は問題をただ解くのとは違った楽しみがあるので、とてもおすすめです!
またいつかyukicoderにはセットを出したいと思っているので、その時はよろしくお願いいたします。 最後になりますが、ありがとうございました!!