2024-03-20

TUPC2023開催記

3月9日に東北大学プログラミングコンテスト（以下TUPC）を開催した。私もwriter・運営としてコンテストに関わったのでその記録を書こうと思う。

準備について
当日について
問題について
- L - Random Mex
- N - Do Not Turn Back
最後に

準備について

運営が組織として動き始めたのはICPCの国内予選が終わった直後だった。その時点でいくつか原案があったのでwriterとして参加することにした。また、自分以外のwriter陣が全員B4以上だったので今後の開催も考えてAtCoderとの連絡係も引き受けることにした。そこから11月ごろまでは原案出しやtester作業をしていた。

11月の終わりごろには原案がある程度出ていたのでコンテストの開催に向けて本格的に動き出した。一度writer陣で集まり、問題の選定なや今後のスケジュールなどを議論した。実は最初の候補日としては3月2日を考えていたが、これを決めた直後にマスターズの予選が生えたため変更を余儀なくされた。運営陣の都合を考えると3月9日しか候補日がなかったが、この日は東北大で入試があり学内の教室を借りることが難しそうだった。顧問の先生との協議を重ね、何とか年内に教室使用の目途が立った。また、それと同時並行でAtCoderとの連絡やhenoさんへのtester依頼を行っていた。

年が明けてすぐに大学から教室の使用許可書をいただき、オンサイトを開催できることが決定したので告知を行った。オフィシャルなアカウントからツイートをするのはかなりドキドキする。

お久しぶりです

今年も東北大学競プロサークルpuzzleknotによるコンテスト「TUPC2023」を3/9(土)にAtCoder上で開催します！！
昨年同様にオンサイト会場も用意してあります！！

オンサイトの申し込みやコンテストの詳細については後日公開する予定です．

みなさんのご参加をお待ちしております！
— TUPC2023 (@tupc_tohoku) 2024年1月9日

ツイートしてから1時間ほどはずっとTLを眺めていたような気がする。多くの方から楽しみという声があり、とてもやる気が出た。後日気付いたことだが、このツイートにハッシュタグを付け忘れてしまった。反省。

その数日後に再びwriter陣で集まり、問題順や開催までのスケージュールを話し合った。その時にオンサイトの募集開催とコンテストサイトの公開も同時に行った。

TUPC2023のオンサイト参加の応募フォーム(compass)とコンテストサイト(AtCoder)を公開しました.

オンサイト参加の応募は2月末まで，先着順で50名です.
コンテストの参加登録は現時点では出来ないので注意してください.#TUPC2023 pic.twitter.com/rCiCa16JM2
— TUPC2023 (@tupc_tohoku) 2024年1月15日

とりゐさんから文字サイズの変更のアイディアがあがり、クリックすることで文字サイズが変わるようになった。

2月に入り全体testerのkotatsugameさんとhenoさんに問題を渡した。また、オンサイトに来た人が暇にならないように学内の青黄の3人チームに実際に5時間走ってもらい、難易度感などを確認した。特に「簡単枠を解いた後に不可能枠しか残っておらず何もできなかった」ということにならないようにしたいという気持ちがあったので、この確認が出来たのはよかった。これは来年以降も続けていきたい。

3月に入ってからは問題文のチェックや解説に嘘がないかなどを繰り返し確認した。また、直前には名札を作ったりお菓子の買い出しなどを行った。

名札を作っています！！ pic.twitter.com/xtRCefzaCl
— ののん (@nonon_math) 2024年3月7日

当日のお菓子と飲み物です！
当日までにもう少し増える予定です
#TUPC2023 pic.twitter.com/nSrh7vzeUl
— ののん (@nonon_math) 2024年3月7日

当日について

当日は11時ごろに集合し、会場準備などを行った。名札やお菓子を並べていたら受付開始時間になってしまったので慌てて受付に座り受付の仕事を行った。そしてついにコンテスト開始。

開始してすぐにA問題のFAが出て開始を実感。その後すぐにG問題、I問題のFAも出ており順調な滑り出しだった。数分後にはC問題。F問題にもFAが出ており、難易度を見極めるのがうまいなぁと思っていた。
次にFAが出たのはN問題だったがこれはかなり想定外。その後1時間以上たってから2nd ACが出たのでNyaanさんがやばかったらしい。続いてJ問題、E問題と解かれていてかなりいい感じだった。開始1時間で半分の問題にACが出ていた。続いてL問題、P問題と解かれ、開始2時間を迎えた。
その次にFAが出たのがO問題だったがこれもびっくり。コンテスト後にHemimorさんに話を聞くと20分くらいで解いたらしい、すごい。O問題は結局このFAがユニークACなので難易度推定が間違っていたわけではないのだろう。その後、開始3時間までにB問題、D問題とFAが出ていた。次の1時間はFAが出なかった。しかし、上位陣は解いてる問題がチームによって異なっており、順位表は賑やかだった。残り1時間となりまだ3問が0AC。だが、最後の1時間の間にM問題、H問題とFAが出た。運営の面々でもジャッジを見守っており、ACの文字が見えたときにはかなり盛り上がった。そしてコンテスト終了。あっという間の5時間だった。

結果としては以下のようになった（画像は解説スライドから）。

コンテスト終了です！！お疲れ様でした！！！
優勝は Time in Sendai でした！！！#TUPC2023 pic.twitter.com/6mPSHdEvWY
— TUPC2023 (@tupc_tohoku) 2024年3月9日

diff予想を大きく外したのがD問題、J問題、K問題、M問題、O問題だけで、それ以外はかなり予想通りで嬉しい。特に（難易度順で）前半の問題での大きなミスがなかったのはよかった。

その後は解説会と懇親会。解説会については割愛。来年はもう少しうまく話せるようにしたいね。懇親会では多くの人と話すことができて良かった。特に自分の問題についての感想をいただけるのは本当に嬉しかった。これからもオンサイトコンで作問したいと強く思った。

問題について

各問題の細かい裏話は他の方に任せて自分がwriterをした問題についてのみ書こうと思う。

L - Random Mex

最初にこの問題を考えたときは以下のような設定だった。

$N$ 個のサイコロがあり、 $i$ 番目のサイコロは $0$ 以上 $A_i$ 未満の目が一様ランダムに出る。これらをすべて振るという操作を $M$ 回行う。 $i$ 回目の操作の出目の $\text{mex}$ を $B_i$ とするとき $B$ の $\text{mex}$ の期待値を求めよ。

