2025-12-09

虹色全域有向木予想

前回の更新から約 2 年半ぶりの更新になります．信じられない…

この記事は木 Advent Calendar 2025 の 9 日目の記事になります．参加者を絶賛募集中です．

木ということで，最近の面白研究ネタの紹介をしたいと思います．組合せ数学の話なので予備知識はあまり要りませんし，競プロer も必見*1 です．

虹色集合

皆さんは虹🌈が好きですか？好きですよね，分かります．

組合せ数学では，集合の要素がいくつかの色で塗り分けられているときに，要素の色が相異なるように選んだ部分集合のことを虹色 (rainbow) と呼ぶことがあります．*2

まずは簡単な例を見てみましょう．突然ですが，次のような予想が知られています．

予想 1 (Ryser–Brualdi–Stein 1967)

$n$ を奇数とする． $n \times n$ の任意のラテン方陣（各行各列に $1$ から $n$ の整数がちょうど 1 回ずつ出現する正方行列）に対して，各行各列各整数からちょうど 1 つずつになるように合計 $n$ 個の要素を選べる．

たとえば，下の図 1 は $5 \times 5$ のラテン方陣の一例です．行ごとに見ても列ごとに見ても整数ごとに見てもちょうど 1 つずつになるように $5$ 個の要素を選べるでしょうか？

*1:特に最後らへん．

*2:各色の要素をちょうど 1 つずつ含むとき，横断 (transversal) と言ったり，代表元の集合 (set of representatives) と言ったりもします．

2023-06-06

ARC161 開催記

前回 (ARC157) から約 3 ヶ月で ARC の writer をやったので，また感想とか元ネタみたいな当たり障りの無い話を綴っておこうかと思います．まだ問題を見ていない方は，ぜひご覧になっていただいて，できれば 1 問でも取り組んでいただけるととても嬉しいです．（定型文）

明日、対戦よろしくお願いしますhttps://t.co/ENZ8CYmgSj pic.twitter.com/Rwf6k2ASmu
— ⚫️Y.Y.⚪️ (@ygussany) 2023年5月27日

ARC161 おつでした～
今回は証明セットです、解説を書くのがしんどかった…
— ⚫️Y.Y.⚪️ (@ygussany) 2023年5月28日

A: 一番最後に作った、ARC161 なので 161 から
B: 最後から二番目、ARC161 なので 161 から
C, E: ドナウ川沿いで降って来た、色々変種があったけど最終的にこの 2 個に
D, F: 前回 (ARC157) 時点で既にあった、実家、DM 分解を人々の記憶に刻みたい（ D は 700 提案で 500 まで下がった、正しい…）
— ⚫️Y.Y.⚪️ (@ygussany) 2023年5月28日

2023-02-26

ARC157 開催記

お久しぶりです，Y.Y. (@ygussany) です．競プロを始めて 3 年弱で，2 年半ほど延々と AtCoder のコンテストに contestant として出続けていた訳ですが，ついに AtCoder Regular Contest (ARC) の writer を務めることができました．ということで，感想とか元ネタみたいな当たり障りの無い話を綴っておこうかと思います．まだ問題を見ていない方は，ぜひご覧になっていただいて，できれば 1 問でも取り組んでいただけるととても嬉しいです．（定型文）