はじめに
こんにちは。paiza×Qiitaコラボキャンペーンで、記事を投稿すると賞が当たるというのをやっているので、参加して問題を解いてみました。
今回解いたのは「村人の友好関係」。
Sランクなだけあり、正解率は62.7%と低めです。
以下ネタバレ注意です。（クリックで余白を折りたたみ）
解いた感想
高度なデータ構造を使う必要があり、Sランクの中でも相当難しかったです。
問題を解くためにデータ構造を書いてしまったため、せっかくなのでここに供養しておきます。
解法
時間計算量は$O(M+QN\log M)$です。
手順:
- 隣接リスト形式のグラフを構築
- 最大値を保持する多重集合データ構造を用意（グループの内外にまたがる友好関係の友好度を入れる）
- クエリで与えられた頂点に隣接する友好関係すべてに対し、多重集合に含まれるかを再計算
プログラミングを愛する方なら言葉など蛇足でしょう。
読みやすく書いたつもりなので、ぜひコードを読んでみてください。
ソースコード
/**
* 多重集合の最大値ライブラリ
*/
class MultisetMax {
capacity;
length;
map;
// 典型的なセグメント木の実装と同様に、 `tree[1]` から `tree[capacity - 1]` までは集約値が入ります。特に、 `tree[1]` はすべての要素の最大値となります。
// `tree[capacity]` から `tree[capacity + length - 1]` までは要素の値です。
tree;
constructor() {
this.capacity = 128;
this.length = 0;
this.map = new Map;
this.tree = new Array(this.capacity * 2).fill(0);
}
/**
* 値 `x` を多重集合に追加する。
* @param x 追加する値
* 計算量: amortized O(log(this.length)), worst O(this.length)
*/
add(x) {
if(!this.map.has(x)) {
if(this.length == this.capacity) {
this.tree.length = this.capacity * 4;
this.tree.fill(0, this.capacity * 2);
this.tree.copyWithin(this.capacity * 2, this.capacity, this.capacity * 2);
this.capacity *= 2;
for(let i = this.capacity; --i > 0; ) this.tree[i] = Math.max(this.tree[i * 2], this.tree[i * 2 + 1]);
}
const index = this.length++;
this.map.set(x, {index, count: 0});
}
const entry = this.map.get(x);
if(entry.count++ == 0) {
let i = this.capacity + entry.index;
this.tree[i] = x;
i >>= 1;
while(i > 0) {
this.tree[i] = Math.max(this.tree[i * 2], this.tree[i * 2 + 1]);
i >>= 1;
}
}
}
/**
* 値 `x` を多重集合から削除する。
* @param x 削除する値
* 計算量: worst O(log(this.length))
*/
remove(x) {
if(!this.map.has(x)) return;
const entry = this.map.get(x);
if(entry.count == 0) return;
if(--entry.count == 0) {
let i = this.capacity + entry.index;
this.tree[i] = 0;
i >>= 1;
while(i > 0) {
this.tree[i] = Math.max(this.tree[i * 2], this.tree[i * 2 + 1]);
i >>= 1;
}
}
}
/**
* 多重集合に含まれている値の最大値を求める。
* 計算量: worst O(1)
*/
get max() {
return this.tree[1];
}
}
// `(yield)` で行入力
function* main() {
const [N, M, Q] = (yield).split(' ').map(Number);
const graph = new Array(N).fill().map(() => []);
const inGroup = new Array(N).fill(false);
const relation = new Array(M);
const relationIsBorder = new Array(M).fill(false);
const relationValue = [];
for(let relationId = 0; relationId < M; relationId++) {
const [_a, _b, f] = (yield).split(' ').map(Number);
const [a, b] = [_a - 1, _b - 1];
relation[relationId] = [a, b];
relationValue[relationId] = f;
graph[a].push(relationId);
graph[b].push(relationId);
}
const borderValues = new MultisetMax;
for(let i = 0; i < Q; i++) {
const [op, _q] = (yield).split(' ');
const q = +_q - 1;
inGroup[q] = (op == '+');
for(const relationId of graph[q]) {
const [a, b] = relation[relationId];
const isBorderNow = (inGroup[a] != inGroup[b]);
if(isBorderNow != relationIsBorder[relationId]) {
const value = relationValue[relationId];
if (isBorderNow) borderValues.add(value);
else borderValues.remove(value);
relationIsBorder[relationId] = isBorderNow;
}
}
console.log(borderValues.max);
}
}
const mainIterator = main();
mainIterator.next();
require('readline').createInterface({input: process.stdin}).on('line', line => {
mainIterator.next(line);
});