OneKuma

OneKuma's Blog

One Lonely Kuma.
github
bilibili
twitter
ホームアーカイブ作品集紹介

Codeforces Round 935 (Div. 3) 解説

#XCPC112
AI 翻訳
この記事はAIを通じて中国語から日本語に翻訳されました。原文を表示
AI が生成した要約
"比赛包括设置营地，点烟火，左右房屋和Seraphim the Owl。在设置营地中，需要确定最少需要多少个帐篷才能满足条件。在点烟火中，需要计算同时绽放的最大烟火数量。在左右房屋中，需要安排住户使得左右两边满足条件且距离中点最小。在Seraphim the Owl中，需要确定最优跳跃位置。"

コンテスト

A. キャンプの設営#

3 種類の人がテントに住む必要があり、それぞれ aa、bb、cc 人います。最初の種類の人は小波奇で、彼は一人で住むことを望んでいます。2 番目の種類の人は喜多で、彼は必ず他の 2 人と一緒に住む必要があります。3 番目の種類の人は特に気にしません。各テントには最大 3 人まで住むことができる場合、最小でいくつのテントが必要ですか？

小波奇は一人で住み、喜多はできるだけ内部でチームを組み、3 番目の人が喜多の空きスペースを埋め、その後 3 で割って切り上げます。

B. 花火#

2 種類の花火があり、それぞれ 0,a,2a,3a,…0,a,2a,3a,\dots と 0,b,2b,3b,…0,b,2b,3b,\dots の時刻に開花します。毎回の開花は m+1m+1 単位の時間続き、つまりそれぞれ [0,m],[a,a+m],[2a,2a+m],[3a,3a+m],…[0,m],[a,a+m],[2a,2a+m],[3a,3a+m],\dots と [0,m],[b,b+m],[2b,2b+m],[3b,3b+m],…[0,m],[b,b+m],[2b,2b+m],[3b,3b+m],\dots の時刻に開花します。すべての時刻に対して、同時に最大でいくつの花火が開花しているかを求めてください。

明らかに、mm の時刻にいくつの花火が開花しているかを見ればよく、答えは (1+⌊ma⌋)+(1+⌊mb⌋)(1 + \lfloor \frac{m}{a} \rfloor) + (1 + \lfloor \frac{m}{b}\rfloor) ​ です。

C. 左右の家#

nn 人の住民がいる通りがあり、道路によって左右に分けられています。各住民には左側または右側に住む意向 a1,a2,…,ana_1, a_2, \dots, a_n があります。今、あなたはこの道路の位置を配置する必要があります。左右の両側には、住民数を 2 で割って切り上げた人数が満足する必要があり、かつその距離を最小化し、道路の座標も最小化する必要があります。

条件は多いですが、左から右に道路をどこに置くかを列挙するだけで済み、前後に前方和を記録すれば、合法性を迅速に判断できます。

D. セラフィムフクロウ#

長さ nn の列があり、あなたは現在列の最右端（座標 n+1n+1）に立っています。現在位置 ii にいると仮定すると、毎回左側の位置 j<ij < i にジャンプすることができ、そのコストは aj+∑k=j+1ibka_j + \sum_{k=j+1}^{i} b_k です。あなたの目標は、mm 以下のある位置にジャンプすることで、最小コストを求めます。

元の問題は、各位置からコスト aia_i または bib_i を選ぶことに相当します。なぜなら、各位置はその中から一つを選んで一度だけ計算し、最後のコストは aia_i であるため、合法的なジャンププランを構築できます。注意が必要なのは、最後の落下点は [1,m][1,m] のどこかである必要があることです。なぜなら、bb が非常に小さく aa が非常に大きい場合があるからです。

E. 二分探索#

長さ nn の無秩序な配列が与えられ、最大 2 回まで任意の 2 つの位置を交換して、この配列に対して二分探索を実行して答えを見つけることができます。

一見すると、二分探索が正しく動作するために長さ ⌊log⁡2n⌋\lfloor \log_2n \rfloor の列を構築する必要があるように思えますが、実際にはそれは間違いです。二分探索の過程は乱雑ですが、確かに目標範囲を唯一のものに縮小しています。私たちは実際にはそれを自由に実行させ、その後答えを自由に実行された目標位置に置くだけで済みます。

