当サイトの記事にはプロモーションが含まれています。
ABC397 - C - Variety Split Easy
最終更新：2025-03-19 投稿日：2025-03-19
2025/03/15に行われたオムロンプログラミングコンテスト2025（AtCoder Beginner Contest 397）のC問題の解法についての記事です。
考えたこと
長さ\( N \)の整数列\( A \)を2分割するとき、分割した箇所より小さい側を「左」、大きい側を「右」と呼ぶことにします。
（左の長さ）\( + \)（右の長さ） \( == \) （\( A \)の長さ）
なので、左の長さを決めてしまえば、
（右の長さ）\( == \)（\( A \)の長さ） \( - \) （左の長さ）
\( ⇔ \) （右の長さ）\( == \) \( N \) \( - \) （左の長さ）
として、右の長さは自動的に決まります。
したがって、左と右、それぞれの長さにおける整数の種類数を求めて足し合わせていき、その最大値を求めれば、\( O ( N ) \)で答えを導くことができます。
コードの例
#include <bits/stdc++.h>using namespace std;int main() {int N;cin >> N;vector<int> A(N);for (int i = 0; i < N; i++) {cin >> A.at(i);}vector<int> left(N);vector<int> right(N);set<int> leftS;set<int> rightS;//まずleftを求めるfor (int i = 0; i <= N - 2; i++) {leftS.insert(A.at(i));left.at(i) = (int)leftS.size();}//次にrightを求めるfor (int i = N - 1; i >= 1; i--) {rightS.insert(A.at(i));right.at(i) = (int)rightS.size();}//必要な値が求まったので答えを導くint ans = 0;for (int i = 0; i <= N - 2; i++) {int j = i + 1;ans = max(ans, left.at(i) + right.at(j));}cout << ans << endl;return 0;}
解法
左の長さ\( ( left ) \)が取りうる値は\( １ \leq left \leq N - 1 \)、
右の長さ\( ( right ) \)が取りうる値は\( N - 1 \geq right \geq 1 \)です。
そこで、それぞれの長さに含まれる整数の種類数を求める際には、
\( left \)については\( A_1 \)側から順に\( A_{N-1} \)まで、
\( right \)については\( A_N \)側から順に\( A_2 \)まで、
それぞれ求めていくと、最後に適切に足し合わせるだけで答えが導き出せます。
種類数を数える際には、setを用いればよいです。
\( A \)の各項がすべて異なったときに総種類数は最大となりますが、\( N \)項の数列なのでint型で処理が可能です。