これでは全然解けなかったので今の形式に落ち着いた。また、原案を投げたときは $M,N \leq 5000$ とかで $O(NM)$ のdpが想定だった（解説スライドの部分点解法）。遷移部分がかなり面白いので個人的にはかなり好きな解法。

また、その後も制約や解答形式の変更が何度かあった。具体的に以下のものを考えた（どれも解ける）。

$N,M \leq 3 \times 10 ^5$
$N,M \leq 3 \times 10 ^5$ 、 $M$ に関する列挙
$N,M \leq 3 \times 10 ^5$ 、 $N$ に関する列挙

ただ、最終的な閉じた式を出してほしいということで現在の制約になった。 $O(N^2\log N)$ や $O(TM)$ を落としたかったので普段のコンテストでは見ないような厳しい制約になってしまった。実際1ケースだけTLEの提出もあったのでかなりギリギリなことをしていたのだろう。

N - Do Not Turn Back

解説スライドにも書いたが元ネタは桃鉄の「いけるかな」である。友達の家で桃鉄をしているときにふと思いついた問題。問題を考えたときはTUPCに出そうと思ってなかったのだが思いのほか好評で採用となった。この問題もL問題同様TLが厳しめになっている。また、既出が見つかったり非想定のBMBMで殴られたりと悲しいことに。もし来年もwriterをやるなら気を付けたいと思った。

最後に

はじめて競プロのwriterをしたが本当に楽しかった。語彙力がないのでうまく書けないがとにかく楽しかった。また、オンサイトの準備・運営も楽しかった。普段はTwitterでしか見ない人々が実際に目の前で話しているというのは何となく不思議な感覚になる。この楽しさをまた味わいたいので来年もTUPCを開催したい！幸いなことに今年のwriterのうち5/6は来年も残っているのでとても楽しみである。

最後に、はるばると仙台まで足を運んでくださった方々、順位表をに賑やかにしてくださったコンテスタントの方々、本当にありがとうございました！！また来年もよろしくお願いします！！！

2023-12-16

OMCerに向けたグラフ理論のお話(Advent Math Calendar2023)

この記事はAdvent Math Calendar2023 day16の記事です。これまでの方の記事もとても面白いですしこれからの方の記事もとても面白いのでぜひ読みましょう。

この記事は「グラフって言葉をときどき見るけど何のこと分からない」「グラフをかっこよく使って問題を解いてみたい」という人に向けた記事です。そのため、一部厳密性よりも直観的な分かりやすさを重視して書いています。また、出来る限り新規性のある記事にするように心がけていますが、他のグラフ理論に関する記事等と内容が被っていることがあります（この記事を書くときに参考にした記事やおすすめの記事等は最後にまとめてあります。勉強等にご活用ください）。また、分かりにくい部分や説明不足だと感じた点があれば遠慮なく教えてください。加筆します。

そもそもグラフって何？
用語集
グラフを使って問題を解くときに考えること
実際に問題を解いてみよう
- 第1問
- 第2問
- 第3問
- 第4問
おまけのおはなし
最後に
参考文献・おすすめの記事等の紹介

そもそもグラフって何？

まずは「グラフ」とは何かについて話します。グラフとは、すごく簡単に言うと、点とそれらを結ぶ線を抽象的に見たものです（グラフ理論ではこれらを「頂点」・「辺」と呼びます）。例えば、以下のようなものはグラフとして考えることが出来ます。

鉄道の駅とそれらを結ぶ線路の関係
SNSにおけるフォロー関係

駅と線路の関係については駅を頂点、線路を辺とみなせますし、SNSの例ではユーザーを頂点、フォロー関係を辺とみなせばよいですね。ここで大切なのは辺がどの頂点とどの頂点を結んでいるのかという情報です。例えば、実社会において駅がどこにあるか、線路がどのような場所を通っているのかというのは大切な情報です（観光地との距離や住宅街との位置関係、地下を走っているのかなど）。しかし、グラフにおいてはそれらは（ほとんどの場合で）気にしません。*1このような「グラフ」について調べるのがグラフ理論という分野です。

用語集

グラフ理論においては、グラフ理論独特の用語が数多く存在します。OMCの解説等でもこれらの用語はよく使われています。みなさんも使いこなせるようになりましょう。この章ではそのような用語の紹介と簡単な説明を書いています。用語についての理解がある方は読み飛ばしてもらって構いません。なお、一部競技数学ではあまり見かけない用語も紹介しています。

先ほど述べたようにグラフとは頂点(vertex)と辺(edge)からなるものです。頂点と辺がつながっていることを指す用語として接続(incident)があります。また、辺に接続している頂点を端点(endpoint)と呼びます。

似た用語として隣接(adjacent)があります。これは、ある辺によって直接むすばれている頂点の組のこと、端点に同一の頂点を持つ辺の組を指します。*2

例えば以下のグラフにおいてはこのようにいうことが出来ます。

頂点 $1$ と辺 $1$ は接続している
辺 $3$ の端点は頂点 $3$ と頂点 $4$ である
頂点 $2$ と頂点 $5$ は（辺 $4$ によって）隣接している

グラフ全体に関する性質

次に、グラフ全体を見る性質について見ていきます。重要な性質の1つ目に連結性(connectivity)があります。あるグラフが連結(connected)であるとは、そのグラフにおいてどの頂点からどの頂点も移動が可能であることです。直感的な言葉を使えば、つながっているグラフです。連結でないグラフは非連結(disconnected)であるといいます。グラフは（辺を削除することなく）いくつかの連結なグラフに分解することが出来ます。このような連結グラフのことを連結成分(component)といい、グラフにおける連結成分の個数を連結成分数(number of connected components)といいます。

辺についての用語

次に辺について見ていきます。グラフにおいては辺に情報を乗せることがよくあります。乗せることの多い情報として重み(weight)や向き(direction)があります。辺に重みをつけることで頂点間の移動におけるコストなどを考えることが出来ます。辺に重みのついたグラフを重み付きグラフ(weighted graph)といいます。また、辺に向きをつけることがあります。辺に向きのあるグラフを有向グラフ(directed graph)、向きのないグラフを無向グラフ(undirected graph) といいます。無向グラフにおいては、辺のどちらからも他方へ移動できますが、有向グラフにおいては各辺に定められた方向にのみ移動することが出来ます。

