AtCoder Regular Contest #022
問題文
$N$ ノードから成る木が与えられる.各枝の距離は $1$ である.
$2$ ノード間の距離が最大と成るようなノードの組を求める問題.
複数あるなら,その中の $1$ つのみを出力すれば良い.
ある $1$ つのノードから全ノードまでの距離を求めるのはBFSを行えば良い.
自由に選んだあるノードから最も遠い場所にあるノードを $1$ つ選んできて $x$ とする.
$x$ から最も遠い場所にあるノードを $1$ つ選んできて $y$ とする.
すると答えは $(x,y)$ となる.
理由は,最も $2$ ノード間のパスの中点(ちょうど真ん中)を考える.真ん中はノードか枝の途中かはわからない.
中点でぶった切って $2$ つ(以上)の領域に分けると,$x$ は最初に選んだ $1$ つのノードの領域ではない領域で,中点から最も遠い距離にあることになる.
ここで,中点から $x$ までの距離は,最も遠い $2$ ノード間の距離のちょうど半分.
$y$ についても同様で,$x$ と違う領域で,中点からの距離は最も遠い $2$ ノード間の距離のちょうど半分になる.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}
int N, A[100010];
int c[100100];
int main(){
int i, j, k, st;
int res = 0;
reader(&N);
rep(i,N) reader(A+i);
st = 0;
rep(i,N){
while(c[A[i]]){
c[A[st]]--;
st++;
}
c[A[i]]++;
res = max(res, i-st+1);
}
writer(res, '\n');
return 0;
}
Current time: 2024年04月27日04時37分27秒
Last modified: 2014年05月10日03時04分54秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC022 ARC_C
トップページに戻る
Logged in as: unknown user (not login)