# Gori#020(ABC040)

問題セット

# B -

# 概要

NN枚のタイルを用いて隙間なく並べて長方形を作る(全て使用しなくとも良い).
このとき, 長方形の盾と横の長さの差の絶対値と, 余ったタイルの枚数を最小化せよ.

# 解法

制約より, タイルの枚数の上限は10510^5なので, 辺で全探索しても間に合う(枝刈りが必要).
したがって, 縦と横の辺で全探索し, 最小値を求めれば良い.

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

int main(){
  int n; cin >> n;
  int ans = n;  
  for(int i=0; i<=n; ++i){
    for(int j=0; j<=n; ++j){
      if (i*j > n) break;
      ans = min(ans, (n-i*j)+abs(j-i));
    }
  }
  cout << ans << endl;
  return 0;
}

# C - 柱柱柱柱柱

# 概要

NN本の柱があり, その高さはaia_iとする.
高橋くんは, ある柱から1個もしくは2個右にある柱のどちらかに移動することができる.
しかし, 移動するときは, 移動する先の柱の高さと現在いる柱の高さの差の絶対値の分だけコストがかかる.
現在11本目の柱にいて, NN本目の柱まで行くとき, コストの合計の最小値を求めよ.

# 解法

DPを用いる.

DPで重要なのは, 状態の持ち方と遷移の仕方である.
順番に考える.

  1. 状態の持ち方
dp[i] := i番目の柱にいるときの合計コストの最小値
  1. 遷移の仕方 高橋くんは, ある柱から1個もしくは2個右にある柱のどちらかに移動することが可能で, コストは現在いる柱との高さの差の絶対値である.
    したがって, 遷移は以下のようにかける.
if (i>0) dp[i] = min(dp[i], dp[i-1] + abs(a[i] - a[i-1]));
if (i>1) dp[i] = min(dp[i], dp[i-2] + abs(a[i] - a[i-2]));

以上をまとめてDPを用いれば良い.

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

int main(){
  int n; cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;++i) cin >> a[i];

  vector<int> dp(n+1, 1e9+1);
  dp[0] = 0;
  for(int i=0;i<n;++i){
    if (i>0) dp[i] = min(dp[i], dp[i-1] + abs(a[i] - a[i-1]));
    if (i>1) dp[i] = min(dp[i], dp[i-2] + abs(a[i] - a[i-2]));
  }

  cout << dp[n-1] << endl;
  return 0;
}

# D - 道路の老朽化対策について

# 概要

11からNNまでの番号がつけられているNN個の都市がある.
これらの都市にはyiy_i年に作られた都市aia_iと都市bib_iを結ぶ橋が, MM本ある.
ここで, 以下のようなクエリがQQ個与えられるので, それらに答えよ.

  • 都市vjv_jから出ている橋で, wjw_j年以前に作られた橋はいくつあるか?

# 解法

制約より, Q=2×105Q = 2 \times 10^5なので, 与えられた以下のクエリにはO(logM)O(logM)O(1)O(1)程度で計算できなければならないことが分かる.

  • 都市vjv_jから出ている橋で, wjw_j年以前に作られた橋はいくつあるか?

ここで, O(logM)O(logM)O(1)O(1)程度できるアルゴリズム, もしくはデータ構造を考えると, データの連結によるものなので, Union-Find木が出てくる.
(ちなみにO(α(N))O(\alpha(N))である.(ただし, α\alphaはアッカーマン関数))

しかし, Union-Find木を使うとしても, クエリ内の

  • wjw_j年以前に作られた橋はいくつあるか? という部分のせいで, wjw_j年以前であるものを列挙するためにO(M)O(M)が必要になる.

そこで,

  • 橋の情報を, 作られた年(yiy_i)をキーとして降順にソート
  • クエリの情報を, 年の条件(wjw_j)をキーとして降順にソート することにする(ソートはO(MlogM)O(MlogM)なので, 先に計算しておけば間に合う).
    そうすることで, 1度確認した都市がその後使われなくなることが無くなる.

したがって, まとめると

  • 橋の情報を降順にソート
  • クエリの情報を降順にソート
  • Union-Find木を生成
  • クエリを順番に見ていき, wjw_j以前という条件を満たす時に辺をマージ
  • 解を出力
    という順番に実装すればよい.
#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
  vector< int > par;
  UnionFind(int n = 1) {
    init(n);
  }

  void init(int n = 1) {
    par.assign(n, -1);
  }
  
  int root(int n) {
    if (par[n] < 0) return n;
    return par[n] = root(par[n]);
  }

  bool merge(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (par[x] > par[y]) swap(x, y);
    par[x] += par[y];
    par[y] = x;

    return true;
  }

  bool issame(int x, int y) {
    return root(x) == root(y);
  }

  int getSize(int x){
    return (-par[root(x)]);
  }
};

struct Edge {
  int fr, to, y;
};

struct Q {
  int fr, y, id;
};

int main() {
   int n, m;
   cin >> n >> m;
   vector< Edge > e(m);
   for(int i=0;i<m;++i) {
     cin >> e[i].fr >> e[i].to >> e[i].y;
   }

   sort(e.begin(), e.end(), [](Edge e1, Edge e2){ return e1.y > e2.y;});

   int qn; cin >> qn;
   vector< Q > q(qn);
   for(int i=0;i<qn;++i){
     cin >> q[i].fr >> q[i].y;
     q[i].id = i 
   }
   sort(q.begin(), q.end(), [&](const Q &q1, const Q &q2){return q1.y > q2.y;});

   vector< int > ans(qn, 0);
   UnionFind uf(n);
   int ei = 0;
   for(int qi=0;qi<qn;++qi){
     while (ei < m && q[qi].y < e[ei].y) {
       uf.merge(e[ei].fr, e[ei].to);
       ++ei;
     }
     ans[q[qi].id] = uf.getSize(q[qi].fr);
   }

  for(int i=0;i<qn;++i){
    cout << ans[i] << endl;
  }
               
  return 0;
}

以上.
お疲れ様でした.

# 参考資料

Editorial

Last Updated: 2019-9-5 12:38:33