AppleWatchが欲しかったのでpaizaのSランク問題に挑戦して記事を書いてみた

挑戦した問題はこちら

工夫した点

問題をそのまま素直に記述するならツリーとかノードとか使いたくなります。
しかし問題文をよく読むと結局人気度の算出に必要なのは一番高い友好度だけだということに気付きます。
それならば予め全ての関係データを友好度で降順にソートしておき、片方の村人のみグループに所属しているデータを上から順に探すという単純な方法で友好度が算出できるでしょう。難しいデータ構造は必要ありません。

この方法では1回の人気度の計算量は O(M) になります。

他の人のコードよりもかなりシンプルに記述できているのではないかと思います。

苦労した点

友好度データのソートリストの格納に最初はSortedSetを使ってしまったことで、友好度が同じデータが存在する場合にうまくいかずにドツボにハマってしまいました…最終的には普通のListを使いBinarySearchで挿入位置を探しながら整列させています。

実装したC#コード

（※VisualStudioでターゲットフレームワーク.NET8.0 で作成したのでそのままpaizaの提出フォームにコピペしてもコンパイルが通りません。usingやMainメソッドの追加やrecordをクラスに変更するなど、少し手直しする必要があります）

var nnn = Console.ReadLine().Split();
var N = int.Parse(nnn[0]);	// 村人数
var M = int.Parse(nnn[1]);	// 関係数
var Q = int.Parse(nnn[2]);	// ログ数
// 友好度でソートしたリスト
var sortedList = new List<Data>();
var comparer = new Comparer();
// 降順の有効度リストを作成
for(var i = 0; i < M; i++)
{
	nnn = Console.ReadLine().Split();
	var d = new Data(int.Parse(nnn[2]), int.Parse(nnn[0]), int.Parse(nnn[1]));
    // ソートしながらデータを挿入
	int p = sortedList.BinarySearch(d, comparer);
	if(0<= p)
		sortedList.Insert(p, d);
	else
		sortedList.Insert(~p, d);
}
// 現在のグループ(i番目の村人のグループ参加状況)
bool[] group = new bool[N];
// ログを解読しながら友好度を出力
for(var i = 0; i < Q; i++)
{
	var s = Console.ReadLine();
	int q = int.Parse(s.Substring(2));
	// グループ加入・脱退
	if(s[0] == '+')
		group[q - 1] = true;
	if(s[0] == '-')
		group[q - 1] = false;
    // グループが0人、または全員の時は０
	if(group.All(f => !f) || group.All(f => f))
	{
		Console.WriteLine(0);
		continue;
	}
	// 友好度の高いデータから順に片方の村人だけが加入しているデータを探す
	foreach(var d in sortedList)
	{
        // A加入B非加入 or A非加入B加入
		if(group[d.A - 1] != group[d.B - 1])
		{
			Console.WriteLine((int)d.Value);
			break;
		}
	}
}

/// <summary>
/// 友好度データ
/// </summary>
/// <param name="Value">友好度</param>
/// <param name="A">村人A</param>
/// <param name="B">村人B</param>
public record Data(int Value, int A, int B);
/// <summary>
/// 友好度データの比較用(降順)
/// </summary>
public class Comparer : IComparer<Data>
{
	public int Compare(Data x, Data y)
	{
		// 降順
		return (y.Value - x.Value);
	}
}