AtCoder ABC290 E - Make it Palindrome

uyisl

考えたこと

・最初の要素だけ見れば、数字の異なるペア数探し

入力例1の1要素目である"5"に着目すると、1要素目が関わっているのは

　　f(5, 2) = 1
　　　→5と2要素目の2で不一致なので+1
　　f(5, 2, 1) = 1
　　　→5と3要素目の1で不一致なので+1
　　f(5, 2, 1, 2) = 2
　　　→5と4要素目の2で不一致なので+1
　　　→2要素目と3要素目も不一致なのでさらに+1
　　f(5, 2, 1, 2, 2) = 1
　　　→5と5要素目の2で不一致なので+1

の4点である。ここだけ見れば不一致のペア数探しである。
(同様のことが最終要素にも言える)

・最初の要素以外は不一致のペア数だけでは済まない

入力例1の2要素目である"2"に着目すると、2要素目が関わっているのは

　　f(5, 2) = 1
　　　→2と1要素目の5で不一致なので+1
　　f(2, 1) = 1
　　　→2と3要素目の1で不一致なので+1
　　f(2, 1, 2) = 0
　　　→2と4要素目の2で一致
　　f(2, 1, 2, 2) = 1
　　　→2と5要素目の2で一致
　　　→3要素目と4要素目が不一致なので+1
　　f(5, 2, 1, 2) = 2
　　　→2と3要素目の1で不一致なので+1
　　　→1要素目と4要素目も不一致なのでさらに+1
　　f(5, 2, 1, 2, 2) = 1
　　　→2と4要素目の2で一致
　　　→1要素目と5要素目が不一致なので+1

の6点である。まとめると
　　2要素目は
　　　端である1要素目や5要素目とは1回比較する
　　　端でない3要素目や4要素目とは2回比較する
となっている。例えば2要素目と3要素目の比較は、
　　連続部分列(2, 1)　・・・2要素目から3要素目
　　連続部分列(5, 2, 1, 2)　・・・1要素目から4要素目
の2回行われる。
要素数を大きくするとわかるが、例えば10要素の3と5要素目を比較する回数は以下の図のように3回となる。

これは、min(右側の要素の右端からの距離, 左側の要素の左端からの距離)に等しい。
つまりこの問題は、不一致ペアを探してペアごとにどれだけ内側にあるかの重みを付けて和を計算する問題となる。

・計算順序を工夫して重みづけを行う

一番外の要素が関わるペアは重み1、外から2番目の要素が関わるペアは重み2、…とすればいいので、外側から順に処理していくとよさそうである。
あらかじめ全要素に対して1が何個あったか、2が何個あったか、…を数えておけば、今着目している要素と不一致のペアの数は
　　(不一致ペア数) = (全要素数)
　　　　　　　　　　- (今着目している要素と同じものが何個あるか)
で求められる。求めた不一致ペア数に重みをつけて足し算をしていけばいい。

入力例1を例にすると、各数値ごとの出現個数は
　　1の出現数：1個
　　2の出現数：3個
　　5の出現数：1個
である。一番外側である1要素目の5と不一致になるペア数は
　　(不一致ペア数) = 5(全要素数) - 1(5は1個ある) = 4
となる。一番外側は重み1なので、答えに(1 × 4)を加える。

次にもう一つの一番外側である5要素目を考えたいが、このまま5要素目について計算すると1要素目に計算済みのペアを再計算してしまうので、再計算しないように1要素目を除外する。具体的には
　　全要素数：4
　　1の出現数：1個
　　2の出現数：3個
　　5の出現数：0個
というように全要素数と1要素目の5の個数を1減らせばいい。あとは先ほどと同様の計算を行い不一致数1、答えに(1 × 1)を加える。

次は2要素目を考える。先ほど処理した5要素目を除外すると
　　全要素数：3
　　1の出現数：1個
　　2の出現数：2個
　　5の出現数：0個
となるので、不一致数1である。2要素目で重み2となるので、答えに(2 × 1)を加える。

後はこれの繰り返しで、1→5→2→4→3という順に処理としていけばいい。
最初の2回(1と5)は重み1、次の2回(2と4)は重み2である。
このように外側の要素を1つ決めて、それより内側にある要素とのペアを数えるようにすると、同一の重みのペアをまとめて計算することができる。

要素数が5より大きい場合も同様に2個処理する毎に重みを1増やしていけばいい。

出現する数値が全てN以下なので、出現数を数える際も連想配列を用いる必要はなくただの配列でいい。そのため計算量はO(N)である。

書いたコードと提出結果

#include <bits/stdc++.h>

int main(){
    int N;
    std::cin >> N;
    std::vector< int > A(N);
    std::vector< int > cnt(N+1);
    for(int i=0; i<N; i++){
        std::cin >> A[i];
        cnt[A[i]]++;
    }
    
    long long ans = 0;
    int total = N;
    for(int i=0; i<N / 2; i++){
        int left = i;
        long long tmp = total - cnt[A[left]];
        ans += tmp * (i + 1);
        total--;
        cnt[A[left]]--;
        
        int right = N - i - 1;
        tmp = total - cnt[A[right]];
        ans += tmp * (i + 1);
        total--;
        cnt[A[right]]--;
        
    }
    
    std::cout << ans << std::endl;
    
    return 0;
}


この記事が気に入ったらサポートをしてみませんか？