AtCoder Beginner Contest 097

ABc-で2完+部分点でした. Cが厳しかった.

A - Colorful Transceivers

CとAの距離がd以下ならばAとCは直接会話できるので"Yes".
AとBの距離がd以下かつCとAの距離がd以下ならばAとCは間接的に会話できるのでこれも"Yes".
それ以外は"No".

#include <bits/stdc++.h>

using namespace std;

int abs(int x) {
  if(x < 0) {
    return (-1) * x;
  }
  else {
    return x;
  }
}

int main(void) {
  int a, b, c, d;
  cin >> a >> b >> c >> d;

  if(abs(c - a) <= d) {
    cout << "Yes" << endl;
  }
  else if(abs(b - a) <= d && abs(c - b) <= d) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

B - Exponential

2以上X未満の数をべき乗して作れる1000未満の数を全探索して最大のものを出力する.
何故かエラトステネスのふるいが貼っつけられてますが別にいらない.

#include <bits/stdc++.h>
#define MAX_N 2000

using namespace std;

int prime[MAX_N];  // i番目の素数
bool is_prime[MAX_N + 1];  // is_prime[i]がtrueならiは素数

// n以下の素数の数を返す
int sieve(int n) {
  int p = 0;
  for(int i = 0; i <= n; i++) {
    is_prime[i] = true;
  }
  is_prime[0] = is_prime[1] = false;
  for(int i = 2; i <= n; i++) {
    if (is_prime[i]) {
      prime[p++] = i;
      for(int j = 2 * i; j <= n; j += i) {
	is_prime[j] = false;
      }
    }
  }
  return p;
}

int main(void) {
  int n = sieve(1001);
  int x;
  cin >> x;

  int mx = 1;
  for(int i = 2; i < x; i++) {
    int p = 0;
    int tmp = 1;
    while(tmp <= x) {
      tmp *= i;
      p++;
    }
    tmp /= i;
    p--;
    if(mx < tmp && 1 < p) {
      //      cout << "i: " << i << endl;
      mx = tmp;
    }
  }
  cout << mx << endl;
}

C - K-th Substring

コンテスト中は部分点のみ解いた.
部分文字列をsetに全部放り込んでそこからK番目に小さいものを出力する.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  string s;
  int k;
  cin >> s >> k;

  set <string> t;
  for(int i = 1; i <= s.length(); i++) {
    for(int j = 0; j < s.length() - i + 1; j++) {
      string u;
      for(int k = 0; k < i; k++) {
	u.push_back(s[j + k]);
      }
      t.insert(u);
    }
  }
  long long count = 0;
  for(auto i: t) {
    count++;
    if(count == k) {
      cout << i << endl;
      return 0;
    }
  }
}

よく見たら入力のkとfor文の添字のkかぶってるじゃん. よく部分点取れたな.

editorialによると答えの文字列の長さは高々Kとなる.
よってsetに入れるsubstringは長さK以下でO(NK)個.
これは思いつきたかったな. string.substr(i, j)の存在を知れたのは勉強になった.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  string S;
  int K;
  cin >> S >> K;

  set <string> t;
  for(int i = 1; i <= K; i++) {
    for(int j = 0; j + i - 1 < S.length(); j++) {
      string u = S.substr(j, i);
      t.insert(u);
    }
  }
  long long count = 0;
  for(auto i: t) {
    count++;
    if(count == K) {
      cout << i << endl;
      return 0;
    }
  }
}