yukicoder contest 305 開催記
yukicoder で単独 writer コンテストを開いたので，感想や裏話などを綴っておこうかと思います．まだ問題を見ていない方は是非ご覧になっていただいて，できれば 1 問でも取り組んでいただけるととても嬉しいです．
A. She Loves Me, She Loves Me Not, ...
1 問目は簡単めに…という気持ちで作られた問題で，当初は☆1.5 の diff 500 程度想定でした．全体 tester の tatyam さん (@tatyam_prime) さんから「☆2 では？」という指摘を頂き，「そうかもな～？」という気持ちで上げたのですが，とても適切だったようです．ありがとうございます！
よくある（？）花占いをスターから一般のグラフに広げてみましたというだけの問題です．少し考察は必要ですが，詳細に詰めなくてもとりあえずシミュレーションしてみれば正解できるという問題で，ちゃんとたくさん解かれて良かったです．解説を書くのは地味に大変でした．
B. Minimum Multiple with Double Divisors
整数枠で，ランニング中に原案が降ってきました．問題文も解法もシンプルでとても気に入っている問題です．実際 Fav もたくさん（執筆時点で 17 も）頂いていて光栄です．
コンテスト開始からしばらく順位表を眺めていると，無限人が WA を出していてヒヤッとしました．提出を色々眺めていると，素冪に限定してやっていそうなものが結構あって，想定 WA 解法だったので安心して見ていました．tester のねぼこさん (@nebocco27) には「サンプルに 6 まで入れていて（素数限定 WA を誘発しないので）優しいですね」とコメントを頂いていたのですが，それでも意外とハマってくれるんだなあという気持ちです．
C. I hate Construct a Palindrome
ABC197-F を解いたときに思い付いた問題で，構築問題も欲しいなと思っていたのでちょうど良い題材でした．自分の実装だと 0.1 sec を切っているので安心していましたが，意外と TL が厳しめだったかもしれません．☆3 は適切だと思いますが，実装が重いのもあって D の方が通されてしまい逆転してしまいました．
当初の想定解法だと BFS をして から
への最短路を求めた後，文字が 1 種類のみであれば最短路上の頂点をすべて根と見なして（縮約して）再度 BFS をして別の文字への最短路を求め，それらを繋ぎ合わせるということをしていました．tester の nok0 さん (@nok0_kyopro) がシンプルな（実装が楽な）解法を提案してくださったので，解説にはそちらを載せています．ありがとうございました！
D. Rush and Remove
ゲーム枠です．実は元ネタがある *1 ので，あまり Fav を頂いてしまうと恐縮です．
問題としては，やることの候補がそんなに無いので，（想像以上に綺麗な）法則に気付いてしまえば実装は激軽で AC できるという感じでした．とはいえ Grundy 数の知識は必須で，どれだけ気付かれるか不明だったので ☆3.5 にしていましたが，実際には C よりも通されてしまうという結果になり驚きました．難易度投票では☆3 に揃っていたので，終了後に下げました．高得点を狙って先に解きに行った皆様，ごめんなさい．
E. Majority Painting on Tree
数え上げ枠です．本業の方で似たような課題に直面して，それっぽい感じに問題として仕立て上げたものになります．辺や頂点ごとに禁止色を作ってみたり，色々変種を考えたりもしましたが，設定はシンプルな方が面白いという気持ちで最終的に出題した形に落ち着きました．B と同じぐらいの自信作のつもりなので，まだ取り組まれていない方は是非今からでもチャレンジしてみてください．
想定解は包除原理＋木 DP でしたが，tester のながたかなさん (@ngtkana) に「これは DP というよりは頂点ごとに独立に解いている感じでは？」とご指摘いただき，確かにと思って解説に追記しました．基本的にやることは同じなのですが，この考え方だと木の形自体にはもはや意味が無くなり，次数列のみから答えが決まるというのが面白く，また計算時間の定数倍部分もかなり軽くなります．皆様の提出を見た感じだと，Python などで TL 5 sec に間に合わせるには，高速な方の解法を採用しないと厳しいのかもしれません？
F. Double Down
最適化枠で，ボス問です．原案は今朝 arXiv で公開されたこちらの論文 *2 の一部で，この部分（辞書順最大を求めればよい）自体はそこまで難しい考察ではないと思います．実際 tester の iaNTU さん (@iaNTU_) やご参加いただいた heno さん (@heno_code) もその部分はクリアされていたようです．
難しい（かつ面白い）のは，それが Dulmage–Mendelsohn (DM) 分解を活用すると（重み付きマッチングを解くより）高速に求まるという部分で，ここはさすがに誰も解けなかったようです．アルゴリズム自体はかなりシンプル（グラフを更新しながら重み無しマッチングを 回解くだけ）で，直観的にそうだなと納得してもらえるだろう程度には解説を書いていますので，DM 分解の勉強も兼ねて是非解説 AC していただければと思います．（布教問 *3 でもあるので．）
コンテスト中には異常高速化された最小費用流アルゴリズムたちに 3 発ほど殴られましたが，実は半分想定内でした．準備中は自分と tatyam さんがそれぞれ高速な Network Simplex 法を拾ってきて通してしまうというのをやり，制約と TL を の 5 sec から
の 8 sec，
の 10 sec と変えて，テストケースも色々準備したのですが，任意を防ぐのは不可能では？？？という気持ちになっていました．*4 想定解法が出なくても高速化で AC 出るかもぐらいに思っていたら，本当にそうなって強い人は力もすごいなあという気持ちです．
まとめ
橙になったときに書いた記事 *5 で「そろそろ作る側でもちゃんと貢献したいな」と書いたのを達成でき，皆様にもそれなりに楽しんでいただけたようでとても良かったです．自分の作った問題を解いてもらえると嬉しいですね．ツイートもしましたが，clar も事故も無く無事に終えられたのは tester の皆様のおかげです，ありがとうございました．原案はまだいくつか持っているので，またしばらくしたらどこかで出題したいと思っています．そのときは対戦よろしくお願いします！