最初にあげた例を考えると、例えば駅と線路の関係は無向グラフ*3、SNSでの関係は有向グラフと考えることが出来ます。また、鉄道は所要時間などを考えれば重み付きグラフでもありますね。

ここまでは辺の持つ情報を見てきました。次は辺の性質として多重辺(multiple edges)、自己ループ(loop)、橋(bridge)を紹介します。多重辺とは、複数の辺の組であって、端点の頂点がともに等しいもののことです。なお、有向グラフにおいて $a \to b$ の辺と $b \to a$ の辺を多重辺とは呼びません。自己ループは端点の等しい辺のことです。特に、多重辺と自己ループを含まないグラフを単純グラフ(simple graph)と呼びます。橋とは、その辺を削除することでグラフの連結成分数の増える辺のことです。橋の重要な性質としてサイクル（後述）に含まれないというものがあります。

頂点についての用語

次は頂点について見てみましょう。頂点における重要な用語は次数(degree)です。これは頂点に接続する辺の本数を指すものです。無向グラフにおいては、ループは $2$ 回カウントすることに注意しましょう。また、有向グラフにおいては入次数(indegree)と出次数(outdegree)を区別して考えます。入次数はその頂点に入ってくる辺の本数、出次数はその頂点から出ていく辺の本数です。また、競技数学ではあまり見かけませんが、関節点(articulation point)も紹介します。これは、その頂点を削除することでグラフの連結成分数が増える頂点のことです。辺における橋と似たようなものです。

その他の用語

さて、次はグラフ上での移動を考えていきます。ここで大事になる用語は歩道(walk)、道(path)*4、閉路(cycle)*5です。歩道は、グラフ上で隣接する頂点への移動を繰り返すことで得られる経路のことです。このうち、同一の頂点を含まないものを道、始点と終点の頂点が同じであり、同一の辺を通らないものを閉路といいます。これらは直感的なイメージと一致するでしょう。また、歩道に含まれる辺の本数を、その歩道の長さ(length)といいます。*6また、グラフの $2$ つの頂点 $u,v$ に対して、始点が $u$ 、終点が $v$ であるような道の長さの最小値を $u,v$ の距離(distance)といいます。*7

さて、このあたりでこれまでに紹介した用語を簡単に復習してみましょう。問題形式にしてあるので解いてみてください。

次のグラフについて以下の問いに答えてみましょう。

それぞれの頂点の次数はいくつですか。
頂点 $3$ から頂点 $6$ までの距離はいくつですか。
橋である辺をすべて挙げてください。
関節点である頂点をすべて挙げてください。

解答

1. 頂点 $1$ から順に $2,3,2,5,2,2$ です。頂点 $4$ での自己ループに気を付けましょう。
2. $4$ です。辺 $2,1,4,7$ などと通ればよいですね。
3. 辺 $1,4$ です。例えば、辺 $1$ を取り除くと、頂点 $2$ から頂点 [tex;4] へのパスが存在しません。
4. 頂点 $1,2,4$ が関節点となります。

グラフの種類

次にグラフの種類についてです。グラフは性質によって様々な種類に分けられます。これらの性質を理解することでグラフを扱う問題へのハードルがぐっと下がります（私個人の意見です）。また、以下では（functional graphを除き）グラフは無向グラフとして考えます。*8

森(forest)

閉路を含まないグラフのことです。とくに連結である必要はありません。

木(tree)

森のうち、連結であるものを指します。このことからわかるように木は明らかに森です。*9 また、木においてはある頂点を根(root)とすることが出来ます。ここで大切なのは、根とする頂点にとくに制限はないという点です。しかし、根を決めてしまえばそれによって様々なものが定まります。根を定めることで決まるものとして、例えば以下のようなものがあります。

葉(leaf)
根でない頂点のうち、次数が $1$ であるものを指します。
深さ(depth)
各頂点における根からの距離のことです。
親、子(parent, child)
隣接する頂点の組のうち、根に近い（深さの小さい）頂点を親、他方を子と呼びます。
先祖、子孫(ancestor, descendant)
ある頂点に対し、その頂点から根にまでのパスに含まれる頂点のことをその頂点の先祖といいます。また、その頂点を先祖にもつ頂点をその頂点の子孫と呼びます。これらは現実世界の家系図と同じです。

また、根を定めた木を根付き木(rooted tree)と呼びます。

次に木の持つ重要な性質を紹介します。例えば以下のようなものが有名でしょう。

木の辺の本数は $(頂点数-1)$ である
木の辺はすべて橋である
木に辺を $1$ 本加えると閉路ができる
任意の $2$ 頂点間の閉路は一意に存在する。

また、この記事では紹介しませんが有向木も良い性質をたくさん持っています。「DAG*10」などと調べればたくさんの記事が見つかります。ぜひ勉強してみてください。

完全グラフ(complete graph)

すべての頂点対に対し、それらを結ぶ辺が存在するグラフのことです。例えば、 $3$ 頂点の完全グラフは三角形、 $4$ 頂点の完全グラフは四面体となります。

二部グラフ(bipartite graph)

グラフの頂点に白か黒を塗ったときに、「どの辺についても、その両端点に塗られた色が異なる」というような塗り方が存在するものです。一般にn部グラフへの拡張を考えることもできます。二部グラフを題材とした有名な議題としてマッチングがあります。面白い定理等がたくさんあるので調べてみましょう。

完全二部グラフ(complete bipartite graph)

二部グラフのうち、「任意の頂点対について、それらが異なるグループに属するならばその間に辺が存在する」という条件を満たすものです。二部グラフに対して、グラフが二部グラフである限り辺を増やし続けることで得られます。

オイラーグラフ(Eulerian graph)

ある頂点から、すべての辺をちょうど1度だけ用いて元の頂点に戻る閉路が存在するグラフのことです。直感的な表現をすれば一筆書きをして元の場所に戻ってくることの可能なグラフです。グラフがオイラーグラフであることはすべての頂点の次数が偶数であることと同値です（証明は高校数学の美しい物語に載っているため割愛します）。また、閉路ではないが一筆書きが可能なグラフを準オイラーグラフ(semi-Eulerian graph)といい、グラフが準オイラーグラフであることの同値条件は次数が奇数の頂点の個数がちょうど2個であることです。

