AtCoder Regular Contest #022 C問題 - ロミオとジュリエット

Source

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$ ノード間の距離のちょうど半分になる.

C++によるスパゲッティなソースコード

#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年03月29日05時54分09秒
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)

ログイン: