問題
これの
これです。
ソート、しません。
説明
この問題に出てくる話をざっくり書くと、
- 村人と別の村人の友好度の情報(友好関係)の一覧
- 村人の加入と脱退のログ一覧
があって、
ログごとに、
「加入中の村人」と「加入していない村人」の間にある友好関係の内、
最大の友好度を出す
という内容です。
Observerパターン(Wikipedia)というのは、
イベントのを「通知する側」と「通知を受ける側(リスナー)」で考えるやつですね。
paizaがJavaScriptをNode.jsで動かしているのは分かっているので
標準ライブラリにあるEventEmitterを利用しましょう。性能良さそうですし。
これでタグにNode.jsを付けられます。
リスナーは誰か
「ログ」がイベントの契機だとして、リスナーは村人・・・と思われそうですが違います。
今回のリスナーは「友好関係」です。その方が簡潔。
「友好関係」には、自分が今アクティブ(集計対象)かどうかの状態を持たせます。
イベントは何か
「友好関係」には、自身に関係している２人の村人について加入/脱退があったときに
通知してもらうようにしましょう。
通知を受けたら、自分がアクティブかどうかを反転します。
(ルール上の制約により、+-を見る必要はありません)
あと、最大値を見失った時のための「全探索」イベントを定義しておきます。
イベントの種類は
- 「村人」イベント (正確には、村人の数字ごとに別のイベント)
- 「全探索」イベント
になります。
無駄な計算は省く必要がある
毎回、友好関係をすべて再確認すると数が多すぎるようです。
確認回数そのものをいくらか減らさなくてはなりません。
何を見るか
「村人」イベントで状態が変化した友好関係だけで、最大値を取ります。
- 今回アクティブではなくなる友好度の内、最大の値 (max_out)
- 今回アクティブになる友好度の内、最大の値 (max_in)
を反転処理のついでに取得します。
再確認(全探索)が不要になるパターン
以下のどちらかを満たすときです。
- 今回アクティブではなくなる友好度の最大が、現在の最大値より小さい
- 今回アクティブになる友好度の最大が、現在の最大値と同じかそれ以上
最大値は維持されるか、増加してmax_inの値に更新されます。
再確認(全探索)が必要になるパターン
上記とは逆の条件、つまり以下の両方を満たすときです。
- 今回アクティブではなくなる友好度の最大が、現在の最大値である
- 今回アクティブになる友好度の最大が、現在の最大値より小さい
友好度が下がることは分かったのですが、いくつになるか不明の状態です。
特にソートの類をしていないので、やむなく全探索をかけます。
コード
雰囲気だけでも見てもらえれば。
// 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秒台だったので一旦よしとしました。
こんな方法でしたが面白がっていただければ幸いです。
読んでいただきありがとうございました。