Codeforces Round #418 (Div. 2)

おー.

oooo- 33rd. 1333 だけに(?)

A. An abandoned sentiment from past

codeforces.com

問題概要

長さ ${n(2 \le n \le 100)}$ の配列 ${a_i(0 \le a_i \le 200)}$ が与えられる.

また, 長さ ${k(1 \le k \le n)}$ の配列 ${b_i(1 \le b_i 200)}$ も与えられる.

配列 ${a_i}$ のうち ${k}$ 箇所は ${0}$ で, これらの要素を ${b_i}$ のいずれかで置き換える.

${0}$ 以外の値が複数回現れることはない.

上手く置き換えることで ${a_i}$ を非増加列にできるか判定せよ.

解法

やる.

${b_i}$ を降順ソートして, ${a_i}$ の左の ${0}$ から埋めていって判定すればよい.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N, K, A[100], B[100];
  cin >> N >> K;
  for(int i = 0; i < N; i++) cin >> A[i];
  for(int i = 0; i < K; i++) cin >> B[i];
  sort(B, B + K);
  int tail = 0;
  for(int i = N - 1; i >= 0; i--) {
    if(A[i] == 0) A[i] = B[tail++];
  }
  if([&]()
  {
    for(int i = 1; i < N; i++)
      if(A[i - 1] > A[i]) return (true);
    return (false);
  }())
    cout << "Yes" << endl;
  else cout << "No" << endl;
}

B. An express train to reveries

codeforces.com

問題概要

${2}$ つの長さ ${n(2 \le n \le 1000)}$ の配列 ${a_i, b_i(1 \le a_i, b_i \le n)}$ が与えられる.

それぞれの配列中では, ちょうど ${n - 1}$ 種類の値が現れる.

配列 ${a_i, b_i}$ とはちょうど ${1}$ 箇所だけ異なるような長さ ${n}$ の順列 ${p_i}$ を出力せよ.

解法

やる.

${p_i}$ は, ${a_i}$ 中で ${2}$ 個ある同じ値のうちどちらかを未出現の値に置換したものである.

それぞれ変えてみて, 条件を満たしているかどうかみればよい.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N, A[1000], B[1000];
  int v[1001] = {};

  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i], v[A[i]]++;
  for(int i = 0; i < N; i++) cin >> B[i];

  int latte, malta;
  vector< int > beet;
  for(int i = 1; i <= N; i++) {
    if(v[i] == 0) latte = i;
    else if(v[i] == 2) malta = i;
  }
  for(int i = 0; i < N; i++) {
    if(v[A[i]] == 2) beet.push_back(i);
  }

  for(int s : beet) {
    A[s] = latte;
    int diff = 0;
    for(int j = 0; j < N; j++) diff += A[j] != B[j];
    if(diff == 1) {
      for(int j = 0; j < N; j++) cout << A[j] << " ";
      cout << endl;
      return(0);
    }
    A[s] = malta;
  }
}

C. An impassioned circulation of affection

codeforces.com

問題概要

長さ ${n(1 \le n \le 1500)}$ の文字列 ${s}$ が与えられる.

最大で ${m_i(1 \le m_i \le n)}$ 個の文字を変更できるとき, 文字 ${c_i}$ のみからなる部分文字列の最長の長さを求める ${q(1 \le q \le 200 000)}$ 個のクエリが与えられるので全て処理せよ.

解法

尺取り法を適用することで, ${1}$ クエリあたり ${O(n)}$ で処理できる.

具体的には, 部分文字列の先頭を小さい方から固定して試す. 違う文字が ${m_i}$ 回までの出現は許されるので, その条件を満たす限り部分文字列の末尾を後ろにずらしていく.

最近のコンピュータははやいので ${O(nq)}$ が間に合う. やったぜ(マジか).

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N, Q;
  char buff[1505];

  scanf("%d", &N);
  scanf("%s", buff);
  scanf("%d", &Q);
  for(int i = 0; i < Q; i++) {
    int sz;
    char c;
    scanf("%d %c", &sz, &c);

    int ret = 0;
    int sum = 0, tail = 0;
    for(int k = 0; k < N; k++) {
      while(tail < N && sum + (buff[tail] != c) <= sz) {
        sum += buff[tail++] != c;
      }
      ret = max(ret, tail - k);
      sum -= buff[k] != c;
    }
    printf("%d\n", ret);
  }
}

D. An overnight dance in discotheque

codeforces.com

問題概要

${n(1 \le n \le 1000)}$ 個の円が与えられる. ${i}$ 番目の円は ${(x_i, y_i) (-10^6 \le x_i, y_i \le 10^6)}$ に位置し半径 ${r_i(1 \le r_i \le 10^6)}$ である.

すべての円は他の円と ${2}$ 点で共有することはない.

円を ${2}$ グループに分け, それぞれで奇数個の円が重なっている部分の面積を計算する.

面積の和の最大値を求めよ.

解法

木に変換して木DPでえい.

円の重なりの関係を木に変換すると, 複数の根付き木になる.

それぞれの根付き木に対して, ${2}$ グループに分けた時の最大値を求める.

dp[idx][mod1][mod2] := 円 ${idx}$ の部分木で, 祖先の円についてグループ ${1}$ は ${mod1\%2}$ 個, グループ ${2}$ は ${mod2 \%2}$ 個使ったときの最大面積と定義する.

遷移はソースコードを見たほうが分かりやすい(語彙力がなくて説明できないいつものアレ(悲しい

その円をグループ ${1}$ , グループ ${2}$ に入れる場合の最大面積を求めて, 最大を返せば良い.

計算量は ${O(n^2)}$ となる.

貪欲解もあるらしい(賢い).

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 INF = 1LL << 60;

#define SQR(x) ((x)*(x))

int N;
int64 X[1000], Y[1000], R[1000];
vector< int > g[1001];
int64 dp[1001][2][2];

int64 dfs(int idx, bool sum1, bool sum2)
{
  if(~dp[idx][sum1][sum2]) return (dp[idx][sum1][sum2]);
  int64 latte = 0, malta = 0;
  latte += SQR(R[idx]) * (sum1 ? 1 : -1);
  malta += SQR(R[idx]) * (sum2 ? 1 : -1);
  for(auto &to : g[idx]) {
    latte += dfs(to, sum1 ^ 1, sum2);
    malta += dfs(to, sum1, sum2 ^ 1);
  }
  return(dp[idx][sum1][sum2] = max(latte, malta));
}

int main()
{
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i] >> R[i];
  }
  for(int i = 0; i < N; i++) {
    int64 dist = INF, connect = 1000;
    for(int j = 0; j < N; j++) {
      if(i == j) continue;
      if(R[i] >= R[j]) continue;
      const int64 beet = SQR(X[i] - X[j]) + SQR(Y[i] - Y[j]);
      if(beet <= R[j] * R[j] && dist > R[j]) {
        dist = R[j];
        connect = j;
      }
    }
    g[connect].push_back(i);
  }
  memset(dp, -1, sizeof(dp));
  int64 ret = 0;
  for(auto &to : g[1000]) ret += dfs(to, 1, 1);
  cout << fixed << setprecision(12) << ret * acos(-1) << endl;
}

ei1333の日記

ぺこい

Codeforces Round #418 (Div. 2)

A. An abandoned sentiment from past

問題概要

解法

ソース

B. An express train to reveries

問題概要

解法

ソース

C. An impassioned circulation of affection

問題概要

解法

ソース

D. An overnight dance in discotheque

問題概要

解法

ソース