二分探索の過程でどの位置を訪れたかをマークし、残りの位置は自由に交換でき、最後に動かしていない位置を見つけて交換すればよいです。注意が必要なのは、自由に二分探索を行っている過程で、途中で答えを見つけた場合、追加で一回の操作を行い、答えを別の場所に移動させる必要があることです。

要するに、こんな感じで、適当に書きましたが、通過できるはずです。

F. キリルとキノコ#

nn 個のキノコが与えられ、それぞれのキノコには重み a1,a2,a3,…,ana_1,a_2,a_3,\dots,a_n があります。あなたはその中から kk 個のキノコを選ぶことができ、重みは選ばれたキノコの重みの最小値に kk を掛けたものです。さらに制約として、p1,p2,p3,…,pnp_1, p_2, p_3, \dots, p_n という配列があり、選んだ kk 個のキノコに対して、これらの ap1,ap2,…,apk−1a_{p_1}, a_{p_2}, \dots, a_{p_{k-1}} のキノコの重みがクリアされ、選択できなくなります。最大の重みを求める前提で、最小の選択個数を求めてください。

11 から nn まで（おそらく半分程度まで）いくつのキノコを選んだかを列挙し、残りのキノコの上位 kk を維持し、対応するキノコをクリアします。

おそらく直接ヒープを使うことができると感じますが、考えたくないので、直接セグメントツリーを使って上位 kk​ を維持しました。

G. 料理とお粥#

nn 人が食事をするために列を成しており、彼らの列の中での順序に関するルールがあります。DD 時刻内に各人が一度食べることができるか、または不可能であることを報告してください。

書いていませんが、何かデータ構造を維持して処理する必要があると感じます。詳細を書くのが面倒です。

H. GCD が大きい#

サイズが nn の配列が与えられ、あなたはそれを 2 つのブロックに分ける必要があります。各ブロックには少なくとも 2 つの要素が含まれ、最初のブロックの gcd⁡\gcd を求め、2 番目のブロックの bitwiseAND⁡\operatorname{bitwise AND} にパラメータ xx を加えます。最初のブロックの重みが厳密に 2 番目のブロックより大きい分割方案が存在するかどうかを求めます。

明らかに、最初のブロックの gcd⁡\gcd の数は 2 つあれば十分です。なぜなら、数が多いほど gcd⁡\gcd は小さくなるからです。同様に、bitwiseAND⁡\operatorname{bitwise AND}​ も数が多いほど小さくなりますが、目標に合致します。

したがって、私は直接 gcd⁡\gcd を列挙し、どのように判定するかを考えればよいと思いますが、書いていないし、深く考えていないので、たぶんできるはずです。

コード#

A. キャンプの設営#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, a[maxn];

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  int T;
  scanf("%d", &T);
  while (T--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    int cnt = a;
    cnt += b / 3;
    b %= 3;
    if (b > 0 && b + c < 3) {
      puts("-1");
      continue;
    } else {
      if (b > 0) {
        c -= 3 - b;
        cnt++;
      }
      cnt += (c + 2) / 3;
      printf("%d\n", cnt);
    }
  }

  return 0;
}

B. 花火#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  int T;
  scanf("%d", &T);
  while (T--) {
    long long a, b, m;
    scanf("%lld%lld%lld", &a, &b, &m);
    long long ans = 2 + m / a + m / b;
    printf("%lld\n", ans);
  }

  return 0;
}

C. 左右の家#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, pre[maxn], suf[maxn];
char buf[maxn];

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%s", &n, buf + 1);
    pre[0] = 0; suf[n + 1] = 0;
    for (int i = 1; i <= n; i++) {
      pre[i] = pre[i - 1] + (buf[i] == '0');
    }
    for (int i = n; i >= 1; i--) {
      suf[i] = suf[i + 1] + (buf[i] == '1');
    }
    pre[n + 1] = pre[n]; suf[0] = suf[1];

    auto check = [&](int p) {
      int l = pre[p];
      int r = suf[p + 1];
      return l >= (p + 1) / 2 && r >= (n - p + 1) / 2;
    };
    int ans = -1;
    for (int i = 0; i <= n; i++) {
      if (check(i)) {
        if (ans == -1 || abs(n - ans - ans) > abs(n - i - i)) {
          ans = i;
        }
      }
    }
    assert(ans != -1);
    printf("%d\n", ans);
  }

  return 0;
}

