解いてみた。「Sランク：村人の友好関係」

問題

「Sランク：村人の友好関係」

コード

Javaで解いてみました。

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int nN = sc.nextInt();
        int nM = sc.nextInt();
        int nQ = sc.nextInt();
        
        boolean[] bIn = new boolean[nN+1];

        boolean[][] bValid = new boolean[nN+1][nN+1];
        long[][] lValue = new long[nN+1][nN+1];

        for (int i = 1; i <= nM; i++) {
            int nA = sc.nextInt();
            int nB = sc.nextInt();
            long lF = sc.nextLong();
            if (nA > nB) {
                int tmp = nA;
                nA = nB;
                nB = tmp;
            }
            lValue[nA][nB] = lF;
        }

        // 同好会に入会／退会
        long lCurrentF = 0;
        for (int i = 0; i < nQ; i++) {
            String sOp = sc.next();
            int nP = sc.nextInt();

            long lMaxPlusF = 0;
            long lMaxMinusF = 0;
            if (sOp.equals("+")) {  // 入会
                bIn[nP] = true;
                
                for (int j = 1; j <= nN; j++) {
                    int nA = j;
                    int nB = nP;
                    if (j == nP) {
                        continue;
                    } else if (j > nP) {
                        nA = nP;
                        nB = j;
                    }
                    
                    if (bIn[j]) {
                        bValid[nA][nB] = false;
                        if (lMaxMinusF < lValue[nA][nB]) {
                            lMaxMinusF = lValue[nA][nB];
                        }
                    } else {
                        bValid[nA][nB] = true;
                        if (lMaxPlusF < lValue[nA][nB]) {
                            lMaxPlusF = lValue[nA][nB];
                        }
                    }
                }
            } else {    // 退会
                bIn[nP] = false;
                
                for (int j = 1; j <= nN; j++) {
                    int nA = j;
                    int nB = nP;
                    if (j == nP) {
                        continue;
                    } else if (j > nP) {
                        nA = nP;
                        nB = j;
                    }
                    
                    if (!bIn[j]) {
                        bValid[nA][nB] = false;
                        if (lMaxMinusF < lValue[nA][nB]) {
                            lMaxMinusF = lValue[nA][nB];
                        }
                    } else if (bIn[j]) {
                        bValid[nA][nB] = true;
                        if (lMaxPlusF < lValue[nA][nB]) {
                            lMaxPlusF = lValue[nA][nB];
                        }
 
                    }
                }
            }

            long lMaxF = 0;
            if (lCurrentF < lMaxPlusF) {
                lMaxF = lMaxPlusF;
            } else if (lMaxMinusF < lCurrentF) {
                lMaxF = lCurrentF;
            } else {
                boolean bBreakFlag = false;
                for (int x = 1; x < nN; x++) {
                    for (int y = x + 1; y <= nN; y++) {
                        if (bValid[x][y] && (lValue[x][y] > lMaxF)) {
                            lMaxF = lValue[x][y];
                            if (lCurrentF == lMaxF) {
                                bBreakFlag = true;
                                break;
                            }
                        }
                    }
                    if (bBreakFlag) {
                        break;
                    }
                }
            }
            
            System.out.println(lMaxF);
            lCurrentF = lMaxF;
        }
    }

}

解説

標準入力からの数値の読み取り

Scanner インスタンスを作り、nextInt()メソッドで数値を取得しています。

主な変数の説明

bIn[]

村人Nが、同好会に属していれば bIn[N] = true, 属していなければ false です。

bValid[][]

村人M が同好会に属していて、村人N　（M<N）が同好会に属していない、あるいはその逆の時にtrueです。

lValue[][]

村人M と 村人N （M<N）の友好度です。

入会／退会時の動作

入会処理

入会した村人について、入会していない村人との bValid[][] を true に、入会している村人との bValid[][] を false にします。

退会処理

退会した村人について、入会している村人との bValid[][] を true に、入会していない村人との bValid[][] を false にします。

最大友好度を求める

「通常の方法」を使うと、ループが多すぎてタイムオーバーになってしまいます。そこで工夫が必要です。

通常の場合

bValid[][] が true のものの中で、lValue[][] が最大のものを出力します。

有効になった友好度の最大値を求め、前回の結果と比較

前回の結果と比較し、有効になった友好度の最大値の方が大きければ、その値が求める値になります。

無効になった友好度の最大値を求め、前回の結果と比較

前回の結果と比較し、無効になった友好度の最大値の方が小さければ、前回の結果が求める値になります。