ABC066

ABC066

テンプレは省略

A

sortして先頭2つを取っておわり．

ソース

#include <bits/stdc++.h>
using namespace std;

signed main() {
  int a[3];
  rep(i, 3) cin >> a[i];
  sort(all(a));
  print(a[0] + a[1]);
}

B

与えられた文字列が偶数の長さで，半分に割ったときに左右で一致していれば偶文字列と分かるのでsubstrで分割してあげる．

ソース

#include <bits/stdc++.h>
using namespace std;

signed main() {
  string s;
  cin >> s;
  int res = 0;
  
  while (true) {
    string a, b;
    s.erase(s.begin() + s.size() - 1);
    res++;

    if (s.size() % 2 != 0) continue;
    a = s.substr(0, s.size() / 2);
    b = s.substr(s.size() / 2, s.size());
    if (a == b) {
      break;
    }
  }
  print(s.size());
}

C

反転して末尾にpushしていくのは，先頭と末尾へ交互にpushしていくことと変わらないのはすぐに分かる． 先頭・末尾へのpush，アクセスが高速なデータ構造といえばdequeであるから，この子を丁寧に扱ってあげると答えに導いてくれる．

ソース

#include <bits/stdc++.h>
using namespace std;
 
signed main() {
  deque<int> q;
  int n = in();
  
  rep(i, n) {
    int a = in();
    if (i % 2 != 0) q.push_back(a);
    else q.push_front(a);
  }

  if (n % 2 != 0) {
    rep(i, n - 1) {
      cout << q[i] << " ";
    }
    print(q[q.size() - 1]);
  } else {
    rrep(i, q.size() - 1, 1) {
      cout << q[i] << " ";
    }
    print(q[0]);
  }
}

D

逆元を用いたの実装が分からず，時間内に解けなかった．

個の数が必ず一つ以上使われている長さの数列から，長さの部分列の個数を出力する問題．

(組み合わせ)を使う．

そのままやってしまうと重複部分を数えてしまうので，重複分を引いてあげる．

(長さの部分列の個数)

が重複分(は被った2つの数字の数列上での距離)

逆元と親身に接することで答えがでる．

ソース

#include <bits/stdc++.h>
using namespace std;

lint fact[100010], ifact[100010];

lint pow(lint a, lint k) {
  if (k == 0) return 1;
  lint res = pow(a, k / 2);
  res = res * res % MOD;
  if (k & 1) res = res * a % MOD;
  return res;
}

lint inv(lint a) {
  return pow(a, MOD - 2);
}

lint C(lint n, lint r) {
  if (n < 0 || r < 0 || r > n) return 0;
  if (r > n / 2) r = n - r;
  return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}

signed main() {
  lint n = in();
  int N = n + 1;

  fact[0] = ifact[0] = 1;
  rep(i, 1, 100010) {
    fact[i] = (fact[i - 1] * i) % MOD;
    ifact[i] = inv(fact[i]);
  }

  int d = -1;
  int used[100010];
  fill(all(used), -1);

  rep(i, N) {
    int a;
    cin >> a;
    if (used[a] != -1) {
      d = i - used[a];
    }
    used[a] = i;
  }

  rep(i, N) { print((C(N, i + 1) - C(N - d - 1, i) + MOD) % MOD); }
}

1125 -> 1173(+48, Highest!!)

はやいところ水色になりたいです