D. セラフィムフクロウ#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, m, a[maxn], b[maxn];

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
      scanf("%d", a + i);
    }
    for (int i = 1; i <= n; i++) {
      scanf("%d", b + i);
    }

    long long ans = 0, mn = a[m], sum = 0;
    for (int i = n; i > m; i--) {
      ans += min(a[i], b[i]);
    }
    for (int i = m; i >= 1; i--) {
      mn = min(mn, a[i] + sum);
      sum += b[i];
    }
    printf("%lld\n", ans + mn);
  }

  return 0;
}

E. 二分探索#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, x, a[maxn];

void check() {
//  for (int i = 1; i <= n; i++) {
//    printf("%d%c", a[i], " \n"[i == n]);
//  }

  int l = 1, r = n + 1;
  while (r - l > 1) {
    int m = (l + r) / 2;

    if (a[m] <= x) {
      l = m;
    } else {
      r = m;
    }
  }
//  printf(": %d %d\n", l, a[l]);

  assert(r - l == 1 && a[l] == x);
}

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &x);
    for (int i = 1; i <= n; i++) {
      scanf("%d", a + i);
    }

    vector<pair<int,int>> ans;

    int l = 1, r = n + 1;
    vector<int> visited(n + 1, 0);
    while (r - l > 1) {
      int m = (l + r) / 2;

      if (a[m] == x && r - l > 1) {
        int found = -1;
        for (int i = 1; found == -1 && i <= n; i++) {
          if (!visited[i]) found = i;
        }
        assert(found != -1);
        ans.push_back({ m, found });
        swap(a[m], a[found]);
      }

      visited[m] = 1;

      if (a[m] <= x) {
        l = m;
      } else {
        r = m;
      }
    }

    if (a[l] != x) {
      int found = -1;
      for (int i = 1; found == -1 && i <= n; i++) {
        if (a[i] == x) found = i;
      }
      assert(found != -1 && !visited[found]);
      visited[found] = 1;

      ans.push_back({ found, l });
      swap(a[found], a[l]);
    }

    printf("%d\n", (int) ans.size());
    for (auto& p: ans) {
      printf("%d %d\n", p.first, p.second);
    }

    check();
  }

  return 0;
}

F. キリルとキノコ#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

struct BIT {
  static const int R = 1 << 21;

  int a[R];

  inline int lowbit(int x) { return x & -x; }

  void insert(int i, int v) {
    for (; i < R; i += lowbit(i)) a[i] += v;
  }
  void clear(int i) {
    for (; i < R; i += lowbit(i)) a[i] = 0;
  }

  int findx(int p, int rk) {
    // if (p > R) return -1;
    if (p & 1) {
      // if (p + (a[p] < rk) > R) return -1;
      return p + (a[p] < rk);
    } else {
      if (rk > a[p]) return findx(p + lowbit(p) / 2, rk - a[p]);
      else return findx(p - lowbit(p) / 2, rk);
    }
  }
  int findx(int rk) {
    return findx(R >> 1, rk);
  }
} f;

int n, a[maxn], p[maxn];

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);

    vector<int> lsh;
    auto gid = [&](int x) -> int {
      return int(lsh.end() - lower_bound(lsh.begin(), lsh.end(), x));
    };

    for (int i = 1; i <= n; i++) {
      scanf("%d", a + i);
      lsh.push_back(a[i]);
    }
    for (int i = 1; i <= n; i++) {
      scanf("%d", p + i);
    }

    sort(lsh.begin(), lsh.end());
    lsh.resize(unique(lsh.begin(), lsh.end()) - lsh.begin());
    for (int i = 1; i <= n; i++) {
      f.insert(gid(a[i]), 1);
    }

    long long ans = 0;
    int cnt = 0;
    for (int i = 1; i + i - 1 <= n; i++) {
      int id = f.findx(i);
      int val = lsh[lsh.size() - id];
//      printf("Find: %d %d\n", id, val);
      if (1ll * val * i > ans) {
        ans = 1ll * val * i;
        cnt = i;
      }

      // Delete
      f.insert(gid(a[p[i]]), -1);
    }

    printf("%lld %d\n", ans, cnt);

    for (int i = 1; i <= n; i++) f.clear(gid(a[i]));
  }

  return 0;
}
読み込み中...
文章は、創作者によって署名され、ブロックチェーンに安全に保存されています。