平面グラフ(plane graph)

平面の上に辺を交差させることなく書くことの出来るグラフです。平面でないグラフのうち、頂点数が最小のものは頂点数が $5$ の完全グラフです。

正則グラフ(regular graph)

すべての頂点の次数が等しいグラフです。特に、その次数を $k$ としてk-正則グラフ(k-regular graph)と呼ぶことがあります。

functional graph

有向グラフであって、どの頂点の出次数もちょうど $1$ であるようなものです。OMCの問題としては、 $S=\lbrace 1, \dots, n \rbrace$ として関数 $f:S \to S$ を考える問題で有効に使えることが多いです。functional graphの性質としては以下のようなものがあります。

連結成分数はサイクルの数と等しい。
すべての頂点の入次数が $1$ であるとき、グラフはいくつかのサイクルに分解できる。

グラフを使って問題を解くときに考えること

まず、グラフを用いて問題を解く前に覚えておいてほしいことを伝えます。それは、「ほとんどの問題はグラフの用語に置き換えてからが本質である」ということです。グラフ理論と聞くと難しい数え上げ問題をサクッと解決してくれる素晴らしい飛び道具に見えるかもしれませんが、そんなことはありません。もちろん、とても強い定理や性質もありますが、そのような定理を使うだけで解ける問題は稀です。また、ほとんどの問題はグラフ理論の知識がなくても解けます。

では、なんのためにグラフを使うのでしょうか。これは人によって様々な考えがあるかもしれませんが、私は「問題の見通しを良くする」ために使っていることが多いです。問題をグラフ理論の用語に置き換えることで全体像が見えやすくなり、問題を解く手掛かりになります。また、分からないことがあったときに検索がしやすくなります。統一的な用語を用いることで、先人が残してきた様々な定理をたくさん学ぶことが出来ます。

ただ、グラフ理論の強い定理等を知っていると簡単に解ける問題があるのも事実です。以下では実際の問題を扱いながら「問題文をグラフの用語に置き換える練習」と「強い飛び道具の紹介」をしていきます。

実際に問題を解いてみよう

さて、ついに問題演習です。以下ではOMCの過去問を用いて問題を解いていきます。問題に対するネタバレを含むので注意してください。また、すべての問題に対して解答は載せておらず、グラフ的な見方をするまでのヒント・私が解いたときに考えたことや問題に対する一言コメント、類題の紹介を載せています。最終的な答えにたどり着くための計算部分はOMCの公式解説等を見てください。なお、これらは折り畳みとして載せているため、スクロールするだけではこれらが見えることはないので安心してください。

第1問

$5$ 人の生徒がおり、それぞれが一斉に自分以外の $2$ 人を指差したとき、どの $2$ 人の生徒についても互いに指差しているか、互いに指差していないかのどちらかでした。このような指差し方は何通りありますか。ただし、それぞれの生徒は区別します。

（出典：OMC173 B）

ヒント1

まず、何を頂点、何を辺にすればよいか考えてみましょう。また、辺の有向無向や重みについてもどのようにすればよいか考えてみましょう。

ヒント2

人を頂点、指差しの関係を辺とするのが良いですね。また、ある人が別の人を指差したとき、逆方向にも指差しが行われていることから無向グラフと考えることが出来ます。

人が指差しているため有向グラフに見えてしまうことがあるかもしれませんが、「互いに指差している」という条件がうまく効いてきます。ところで、人は指差さないほうがいいらしいです。

第2問

$4$ つの都市 $A,B,C,D$ があり，はじめは $AB,BC,CD,DA$ 間にそれぞれ道路が $1$ 本ずつあります。ここへ、以下の操作を $10^9+10$ 回繰り返します。

異なる $2$ 都市を選び、それらを双方向に結ぶ道路を新たに $1$ 本建設する。

$10^9+10$ 回の操作の組み合わせは $6^{10^9+10}$ 通りありますが、このうち得られた道路網について、すべての道路をちょうど $1$ 回ずつ通るような道順が存在しないような操作の組み合わせは何通りありますか？素数 $10^9+7$ で割った余りを求めてください。

ただし、道路は交差しないものとし、途中で引き返すことはできないものとします。（出典：OMC073 D）

ヒント1

お分かりの通り都市を頂点、道路を辺として見てあげたら良いでしょう。条件を満たさないグラフはどのようなグラフでしょうか。

ヒント2

条件を満たさないグラフはオイラーグラフ（または準オイラーグラフ）ですね。ここでグラフの有名な性質として「グラフにおける次数和が偶数」というものを紹介します。これを考えればもとめるグラフの条件はどのように言えるでしょうか。

ヒント3

一筆書きが出来ることは、次数が奇数の頂点が $2$ 個以下であることと同値なのですべての頂点の次数が奇数になるものを考えればよいです。

翔子さんのユーザー解説もきれいです。ぜひ読みましょう。

第3問

以下の条件をみたす，長さ7の数列 $a_1,a_2,...,a_7$ はいくつありますか？

$a_1,a_2,...,a_7$ はすべて1以上7以下の整数である。

$a_{a_{1}}=a_{a_{2}}=a_{a_{3}}=a_{a_{4}}=a_{a_{5}}=a_{a_{6}}=a_{a_{7}}$

（出典：MathPower杯2022 F）

ヒント1

この問題はこれまでの問題よりもグラフとして見るのが難しいですね。まずは具体的な $a$ をいくつか考えてみましょう。そして、 $i \to a_i$ と辺を張ったグラフを考えてみましょう。どのような特徴が見えてくるでしょうか。

ヒント2

このグラフはfunctional graphですね。そのため、始点が決まれば $2$ つ先の頂点も定まります。この頂点を固定して考えてみましょう。

ヒント3

固定した頂点から伸びる辺は自己ループである必要がありますね。この辺を無視して残りの辺からなる根付き木を考えてみましょう。

この問題のようにfunctional graphを考えることでうまくいく問題がたくさんあります。類題として以下を紹介します。

第4問

ある国には $3000$ 個の都市があり、それぞれの都市に，都市 $1, \dots, 3000$ と番号が振られています。これらの都市の間に、相異なる $2$ 都市間を結ぶ双方向に行き来可能な道を何本か引く方法であって、以下の条件を満たすものが $M$ 通りあるとします。

