CodeForces Round #686(Div.3)

CodeForces Round #686(Div.3)

#	Name	Input/output	Limit
A	Special Permutation	standard input/output	1 s, 256 MB
B	Unique Bid Auction	standard input/output	1 s, 256 MB
C	equence Transformation	standard input/output	1 s, 256 MB
D	Number into Sequence	standard input/output	3 s, 256 MB
E	umber of Simple Paths	tandard input/output	2s, 256 MB
F	Array Partition	standard input/output	2 s, 256 MB

A: “Special Permutation”

問題:
非負整数 n が与えられる。
[1～n]からなる長さnの順列P(p1,p2,….,pn-2,pn-1)で、pi≠i　を満たす順列を出力せよ。

解法:
pi = {(i+1) mod i} + 1
にすると条件を満たす。
計算量O(n)

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

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i){
      if(i!=n-1) cout << (i+1)%n+1 << " ";
      else cout << (i+1)%n+1 << endl;
    }
  }
  return 0;
}

B: “Unique Bid Auction”

問題:
長さnの配列aが与えられる。aの要素で、重複がないもので最小のものを求めよ。
存在しない場合は、”-1″を出力せよ。

解法:
配列を見て行って、重複のないような要素で最小のものを出力する。
存在しない場合-1にする。
計算量O(n)

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

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    vector<vector<int>> a(n);
    for(int i = 0; i < n; ++i){
      int t;
      cin >> t;
      a[t-1].push_back(i+1);
    }
    int ans = -1;
    for(int i = 0; i < n; ++i){
      if(a[i].size() == 1){
        ans = a[i][0];
        break;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

C: “Sequence Transformation”

問題:
長さnの配列aが与えられる。
aのすべての要素を、x(∈a)にしたい。
aの閉区間[l,r](ai≠x if l≤i≤r)を、削除する操作ができる。
最小の操作回数を求めよ。

解法:
各要素が、どの位置に存在するのかをmapでもっておく。
それぞれの要素で、要素間の距離が隣り合っていない場合、1回の削除操作が必要になる。
この操作の最小回数を追えばいい。
計算量O(n)

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

const int INF = 1e9;
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    vector<vector<int>> a(n);
    vector<int> cnt(n, INF);
    for(int i = 0; i < n; ++i){
      int t;
      cin >> t;
      a[t-1].push_back(i);
      if(a[t-1].size() == 1) cnt[t-1] = (i==0)?0:1;
      else{
        int prev = a[t-1][a[t-1].size()-2];
        if(i-prev==1) continue;
        else ++cnt[t-1];
      }
    }
    for(int i = 0; i < n; ++i){
      if(a[i].size() >= 1){
        cnt[i] = (a[i][a[i].size()-1]!=n-1)?cnt[i]+1:cnt[i]; 
      }
    }
    int ans = INF;
    for(int i = 0; i < n; ++i){
      ans = min(ans,cnt[i]);
    }
    cout << ans << endl;
  }
  return 0;
}

D: “Number into Sequence”

問題:
1より大きい整数nが与えられる。
以下の条件を満たすような配列aで、最大の長さの配列を求めよ。
・ai > 1
・ ∏ ai = n
・ai+1は、aj(1<=j<=i-1)で割り切れる

解法:
aの長さを最大にするときは、
nを素因数分解したときに最も多く含まれている素因数因子pを並べていったもの-1+あまり*pにするとき。
pをそのような素因数因子の中で最小のものとして、考えると背理法で証明できる。
O(log(n)^2)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int t;
  cin >> t;
  while(t--){
    ll n;
    cin >> n;
    int ans = 0, rec = INF;
    for(ll i = 2; i <= sqrt(n); ++i){
      ll nn = n;
      int cnt = 0;
      while(nn){
        if(nn%i != 0) break;
        nn /= i;
        ++cnt;
      }
      if(ans < cnt) rec = i, ans = cnt;
    }
    if(rec == INF){
      cout << "1\n";
      cout << n << endl;
    }else{
      cout << ans << "\n";
      for(int i = 0; i < ans-1; ++i){
        cout << rec << " ";
        n /= rec;
      }
      cout << n << endl;
    }
  }
  return 0;
}

E: “Number of Simple Paths”

問題:
G(V,E) = (n,n)の無向グラフが与えられる。
Gは連結である。
Gのパスの総数を求めよ。

