村人の友好関係 (paizaランク S 相当) を何故かObserverパターンで解く(JavaScript)

## 問題

https://qiita.com/official-events/9ab96aa95d62fe3cbdd7

これの

https://paiza.jp/works/mondai/s_rank_skillcheck_archive/group_popularity

これです。
ソート、しません。


## 説明

この問題に出てくる話をざっくり書くと、

- 村人と別の村人の友好度の情報(友好関係)の一覧
- 村人の加入と脱退のログ一覧

があって、

ログごとに、
「加入中の村人」と「加入していない村人」の間にある友好関係の内、
最大の友好度を出す

という内容です。

[Observerパターン(Wikipedia)](https://ja.wikipedia.org/wiki/Observer_%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3)というのは、
イベントのを「通知する側」と「通知を受ける側(リスナー)」で考えるやつですね。

paizaがJavaScriptをNode.jsで動かしているのは分かっているので
標準ライブラリにあるEventEmitterを利用しましょう。性能良さそうですし。
~~これでタグにNode.jsを付けられます。~~


### リスナーは誰か

「ログ」がイベントの契機だとして、リスナーは村人・・・と思われそうですが違います。
今回のリスナーは「友好関係」です。その方が簡潔。

「友好関係」には、自分が今アクティブ(集計対象)かどうかの状態を持たせます。


### イベントは何か

「友好関係」には、自身に関係している２人の村人について加入/脱退があったときに
通知してもらうようにしましょう。
通知を受けたら、自分がアクティブかどうかを反転します。
(ルール上の制約により、+-を見る必要はありません)

あと、最大値を見失った時のための「全探索」イベントを定義しておきます。

イベントの種類は

- 「村人」イベント (正確には、村人の数字ごとに別のイベント)
- 「全探索」イベント

になります。


### 無駄な計算は省く必要がある

毎回、友好関係をすべて再確認すると数が多すぎるようです。
確認回数そのものをいくらか減らさなくてはなりません。


#### 何を見るか

「村人」イベントで状態が変化した友好関係だけで、最大値を取ります。

- 今回アクティブではなくなる友好度の内、最大の値 (max_out)
- 今回アクティブになる友好度の内、最大の値 (max_in)

を反転処理のついでに取得します。


#### 再確認(全探索)が不要になるパターン

以下の**どちらか**を満たすときです。

- 今回アクティブではなくなる友好度の最大が、現在の最大値より小さい
- 今回アクティブになる友好度の最大が、現在の最大値と同じかそれ以上

最大値は維持されるか、増加してmax_inの値に更新されます。


#### 再確認(全探索)が必要になるパターン

上記とは逆の条件、つまり以下の**両方**を満たすときです。

- 今回アクティブではなくなる友好度の最大が、現在の最大値である
- 今回アクティブになる友好度の最大が、現在の最大値より小さい

友好度が下がることは分かったのですが、いくつになるか不明の状態です。
特にソートの類をしていないので、やむなく全探索をかけます。


## コード

雰囲気だけでも見てもらえれば。

```JavaScript
// Copyright © 2024 https://qiita.com/tanin_no_sorani
// Released under the CC0 1.0 Universal license.
'use strict';

const EventEmitter = require('node:events');

const emitter = new EventEmitter().setMaxListeners(0); // リスナー数の上限解除

let first = true; // 先頭行の判定用
let max     = 0; // 現在の友好度の最大値
let max_in  = 0; // 今回アクティブになった友好度の最大値
let max_out = 0; // 今回アクティブでなくなった友好度の最大値

require('node:readline').createInterface({ input: process.stdin })
.on('line', line => {
	if (first) { first = false; return; } // 先頭行は破棄
	
	const words = line.split(' ');
	
	if (words.length === 3) { // [村人, 村人, 友好度]
		// 「友好関係」
		const p = Number(words[2]); // 友好度
		let active = false; // 状態 アクティブかどうか
		
		function reverse() {
			(active = !active) ? // フラグ反転
				((max_in  < p) && (max_in  = p)) : // アクティブになった場合
				((max_out < p) && (max_out = p)) ; // アクティブでなくなった場合
		}
		emitter.on(words[0], reverse); // 「村人」イベント登録
		emitter.on(words[1], reverse); // 「村人」イベント登録
		emitter.on('all', () => active && (max < p) && (max = p)); // 「全探索」イベント登録
		
	} else
	if (words.length === 2) { // [+-, 村人]  (+-は不使用)
		// 「ログ」
		max_in = max_out = 0;
		emitter.emit(words[1]); // 「村人」イベント通知
		
		// 「村人」イベントで変化した友好関係だけを見て、再探索の要否を判定
		if ((max_out < max) || // アクティブでなくなる友好度の最大が、現在の最大値より小さい
			(max <= max_in)) { // アクティブになる友好度の最大が、現在の最大値と同じかそれ以上
			// 再探索は不要  (＝最大値は維持または増加する)
			(max < max_in) && (max = max_in);
			
		} else {
			// 再探索が必要  (＝最大値は減少するが、いくつになるか不明の状態)
			max = 0;
			emitter.emit('all'); // 「全探索」イベント通知
		}
		
		console.log(max);
	}
});
```


## 感想

再探索(全部見る)をどれだけ抑えられるか、まだ工夫の余地が色々ありそうですが、
テストケースでは最長のものでも4秒台だったので一旦よしとしました。

こんな方法でしたが面白がっていただければ幸いです。
読んでいただきありがとうございました。