任意の都市から任意の別の都市へ、必要ならばいくつかの都市を経由して、引かれている道だけを使って必ずたどり着くことができ、また同じ都市を $2$ 回以上通らない場合、その道順はちょうど $1$ つ存在する。

都市 $1, \dots,1000$ を端点に持つ道は、それぞれ高々 $1$ 本である。

都市 $1001, \dots, 2000$ を端点に持つ道は、それぞれ高々 $2$ 本である。

都市 $2001, \dots, 3000$ を端点に持つ道は、それぞれ高々 $3$ 本である。

$\displaystyle\frac{M}{3000!}=\displaystyle\frac{p}{q}$ をみたす互いに素な正整数 $p,q$ に対して、 $p \times q$ を $3000$ で割った余りを答えてください。

（出典：OMC186 F）

ヒント1

何を頂点・辺とすればよいかは分かるでしょう。1つ目の条件はグラフがどのようなものであることと同値でしょうか。

ヒント2

1つ目の条件はグラフが木であることと同値ですね。これは「任意の都市から任意の別の都市へ必ずたどり着くことができる」「その道順はちょうど $1$ つ存在する」という部分を見ればよいです。では、次にこれを頂点 $3000$ を根とした根付き木として見て、葉を取り除いていくことを考えます。どのような順番で取り除けばよいでしょうか。

ヒント3

次数が $1$ である頂点の取り除き方として以下の方法を考えます。

グラフの葉である頂点のうち番号が最小であるものおよびそれに繋がる辺を取り除く．

これは公式解説に書かれている操作です。この操作から何が分かるでしょうか。

ヒント4

この操作の背景（というか操作そのものですが）としてPrüfer codeを紹介します（細かい内容については需要がありそうなら記事を書きます）。これは、簡単に言うと $N$ 頂点のラベル付き木から生成される長さ $N-2$ の数列のことで、この数列と木が一対一対応します。この事実を知っていれば簡単な議論のみで答えにたどり着くことが出来ます。

この日の4eには予定があったため出れませんでした。悲しい。

おまけのおはなし

ここまでは、OMCの過去問を中心としたグラフのお話をしてきました。~~ここから先は、そうではない話、私が勉強しているグラフ理論の話をします。~~書こうと思っていましたが思ったより記事が長くなってしまったので次回以降にでも書きます。

と言いつつこれで終わってしまっても寂しいので最後に私が面白いと思った問題の紹介をします。ノーヒントで解けたらすごいと思います。

単純連結無向グラフ $G$ （すなわち、 $G$ は多重辺、自己ループを持たない連結無向グラフである）について、その頂点数を $n$ 、最小次数を $d$ とします。このとき、 $G$ は長さ $min(n-1,2d)$ 以上のパスを持つことを示してください。（出典：Graph Theory/Ch1）
最小次数とは
$G$ において、頂点 $i$ の次数を $d_i$ とします。このとき $d=min(d_1,d_2,...,d_n)$ です。

ヒント1

$G$ の最長のパス $P$ について、その長さ $k$ を $min(n-1,2d)$ 未満であるとしてみましょう。矛盾が生じます。

ヒント2

$k \lt n-1$ であるので $G$ の頂点のうち $P$ に含まれない頂点があります。また、 $k \lt 2d$ からは何が分かるでしょうか。

ヒント3

$k \lt 2d$ から $P$ 内のすべての頂点を含むサイクルが存在することがわかります。示してみましょう。

ヒント4

$P$ の端点と隣接する頂点はどのような頂点である必要があるでしょうか。 $P$ の定義を思い出してみましょう。

略解

記号はヒントで使用したものを用いています。また、頂点数 $1$ のグラフなどの特殊なケースについての議論は省略しています（このようなグラフについても主張は成り立ちます）。

$P=(p_0,...,p_k)$ とします。また、 $P$ に含まれない頂点 $v$ について $v$ が $p_i(1 \leq i \lt k)$ と隣接しているとしても一般性を失いません（ $k \lt n-1$ ）。次に、ヒント3にあるサイクルの存在を示します。 $p_0$ と $p_k$ が隣接するときは明らかなのでそうでないとしましょう。 $P$ の最長性から $p_0$ と $p_k$ はサイクルに含まれない頂点には隣接しません。そのため $p_0$ と $p_k$ はともに $p_1,...,p_{k-1}$ のうち少なくとも $d$ 個に隣接します。さらに $p_0$ は $p_1$ と、 $p_k$ は $p_{k-1}$ と隣接します。 $k \lt 2d$ と合わせて、ある $1 \leq j \lt k-1$ が存在して $p_0$ は $p_{j+1}$ と、 $p_k$ は $p_j$ と隣接することがわかります（鳩ノ巣原理）。よってサイクルの存在が示せました。このサイクルを頂点 $p_i$ と $p_{i+1}$ の間の辺を無視し、 $v$ とつなぐことで長さ $k+1$ のパスを得ることが出来ました。これによって主張が示されます。

この問題はグラフ理論のゼミで私が担当した問題です。サイクルを見つける議論が難しいですね。

最後に

今回の記事では用語を中心にグラフ理論の基本について書いてみました。今回の記事には載せきれなかったことでも大切なことはたくさんあるので、ぜひこの下に載せある記事も読んでみてください。また、次の記事では今回は書けなかった純粋数学に近いグラフ理論のお話についても書きたいですね。長くなってしまいましたがここまで読んでいただきありがとうございました。それではまた次の記事でお会いしましょう！

参考文献・おすすめの記事等の紹介

*1:これらを気にして議論を行うこともありますが、競技数学においては気にしないと考えて問題ないでしょう。

*2:どちらも同じ語なので文脈から読み取ることが必要です。

*3:鉄道は移動の方向が決まっていますが反対方面のものも存在するので無向グラフと考えられます。これを有向グラフとみなすこともあるでしょう

*4:カタカナで「パス」と表記されることもあります。

*5:カタカナで「サイクル」と表記されることもあります。

*6:重み付きグラフにおいては通った辺の重みの和とすることが多いです。

*7:存在しない場合は $\infty$ とすることが多いです。

*8:有向グラフに対しても定義できますがここでは省略します。

*9:有名な言い回しです。明日クラスメイトにも教えてあげましょう。

*10:directed acyclic graphの略です。

2023-12-11

入青記事

AtCoder青色になりました！！！

