モノグサ社員3名(AtCoder黄・青・青)でチームを組んでKUPC(京都大学プログラミングコンテスト)という競技プログラミングに出場しました。
KUPCはAtCoderのプラットフォームを使った京都大学の学生有志が主催するコンテストであり、通常のAtCoderとは異なり、チームでの参加が許可されています。（コンテストページ）
コンテスト中はDiscordを使ってチャットや音声を介して議論したり、それぞれのPCでコーディングしたりしてリモートで参加していました。 今回はE問題を二人で考えたのが面白い体験だったので、それをシェアしようと思います。
目次
問題概要
【原文：KUPC 2021 E】
図1のような、無向単純連結グラフGがある。
グラフの辺は全て相異なる番号(1〜M)が振られており、辺には赤い辺と青い辺がある。
赤い辺はGの全域木を為している。
グラフの辺に1〜Mのインデックスをアサインした時に、赤い辺の集合が最小全域木になるように、かつインデックスをグラフの番号順で並べた時に辞書順で最小になるようなインデックスのアサイン方法を求めよ。
例えば図1の場合は以下のようなインデックスアサインが解です。
考察の流れ
yujidx7「E問題、どんな感じですか」
ryoryoryo111「そうですね、辞書順なんで可能な限り前の方の辺に小さいインデックスを決定することを考えてます」
ryoryoryo111「いまこの図の状況で番号1の辺にできるだけ小さいインデックスを決定するために、先に頂点1と頂点2の赤い全域木上での経路のインデックスの総和がそれより小さい必要があります。 具体的には頂点1~LCAと頂点2〜LCA上の赤い辺である番号2と3と4の辺の和より大きいインデックスを番号1の辺に決定する必要があります」
ryoryoryo111「だから番号2,3,4のインデックスの和を得るために、パスクエリが必要なんですけど、」
yujidx7「総和はいらないんじゃないんですか？まだ振ってないインデックスの最小の値を番号2-4の辺に決定して、その後番号1の辺にインデックスをアサインすれば十分です」
ryoryoryo111「そうですか？うーん。。」
ryoryoryo111「あー、確かに総和じゃないですね」
補足1
総和じゃないが、正しいです。
クラスカル法で最小木を構成することを考えると、上の図のような状況の場合、最小全域木の構築にはコスト5の辺は不要です。経路上のもっとも大きいコストより、わずかでも青い辺のコストが大きければ、青い辺が最小全域木に含まれることはありません。 議論のおかげで誤解が解けて、いい方向に動いてきました。一人で考えてると見当違いの方向にいってしまっているというのはあることです。
補足2
今回グラフの問題であるため、 GRAPH × GRAPH：競技プログラミングにおけるグラフ可視化サイト を使い、具体的なグラフを描画してDiscordで画面共有しながら、議論しました。
yujidx7「そうなると、全域木上でのインデックスが未決定な複数の辺に対してどのようにインデックスを決定していくかですね」
ryoryoryo111「これはでも、辞書順最小を構築したいので、番号が前の方の赤い辺から、未使用の小さいインデックスをアサインしていく形になるでしょう」
yujidx7「それが良さそうですね」
ryoryoryo111「あとは経路上の辺のうち、インデックス未決定の辺が列挙できればいいです」
yujidx7「未決定の辺を列挙する必要ってありますか？」
ryoryoryo111「例えば上の図で番号2のインデックスを決定する時に、番号3・4・6のインデックスをより小さくする必要がありますが、番号4は既に番号1の青い辺のインデックスを決定するときにインデックスが決定されているため、以後考慮する必要がありません。」
yujidx7「確かにそうですね」
yujidx7「あとはLCAまでの経路中に存在する未アサインの辺を列挙できれば、解けますね」
yujidx7「そういうデータ構造ってありませんか？」
ryoryoryo111「うーん」
==
補足3
全ての辺に対して全域木上での経路を列挙して、インデックスアサイン済みかどうか判定するということもできますが、同じ辺が何度も列挙されるため、計算量的に大きすぎます。ということは二人ともわかっているため、うまく高速化できる方法を検討しています。
==
結構筋が良さそうな方向に議論が進んだのですが、ここで止まってしまいました。別の可能性も探ってみます。
ryoryoryo111「全然別の発想とか考えてみます？」
yujidx7「後ろから考えるとかどうですか？」
ryoryoryo111「面白いですね。しかし、辞書順の場合、後ろの方の要素に貪欲に大きいインデックスをふれても、結果的に前の方の要素に最小のインデックスをふれなくなってしまうことがあるので、難しそうです」
yujidx7「確かにそうですね」
いくつもアイデアを出して、お互いで検証して、駄目だったら捨てるというサイクルを繰り返しました。
==
ryoryoryo111「UFT(Union Find Tree)でアサイン済みのエッジを管理できないですかね？」
yujidx7「UFT考えましたけど、どんな感じですか？」
ryoryoryo111「すでにインデックスをアサインした辺をUFTでuniteします。」
ryoryoryo111「さらに、毎回の更新で、各unionのうちもっとも根に近いnodeを管理する感じです」
ryoryoryo111「経路を列挙する場合にはどんどん根に近づいていって、LCAよりも浅いnodeについたら、探索を打ち切ります」
yujidx7「あー」
yujidx7「一度アサインした辺をスキップできるから計算量的にも間に合いそうですね」
yujidx7「いけそうです」
こんな感じでお互いの発想を出し、確認し、固めることができました。
感想
青〜黄程度の競技プログラマーが集まったので、LCAやUFTといった複数のアルゴリズムが絡む複雑な問題でも少ない言葉でもアイデアを交換できたり、お互いのアイデアを検証することでスピーディーに検討を進めることができました。
私一人では解けない問題だったと思います。
仕事でも競技でも、チームとして一つの難問を解くというのは素晴らしい体験だと思います。 お互いの考える過程がわかるのも参考になります。 また、KUPC2021は有志コンですが、大きなトラブルもなく、問題文もわかりやすく良質で、解説も丁寧でした。ぜひ時間があるときには参加されると良いのではないでしょうか。 モノグサ競プロ部では一緒にチームでコンテストに出てくれる社員を募集中です。
おまけ
yujidx7「実装どうします？」
ryoryoryo111「うーん、もしyujiさんがやりたいならお任せしますが(実装量あって大変そう…)」
yujidx7「うーん(実装量あってやりたくない)」
ryoryoryo111「じゃあ、やりますね」
結局、20分ほどかけてなんとか実装しましたが、サンプルの入出力があいません。
ryoryoryo111「サンプル合ってなくて、どこかバグってそうなので、Discordに実装貼りました。」
Tobisatis「ryoryoryo111さんが実装貼ってますね」
yujidx7「んーまあ、ryoryoryo111さんが頑張るでしょう」
Tobisatis「他の問題解いてましょうか」
現実は非情です。見捨てられました。（チームワークとは...）
おまけのおまけ
後々聞いてみると、私のコードがRustで読めなかったとのことでした。（さらに、別の問題をACしてくれました。）
どうやらC++, C#, Rustと全員が異なる言語で参戦していたらしいです。
モノグサ株式会社では多様なバックグラウンドや得意言語を持ったエンジニアが活躍しています！ 興味を持っていただけたら、ぜひ話を聞きに来てください！
