yukicoder contest 357 の writer でした。単独コンテスト開催は 3 回目になります。
前回の開催記はこちらからご覧ください。
各問題の感想
No.2041 E-mail Address
簡単枠です。1 文字ずつ読みながら処理することで解けます。正規表現を使っても解けます。
Brainfuck で解ける問題を作りたくて作りました。テスターは Whitespace で解いていたみたいです。
No.2042 RGB Caps
構築問題です。やさしめの構築は毎回出しています。
1 番目から A 番目までの帽子の色がわかるというのは一列に並んでいることに由来します。
元々は運動会という設定がついていましたが削られました。
No.2043 Ohuton and Makura
調和級数の入門問題として出しました。
もっと高速化できますが、これが一番楽だと思っています。
最初、B と C の位置は逆でしたが、途中で入れ替えてしまいました。結果逆転が起きてしまいました。構築の難易度判定は難しいがちです。
No.2044 Infinite Nim
Nim の亜種です。しかし Nim とまったく同じコードで解けます。
以下の記事で石が無限にあるゲームが扱われています。ネーター性を使う証明が面白く印象に残っています。
fibonacci-freak.hatenablog.com
これを見て、Nim の石が無限にあったらどうなるだろうと考えて作問しました。
解説の「後手次郎君を先手として通常の Nim が始まりますが、XOR が 0 なので後手である先手太郎君の必勝です。」の部分、ややこしいですね。
No.2045 Two Reflections
過去に群論の記事を書いたり群論をテーマにした問題を出題したりしていましたが、最近はあまり群論に触れていませんでした。今回は久々に群論をテーマにした問題です。
位数 2 の置換 2 つで生成される群が二面体群になるという性質は、今後どこかで出題されてもおかしくないと思っています。
群論は競プロの役に立つ！
998244353 で割った余りを求める問題になっていますが、答えはおそらく 64 bit 整数で扱える範囲に収まると思います。証明は難しそうです。
群論記事もよろしくお願いします。
No.2046 Ans Mod? Mod Ans!
ストーリーの元ネタはこの問題です。
答えで 109+7 を割った余りを求める問題は過去にもう 1 つあったような気がします。(追記)下の問題でした。
(追記終)
解説に載せた記事を参考に実装しました。Kotlin, Python で 2 秒ほどかかっていたので、TL を 4 秒に設定しました。テスター解もそんな感じだったので妥当な TL だと思っていましたが、多くの参加者が 1 秒以下で通しているのでそんなことはなかったです。
この手の問題が苦手なので発想が足りなかったですね。反省しています。
No.2047 Path Factory
元ネタの問題はこれです。
この問題を解いて、こんな感じの木 DP の問題を作ろうと思い作った問題です。
パスグラフの定義がシングルトンを含むか迷っていました。両方あるように見えていました。含めないことにした方が多少難易度が上がるので含めないことにしました。
式変形がだいぶ複雑だったので ★3.5 はあるかと思っていましたが、テスターの提案で ★3 になりました。
No.2048 L(I+D)S
ロビンソン・シェンステッド対応とフック長公式の布教問題です。今は知らない人が多いですが、いつかは典型になる日が来るでしょうか。
最近は群論の代わりにヤング図形といった組合せ論を勉強しています。組合せ論は競プロの役に立つ！
元の問題は「1,2,...,A+B の順列であって、LIS の長さが A、LDS の長さが B となるものの個数」でしたが、平方根をとった値が OEIS にあったので修正しました。この数列に辿り着くことは難しくなったと思いますが、OEIS を利用して解いている人はいました。
おわりに
テスターを引き受けてくださり、有益なアドバイスをくださった harurun さん、Kazun さん、platinum さん、Shirotsume さん、sapphire__15 さん、akakimidori さん、hitonanode さん、素晴らしいプラットフォームを用意してくださった yuki さんに感謝します。
単独コンテストは今後開催しないかもしれません。競技プログラミングに真面目に取り組まなくなって久しいので、作問に自信がないためです。気が変わる可能性はあります。
代わりに、今勉強している組合せ論の布教をやっていきたいと思っています。実際、組合せ論の論文を読んで競プロの問題を作問したので、どこかで出せたらいいなと思っています。また、9 月から始まる予定の月刊組合せ論もよろしくお願いします。
ここまでお読みいただきありがとうございました。