というわけで色変記事を書いていきます. 入水記事はかなり簡単なものになってしまったので今度はちゃんと(?)書きます.

自己紹介

理系の大学1年生
大学に入るまでにしたプログラミングと言えばscratchを少しだけ触ったことがある程度
高校時代は競技数学(OMC)を少しだけやっていた
大学では競技プログラミングサークルに所属、グラフ理論のゼミにも参加している

精進の記録

水→青でやったこと

コンテストに出る
結局これが1番大事だと思います. コンテストに出ないとレートは上がらないですからね. AtCoder以外にもYukicoderやCodeforces, BOJのコンテストに参加をしていました. また, AtCoderのコンテストについては, コンテスト後に振り返りを簡単に書くようにしていました（この記事の1番下に置いてあります）.
バチャにでる
コンテスト形式での練習が（コンテストへの参加を除けば）1番成長すると思います. まよこんやサークルのバチャに出来る限り参加するようにしていました.
知識をつける
実装をしたことがなくとも, そのデータ構造・アルゴリズムが出来ることを知っているだけでも勉強しておくと良いと思います（もちろん書けるに越したことはないのですが）. コンテスト中にそれを使う問題が出たときに検索が出来るようになるメリットはかなり大きいと思っています.

水→青で覚えたこと・出来るようになったこと

Mo's Algorithm
覚えましたがコンテスト中に使ったことがありません. なのでそろそろ出ると思っています.
LCA
AtCoderで使った記憶がないですが...
文字列アルゴリズム
ローリングハッシュ, Z-Algorithm, Manacher's Algorithmあたりは勉強しました. まだ使いこなせないですが.
セグ木
水になる前に使えていたかもしれませんが記憶が定かでないので一応書いておきます.
遅延セグ木
まだ検索と一緒に使っていますが, 遅延セグ木で出来ることはわかってきた気がします.
FPS
ライブラリ整備までしましたがコンテストでは使えていないです. 過去問ではいくつか高難易度も解けるようになってきました.

また, ライブラリの整理などもしました. 今まではテンプレートにすべてを入れていたのですが, ICPCで写経をしないといけないことなどからコーディングスタイルを変更し, それと同時にライブラリをちゃんと作ることにしました.

これから頑張りたいこと

EDPC・典型90を埋める
入水記事でも書きましたが全然解けていないので解きたいですね.
Library Checkerを埋める
少しずつ埋め始めました. これから頑張りたいです.
作問
たまーにX（旧Twitter）に投げています. これからも少しずつ投げます.
学業
ピンチ！！

これからも黄色を目指して頑張っていきます！！

黄coderの奇行だぁ！をやりたいので早く黄色になりたい
— ののん (@nonon_math) 2023年8月11日

今の競プロの目標は来年の7/27のABCで黄色になって8/3の誕生日ABCで飲酒unratedを決めること
— ののん (@nonon_math) 2023年10月29日

水→青のコンテストの振り返り

ABC315
ABC315
ABC314同様に序盤の速解きが上手くいっていました. E問題を通した後はD問題を実装していましたがバグが取れず, 残り時間と通してる人数を見てD問題だけ通してもそこまでパフォが上がらないと考え, F問題にシフトしました. 結果的にこの判断が上手くいきF問題を通しきることが出来たので良かったです.
ABC316
欠番
ABC317

ABC317
この日は埼玉大学でオンサイトがあったので新宿のネカフェから参加しました. D問題は初手の方針を間違えていましたが冷静に考え直すことが出来たためそこまで悪い影響がありませんでした. E問題では実装ミスで時間を取られましたが個人的には満足のいく出来でした.
ABC318

ABC318
この日は早起きして実家（横浜）から自宅（仙台）の長距離移動があったためあまり良いコンディションではありませんでした. B問題での添え字ミス, D問題の実装ミスなどが重なってしまい、少しではありますが冷えてしまいました。
ABC319
ABC319
Cまでは良かったのですがDとEでかなり沼ってしまいました. Dは改行まわりでのミス, Eは i ごとにmodを取っていたことによるミスです. この辺の簡単に防げるミスを減らしていかないといけないなと思いなおしました.
ABC320
ABC320
この日はJAGの夏合宿の初日でした. Cでのつまらないミスで2ペナをしたのが痛かったです. Eでも実装ミスで時間を取られてしまいました. ここ数回EとFの崖にやられているので実力を上げないといけないですね.
ARC165
ARC165
この日はJAGの夏合宿の中日でした. 冷えました. B問題は嘘解法しか思いつきませんでした. C問題は二部グラフ判定のあとの最小値を求めるパートでミスがありサンプルが合わず, 最後まで通すことが出来ませんでした.
ABC321
ABC321
D問題まではかなり良かったのでE問題, F問題がどちらも解けなかったのが悔しいですね, 特にF問題はFPSでの立式が出来ていたのにそこから実装に移すことが出来ませんでした.
ABC322
ABC322
D問題, E問題の実装が重かったですがノーペナで通せたのは良かったです. D問題に30分かかっているのでこの時点で冷えを覚悟しましたが順位表を見ると耐えていたので安心しました. また, E問題は6次元dpを書いていましたがN<5のときの処理をうまく出来たので添え字等で頭がこんがらがることがありませんでした.
ABC323
ABC323
初めての6完です. 嬉しい. F問題は気合の場合分けで通しました. ただ, 3ペナをしていることや, 全体的に時間がかかっていることから, 思ったよりもパフォが伸びませんでした, 早解きを出来るようにすること, 序盤の問題でのペナを減らすことを意識して精進することを決意しました.
ARC166
ARC166
A問題, B問題どちらともかなり時間がかかってしまいました. 特にB問題は公倍数での処理にかなり時間がかかってしまいました. うまい方法があると信じて場合分けして解くことを避けていたのがダメでした（結局場合分けをして解きました）. また, C問題では斜めごとに独立に考える方法が思いつきませんでした. 悲しい.
ABC324
ABC324
D問題でめちゃくちゃ沼りました. 前から貪欲に確認していましたが両側から見ればいいんですね. このような楽な実装方針が考えられないのは自分の弱点だと思います. C問題で沼ったことに焦ってD問題でもペナを重ね, 逆転を狙ってF問題に突っ込みましたが実装が合わず悲惨な結果になってしまいました.
ARC167
ARC167
自分の中ではかなり悲惨な結果だと思っていましたが予想以上にパフォが高くて驚きました. つい最近, 約数積に関する問題を作っていたために, B問題での考察をほとんどスキップできたのが大きかったです. それにしては実装に時間がかかりすぎですが.
ABC325
ABC325
C問題までは良かったのですがD問題で嘘を投げまくっていました. D問題とE問題の配点が変わらないのにD問題にこだわってしまったのは反省です.
ABC326
ABC326
久々にABCで勝てた気がします. D問題で実装に沼っているときに, 先週の反省を生かしてE問題に移れたのは良かったです. そのままの勢いでF問題まで解けたのも良かったです. そのあとD問題が解けなかったのは良くないです.
ABC327
ABC327
E問題まではかなり上手くいきましたが遅延セグ木を履修していなかったためF問題を通すことが出来ませんでした. このコンテストが終わった後に遅延セグ木を勉強しました. キーボードほしかった...
ABC328
AB328
6完しましたがF問題が重み付きUFを張ると通ってしまう問題だったためパフォがそこまで伸びませんでした. 2週連続で知識不足で勝ちを逃していて勉強不足を痛感しました.
ABC329
ABC329
今週はF問題の知識を知っていたので簡単に通すことが出来ました. が, E問題で沼ってしまいせっかくの勝ちのチャンスを逃してしまいました.
ARC168
ARC168
B問題まで解くのが遅いうえにせっかくC問題に数え上げが出ているのに解けませんでした. このようなセットで勝てないのは反省ですね.
ABC330
ABC330
E問題までの速解きでなんとか冷えずに済みました. 時間があったのにF問題の嘘解法に粘着してしまいました. ABC329のE問題と似たようなミスをしており, 自分の愚かさに悲しくなりました.
ABC331
ABC331
D問題の累積和の閉区間・閉区間で頭をバグらせてしまいましたが, E問題を先に解くことで頭をリセットして落ち着いて考えられたので良かったです. F問題は初めてローリングハッシュを使ったため, 実装のバグが多く大変でした.
ARC169
ARC169
A問題は本当に何も分かりませんでしたがB問題は割と簡単に解くことが出来たので冷えを最小限にできました. 助かった...
ABC332
ABC332
E問題とF問題の配点が近かったのでD問題を解いた時点で2問とも問題を読み, F問題はすぐに方針を思いついたのでF問題から解きました. 遅延セグ木が出来ることを自分の中でわかってきている感じがあり, 成長を実感しました.

