活動日記 day 27

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest

コメント :
木の直径の求め方を覚えましょう。

A : 高橋くんと年齢
解法 1
実際にソートして真ん中を出力

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
int main() {
  int arr[3];
  rep(i,3) cin >> arr[i];
  sort(arr,arr+3);
  cout << arr[1] << endl;
  return 0;
}

解法 2
総和 - 最大値 - 最小値

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
  int a,b,c;
  cin >> a >> b >> c;
  cout << ( a + b + c ) - max(a,max(b,c)) - min(a,min(b,c)) << endl;
  return 0;
}

B: 高橋くんと文字列圧縮
その通りにシミュレーションしましょう。

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
int main() {
  string s;
  cin >> s;
  rep(i,(int)s.size()) {
    cout << s[i];
    int cnt = 1;
    int sp = i;
    while( i+1 < (int)s.size() && s[sp] == s[i+1] ) {
      ++cnt, ++i;
    }
    cout << cnt;
  } puts("");
  return 0;
}

C: 高橋くんと魔法の箱
入力で与えられた各値について、２で割る限り割り続けます。
その後に残った値の種類の数が答えです。

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int n,a[100010];
 
int main() {
  cin >> n;
  rep(i,n) {
    cin >> a[i];
    while( a[i] % 2 == 0 ) a[i] /= 2;
  }
  set<int> S;
  rep(i,n) S.insert(a[i]);
  cout << (int)S.size() << endl;
  return 0;
}

D: 高橋くんと木の直径
木の直径の求め方をそのまま実行します。
木の直径の求め方は以下の通りです。
1. どこでも良いので１つノードを選んでそこから最も遠いノードxを求めます。
2. 先ほど求めたノードxから最も遠いノードyを求めます。
xとyの距離が木の直径です。

詳細はあり本に蟻ます。

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int main() {
  int n,v;
  cin >> n;
  vector<int> dist1;
  dist1.push_back(0);
  REP(i,1,n) {
    cout << "? 1 " << i+1 << endl;
    cin >> v;
    dist1.push_back(v);
  }
  int next_sp = 0;
  REP(i,1,n) {
    if( dist1[next_sp] < dist1[i] ) next_sp = i;
  }
  int maxi = 0;
  rep(i,n) {
    if( i != next_sp ) {
      cout << "? " << next_sp+1 << " " << i+1 << endl;
      cin >> v;
      maxi = max(maxi,v);
    }
  }
  cout << "! " << maxi << endl;
  return 0;
}