AtCoder 勉強記録[C++] その13

AtCoderで入茶を目指して勉強しています。
勉強を継続するために投稿を始めました。
もともとアカウントを作成していましたが、今年の4月から本格的に勉強を始めました。
一応自分用に解法を書いていますが雑です、自分で読み返して困ったら修正します。
私のアカウント
解いた問題

本日解いた問題

C - Make Them Narrow

C - Make Them Narrow
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ll n, k;
  cin >> n >> k;
  vec a(n);
  rep(i, n) cin >> a[i];
  sort(a.begin(), a.end());
  ll res = INT_MAX;
  rep(i, k+1){
    res = min(res, a[i+n-k-1] - a[i]);
  }
  cout << res << endl;
}

解法

Aを昇順にソートしたとき、Aの要素のうちiからi+N-Kまでの部分数列を考える。このとき(i+N-K)からiを引いた時の最小値を探索する。

C - kasaka

C - kasaka
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  string s;
  cin >> s;
  ll n = s.size();
  ll x = 0;
  rep(i, n){
    if(s[i] == 'a') x++;
    else break;
  }
  ll y = 0;
  for(int i = n-1; i >= 0; i--){
    if(s[i] == 'a') y++;
    else break;
  }
  if(x == n) {
    cout << "Yes" << endl;
    exit(0);
  }
  if(x > y) {
    cout << "No" << endl;
    exit(0);
  }
  for(int i = x; i < n-y; i++){
    if(s[i] != s[x+n-y-i-1]){
      cout << "No" << endl;
      exit(0);
    }
  }
  cout << "Yes" << endl;
}

解法

先頭から連続するaの個数と末尾から連続するaの個数について考える。aは先頭に付け加えるため、末尾のaの個数より先頭の個数が多いときは必ず回文にならない。また、すべての要素がaの場合は必ず回文になる。それ以外の場合について、末尾の連続したaと先頭から連続したaを除いた文字列が回文だった場合、aを加えたら回文になる。

C - Knight Fork

C - Knight Fork
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
vector<ll> movex = {1,2,1,2,-1,-2,-1,-2};
vector<ll> movey = {2,1,-2,-1,2,1,-2,-1};
int main() {
  ll x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  for(int i = 0; i < 8; i++){
    ll mx = x1 + movex[i];
    ll my = y1 + movey[i];
    if((x2 - mx)*(x2 - mx) + (y2 - my)*(y2 - my) == 5){
      cout << "Yes" << endl;
      exit(0);
    }
  }
  cout << "No" << endl;
}

解法

x1、y1から√5の距離になる格子点は8つしか存在しない。そのため、x1、y1を移動するための配列を用意しておきすべての格子点においてx2、y2との距離が√5となるかを判定する。

C - Yamanote Line Gam

C - Yamanote Line Gam
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

vector<bool> jud(2002, false);

int main(void) {
  ll n;
  cin >> n;
  while(1){
    for(int i = 1; i < 2*n+2;i++){
      if(!jud[i]) {
        jud[i] = true;
        cout << i << endl;
        break;
      }
    }
    ll a;
    cin >> a;
    if(a==0) exit(0);
    jud[a] = true;
  }
  return 0;
}

解法

無限ループを利用して実装する。相手の入力が0になったときループから抜けて終了する。