2023-11-05

近畿大学数学コンテスト2023参加記

今回は近畿大学理工学部理学科数学コース主催の第25回数学コンテストに参加したのでその参加記を書きます。

コンテスト前日
コンテスト当日
コンテスト
コンテスト後
さいごに

コンテスト前日

5限まで授業があったので夜の飛行機で大阪に向かいました。9時半頃に関空に到着し、ホテルの近くのラーメン屋でラーメンを食べました。店の雰囲気が大阪っぽく(？)大阪に来たことを実感しました。

コンテスト当日

朝は6時半頃に起床し、通天閣を見に行きました。その後近畿大学に向かい、コンテスト前に何人かの方とエンカしました。

コンテスト

私は同じ大学の友人と2人チームで参加しました。なので、コンテスト開始と同時に2人で問題の分担を決めることにしました。1問目は解けそうなので最後の保険にします。2問目は問題文が長くて大変そうなので飛ばします。3問目は見た目が幾何なので友達に任せます。4問目は楽しそうなので私が受け持ちます。5,6問目は組み合わせっぽいので友達に任せます。7問目は担当の少ない私が受け持つことになりました。

私は、まず4番を考察することにしました。が、(1)の不等式から何も分かりません。対数を取ったり面積評価を考えたりしましたが、うまくいきません。1時間ほど粘りましたが諦めます。

そのあたりで、チームメイトから5番6番の相談を受けたのでそちらを考えます。5番は数列っぽく考えて積の和典型に落とし込めそうな見た目をしているので頑張ります。しかし、これもうまくいきません。FPSなども考えましたがうまくいきません（実際にはFPSで解けるらしいですが私は出来ませんでした）。次に6番を考えます。問題文の理解に苦労しましたが、何とか読み取ります。友達が下側は出来そうと言っていたので上側を考えていました。定義とにらめっこすると、直交するラテン方陣について一方のマスに書かれている数を順列を使って置き換えてもいいことが分かるのでこれを使って頑張ります。最後の議論でミスをした気がしますが多分大丈夫でしょう。

残り時間が少なくなってきますが解けているのが6番だけでピンチです。急いで1番と7問目の初級を解き、コンテスト終了となりました。

コンテスト後

コンテスト前にエンカ出来なかった方々とエンカをし、サイン会(？)を行い、感想戦などをしました。その後、公式の解説会、表彰式、写真撮影などがあり解散となりました。表彰式ではOMCerが何人か入賞していて勝手に誇らしい気分になっていました。表彰されたみなさん、おめでとうございます！解散後には何人かのOMCerと食事に行きました。お好み焼きを食べました。

さいごに

東北に住んでいるとエンカ出来る機会が少ないのでとても楽しかったです。ただ、コンテストは悔いの残る結果となったので来年はコンテストでもいい成績が残せるように頑張って精進したいですね。

2023-09-20

ICPC JAG夏合宿参加記 2023

今回は8/16～8/18に開催されたJAGの夏合宿に参加したのでその参加記を書きます。

1日目
- コンテスト
2日目
- コンテスト
3日目
- コンテスト
最後に

1日目

集合時間が13時だったのでお昼ご飯を食べてチームメイトと一緒に会場に向かいました。12時50分ごろに到着しました。都内なのに都内にいる感じが全くしないような場所でした。その後、全体での自己紹介などがあったのちにコンテスト開始となりました。また、今回はチームメイトの一人が合宿に参加できないということで3日とも2人チームで参加していました。

コンテスト

1日目のセットは韓国の問題でした。初日ということで簡単目のセットだったらしいです、全然解けませんでしたが。結果としてはACEKの4完でした。 AEKはチームメイトが、私はCを解きました。CはABCでやりましたね。4完後はF問題を粘っていましたが永遠にTLEをしていました。10⁶の1sec厳しすぎませんか？しかもこの問題0頂点グラフが与えられることがあるらしいですね。