解法:
n頂点に、n辺の連結グラフGを考えると、閉路を持つサブグラフ+木の構造になっていることがわかる。
各辺にかんして、ある頂点を含むような辺を重複なくカウントすると答えになる。
閉路を持つサブグラフの頂点集合に、木がくっつている
ような頂点vにかんして、その頂点vに隣接する頂点をqueueでもっておいて一回ずづ探索する。一回探索に使用した辺は削除する。
木の箇所は、(木の頂点集合の大きさ)(木の頂点集合の大きさ-1)/2で木のパスの総数が求まる。閉路を持つサブグラフと、v、vと隣接する頂点を結ぶようなパスは、(閉路を持つサブグラフの頂点の大きさ)(木の頂点集合の大きさ)で求まる。
計算量O(n)

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

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    vector<set<ll>> g(n);
    vector<ll> rec(n,1);
    queue<int> q;
    for(int i = 0; i < n; ++i){
      ll x, y;
      cin >> x >> y;
      x--,y--;
      g[x].insert(y);
      g[y].insert(x);
    }
    for(int i = 0; i < n; ++i){
      if(g[i].size() == 1){
        q.push(i);
      }
    }
    while(!q.empty()){
      int v = q.front();
      q.pop();
      ll to = *g[v].begin();
      rec[to] += rec[v];
      rec[v] = 0;
      g[v].clear();
      g[to].erase(v);
      if(g[to].size() == 1) q.push(to);
    }
    ll ans = 0;
    for(int i = 0; i < n; ++i){
      ans += rec[i] * (rec[i] - 1)/2 + rec[i] * (n - rec[i]);
    }
    cout << ans << endl;
  }
  return 0;
}

F: “Array Partition”

問題:
長さnの配列aが与えられる。
配列aを左から、a1,a2,a3の部分(size(ai)>0)に分割したときに、max(a1) = min(a2) = max(a3)を満たすように配列aを分割できるか？
(max(a1)は、a1の最大の要素、min(a2)は、a2の最小の要素)
できる場合は、分割位置を出力せよ。
できない場合は、Noを出力せよ。

解法:
a2の境界値の左端を順にみて行って、a1の最大値と、a3の最大値が等しくなるようにする。
まず、aを左端から見ていった時の、a[0,i]の最大値(d1)と、aを右端から見ていった時の、a[i,n-1]の最大値(d2)を計算しておく。
次に、aを左端から見ていったとき広義単調増加列となっている部分のa[0,i]の最大値(a1の最大値)と、(pref)
aを右端から見ていったとき広義単調減少列となっている部分の、a[i,n-1]の最大値(a3の最大値)を計算しておく。(suf)
a2の境界値の左端,lを決めたとき、a1の右端を2分探して、l以下の箇所のprefがa1の最大値以下で、a3の左端を2分探索して、l以上の箇所のsufがa3の最大値以下となっているかを調べる。
これが、満たされいるようなa1右端と、a3の左端が存在するとき条件を満たす。
計算量O(nlog(n))

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

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int t;
  cin >> t;
  while(t--){
    int n, flag = false;
    cin >> n;
    vector<int> a(n);
    vector<int> d1(n,0),d2(n,0);
    for(int i = 0; i < n; ++i){
      cin >> a[i];
      if(i==0) d1[i] = a[i];
      else d1[i] = max(a[i], d1[i-1]);
    }
    d2[n-1] = a[n-1];
    for(int i = n-2; i>= 0; --i) d2[i] = max(a[i], d2[i+1]);
    vector<int> pref(n,-1);
    vector<int> suf(n,n);
    stack<int> s1;
    stack<int> s2;
    for(int i = 0; i < n; ++i){
      while(!s1.empty() && a[s1.top()] >= a[i]) s1.pop();
      if(s1.empty()) pref[i] = -1;
      else pref[i] = s1.top();
      s1.push(i);
    }
    for(int i = n-1; i >= 0; --i){
      while(!s2.empty() && a[s2.top()] >= a[i]) s2.pop();
      if(s2.empty()) suf[i] = n;
      else suf[i] = s2.top();
      s2.push(i);
    }

    for(int i = 1; i < n-1; ++i){
      int l = 0, r = i-1, mid;
      int val1 = -2, val2 = n+1;
      while(r >= l){
        mid = (l+r)/2;
        if(d1[mid] == a[i]) val1 = mid, l = mid+1;
        else if(d1[mid] < a[i]) l = mid+1;
        else r = mid-1;
      }
      l = i+1, r = n-1;
      while(r >= l){
        mid = (l+r)/2;
        if(d2[mid] == a[i]) val2 = mid, r = mid-1;
        else if(d2[mid] > a[i]) l = mid+1;
        else r = mid-1;
      }
      if(pref[i] <= val1 && suf[i] >= val2){
        cout << "YES" << endl;
        cout << val1+1 << " " << n - (val1 + (n - val2 + 1) ) << " " << n - val2 << endl;
        flag = true;
        break;
      }
    }
    if(!flag) cout << "NO" << endl;
  }
  return 0;
}

終わりに

Div3は初心者向けにほとんど、アルゴリズムの知識を必要とされないコンテストです！

次回は、
Codeforces Round #687 (Div. 1, based on Technocup 2021 Elimination Round 2)
16:05JST
Sunday, 29 November 2020

是非楽しんでください！

その他のコンテスト

AtCoder: ABC184

Search