コンテスト後は簡単な問題の解説、晩御飯を挟み難しい問題の解説がありました。

その後はチェックインをしてABCに備えてお風呂などを済ませました。みんなで集まれる談話室があったので電話室からABCに参加しました。しかし、テーブルが低くタイピングがしにくい、エアコンから水が垂れてくる、廊下の話し声がかなり聞こえている、など競プロをやる環境としてはあまりいいものとは言えませんでした。ただ、温まったので良しとしましょう。

ABCのあとは談話室に集まりボードゲームなどをして遊びました。ナンジャモンジャなどをしました。 x.com

2日目

朝は7時過ぎに起き、朝ご飯を食べ、コンビニに寄ってからコンテスト会場に向かいました。2日目は1日目と違いコンテスト時間が10時から15時ということで軽食のようなものを買いました。

コンテスト

ACHの3完でした。私はAとCを解きました。Aは実験をするとkごとにいい感じに求まりそうだと思いエスパーをして投げました。通ってよかった。Cは英語が分かりませんでした。perpendicularをサンプルからエスパーして通しました。エスパーしかしてませんね。3完後にL問題を解いていたチームメイトから一般グラフの重み付き最大マッチングが書けるか聞かれましたがさすがに持っておらず。コンテスト後に調べるとpythonだとnetworkxにあるらしいですね。

コンテスト終了後は部屋に戻り、早めにお風呂に入りました。ARCまで時間があったので談話室でゲームなどをしていました。その後、昨日の反省を生かして部屋からARCに参加しました。コンテスト後は談話室で感想戦などをしたのち、同部屋のメンバーと1行作問をして遊んでました。そのときに生えた問題をいくつか以下に載せるのでぜひ解いてください（問題文は清書してあります）。

問題1

$N$ 頂点の木がと正整数 $K \lt N$ 与えられます。 $i=1,2,\dots,N$ に対して以下の問題を解いてください。

$i$ 以外の $N-1$ 個の頂点のうち $K$ 個を選ぶ選び方すべてに対し、以下の値を求めその総和を $998244353$ で割った余りを求めて下さい。

頂点 $i$ から辺で直接つながった頂点に移動することを繰り返し、選んだ $K$ 個の頂点をすべて回る歩道の長さの最小値

最後に頂点 $i$ に戻る必要がないことに注意してください。

問題2

正の整数 $A,B,C$ が与えられます。 $gcd(A,X)+gcd(B,X) \leq C$ となるような正の整数 $X$ の個数を求めてください。

3日目

朝は2日目と同様に過ごしました。

コンテスト

ABEの3完でした。私はAEを担当しました。Ａはやるだけです。Eは余事象を考えると最初に選ばれる数ごとに解けるので条件を満たすような選ばれ方の確率の累積積を取れば良いです。確率を求める部分はOMC-123(E)でやったことがあったので良かったです。その後Cを考えていましたが、細部を詰め切れず解くことができませんでした。悔しい。

コンテスト後は解説、その後解散となりました。

最後に

3日間を通してとにかく実力不足を痛感しました。解法が分かっても書けない問題が多く、普段からライブラリやコピペに頼りすぎていることを改めて感じました。あと、来年以降は英和辞書を持っていくようにします。

この3日間を通じてたくさんの強い方々と交流できたのはとてもいい経験になりました。来年はもっと強くなって参加したいですね。

最後に、夏合宿を開催してくださったJAGの方々には感謝しかないです。ありがとうございました。

2023-08-14

入水記事

AtCoder入水しました～～！！！

ということで簡単にここまでにやったことなどをまとめてみます。

精進の記録

とにかくたくさんやることを意識しました。精進は量より質という人もいますが、私は量がモチベにつながる人間（だと自分では思ってる）のでまずは量を確保する、そのうえで質を上げようと頑張りました。

入水までにやったこと

個人的に1番実力が上がったと思っているのは1日1水diffです。

#1日1水diff https://t.co/1r8JZB9Ade
今日から頑張ります
— ののん (@nonon_math) 2023年6月22日

やっていくうちに1問にかける時間が短くなってきて、少しずつ成長してることを実感できました。皆さんもぜひやりましょう。

あとはとにかく過去問を解きました。様々な解法やアルゴリズムを実際に解いて自分のものに出来るように繰り返しました。

これからやること

青を目指して精進をします。具体的には以下のものを埋めたいですね。

・EDPC
・典型90
・ARC

あとは積極的にバチャに参加しようと思います。

最後までお読みいただきありがとうございました。これからも頑張ります。

2023-07-08

ICPC2023国内予選参加記

はじめに

　お久しぶりです。ICPC2023の国内予選にチームrnnとしてripity,neko0774と参加したのでその参加記を書きます。

本番まで

　まずは、私は大学から競プロを始めた初心者だったので、こんな私とチームを組んでくれた経験者の2人に感謝を言いたいです。私にとっては初めてのチーム戦だったので、練習の時点からめちゃくちゃ楽しんでました。

本番

　チームでのスタートは次のようにしようと決めました。

・Aをnekoが解く
・Bを私が読み、Aが終わったらnekoに解法を伝えて実装を任せる
・ripityがCを読む

これはかなり予定通りにいきました。Bの考察まで終わった段階で、ripityがCの構築を偶数のときだけ作り上げていたのでDと同時並行でCの奇数のときの構築を考えていました。本番直前までルービックキューブで遊んでいたのが功を奏して(?)うまい構築が思いつきました。ripityと共有をし、正当性を確かめ、実装は丸投げしました。そのあとはnekoとDとEの分担をどうするか決め、私はDを担当することにしました。順位表を見た感じ、突破には5完が必要な気がしたため、そこを目標に頑張ることにしました(結果だけを見れば早解き4完でも突破できましたが本番はEFが崖になりそうだと思ってしまいました)。Dはいろんな数を作りたいなぁと強く思うと二進数に気付くので7で抑えられることに気付きます。気付きます、気付いたんです。そこで二進数に囚われすぎてしまい、全探索をしようと思えませんでした。結局最後まで嘘解法しか思いつかずに終わってしまいました。Eはnekoがうまいdpを思いついていたのですが時間が足りず、結局3完で終わってしまいました。

来年以降に向けて

とりあえず、今年は終わってしまいましたが幸いなことに来年以降もICPCに出場するチャンスがあります。来年もこのメンバーで出場して予選突破したいですね。