ABC170自分なりのまとめ - 盆栽エンジニアリング日記

A- Five Variables

順番に変数を読み込んでいって0で会った場所を出力すればよいです。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  rep(i, 5) {
    int x;
    cin >> x;
    if (x == 0) {
      cout << i + 1 << endl;
      return 0;
    }
  }
}

B- Crane and Turtle

鶴の数を固定してfor文を回せば良いです。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  int x, y;
  cin >> x >> y;
  for(int i = 0; i <= x; i++)
  {
    int reg = 2 * i + 4 * (x - i);
    if (reg == y) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

C- Forbidden List

p_iの範囲が1~100と狭いため、候補を全探索することを考えます。
問題文では負の整数についての言及がありますが、p_iの範囲から必ず0~101に解があることがわかります。
あとは、0~101の範囲の整数について、p_iに存在しないかを確かめながら絶対値が最小のものを探せばよいです。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  int x, n;
  cin >> x >> n;
  v p(n, 0);
  rep(i, n) {
    cin >> p[i];
  }
  int result = x;
  int num = 0;
  rep(i, 102) {
    bool exit = false;
    rep(j, n) {
      if (p[j] == i)  exit = true;
    }
    if (!exit) {
      if (result > abs(x - i)) {
        result = abs(x - i);
        num = i;
      }
    }
  }
  cout << num << endl;
}

D- Not Divisible

強引な解法で通してしまいました。
具体的には、A_iをmapで保存しておき、各A_iについて約数列挙を行い、その約数がA_iに存在しないかを判定しました。
計算量的には、O(N * sqrt(A_{max}))となり2 * 10⁸なのでテストケースによっては間に合わない気がします。
運が良かったです。
想定解法はdpを使うようです。
公式のPDFがわかりやすいのでそちらを参照してください。
僕の解法のように、すべての約数を列挙する必要はないということですね。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

map<int, int> memo;

bool check(int a) {
  for(int i = 2; i * i <= a; i++) {
    if (a % i == 0) {
      if (memo.count(i)) {
        return false;
      }
      if (memo.count(a / i)) {
        return false;
      }
    }
  }
  if (memo[a] != 1) return false;
  if (a != 1 && memo.count(1)) return false;
  return true;
}

int main()
{
  int n;
  cin >> n;
  v a(n, 0);
  rep(i, n) {
    cin >> a[i];
    memo[a[i]]++;
  }
  int count = 0;
  rep(i, n) {
    bool result = check(a[i]);
    if(result) count++;
  }
  cout << count << endl;
}

E- Smart Infants

コンテスト後にAC
基本的な方針としては、各幼稚園における最大値を保持しておき、転園時に転園元と転園先の最大値を更新し、最大値の最小値を取得することを考えます。
このときに必要になるのが、

各幼稚園に所属している園児の降順リスト(レートについて)
各幼稚園の最大値の最小値を取得する方法

です。
最初の要件についてはプライオリティキューを用いることで解決することができます。
プライオリティキューには、レートと園児の番号をペアにして入れておき、転園元の最大値の更新の際には、所属が変わっていない園児が手に入るまでキューをpopするような処理を行えば良いです。
転園先の最大値の更新は単純にプライオリティキューにpushするだけで良いです。
この操作はO(Q)回しか行われません。
2つめの要件については、各幼稚園の最大値を管理するセグメントツリーを用いることで解決できます。
以上を組み合わせることで解を高速に求めることができます。
コードが汚くてすみません。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
//エイリアス
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int n;
int m;
int q;
int t = 2 * 100000;

//セグ木

const ll MAX_N = 1 << 20;

//セグメント木を持つグローバル配列
ll dat[2 * MAX_N - 1];

//初期化
void init_seg(int n_)
{
    //簡単のため、要素数を2のべき乗に
  m = 1;
    while(m < n_)
    {
        m *= 2;
    }
    //全ての値をINT_MAXに
    for (int i = 0; i < 2 * m -1; i++)
    {
        dat[i] = llmax;
    }
}

//k番目の値(0-indexed)をaに変更
void update(int k, ll a)
{
    //葉の節点
    k += m - 1;
    dat[k] = a;
    //登りながら更新
    while(k > 0)
    {
        k = (k - 1) / 2;
        dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
}

//[a, b)の最小値を求める
//後ろの方の引数は、計算の簡単のための引数
//kは節点の番号,l,rはその節点が[l, r)に対応づいていることを表す
//したがって外からはquery(a, b, 0, 0, n)として呼ぶ
ll query_(int a, int b, int k, int l, int r){
    //[a, b)と[l, r)が交差しなければ、INT_MAX
    if(r <= a || b <= l){ 
        return llmax;
    }

    //[a, b)が[l, r)を完全に含んでいれば、この節点の値
    if(a <= l && r <= b)
    {
        return dat[k];
    }else{
        //そうでなければ,2つの子の最小値
        ll vl = query_(a, b, k * 2 + 1, l, (l + r) / 2);
        ll vr = query_(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
}

vl rates, belongs, emax;
vector<priority_queue<pl>> eq;

//初期化処理
void init() {
  cin >> n >> q;
  m = t;
  rates.resize(n, 0);
  belongs.resize(n, 0);
  emax.resize(t, -1);
  eq.resize(t);
}

//有効な園児が得られるまでキューから取り出す
void qpop(int school_num) {
  int next = eq[school_num].top().second;
  while(belongs[next] != school_num) {
    eq[school_num].pop();
    if (eq[school_num].empty()) break;
    next = eq[school_num].top().second;
  }
}

int main()
{
  //データの読み込み
  init();
  //セグ木の初期化
  init_seg(t);
  rep(i, n) {
    ll a;
    int b;
    cin >> a >> b; b--;
    rates[i] = a;
    belongs[i] = b;
    eq[b].push({a, i});
    emax[b] = max(emax[b], a);
    update(b, emax[b]);
  }
  vl result;
  //初期解の生成
  ll maxmin = query_(0, t, 0, 0, t);
  //転校処理
  rep(i, q) {
    int c, d;
    cin >> c >> d; c--; d--;
    //転校前の幼稚園
    int ex = belongs[c];
    //転校先の最大値の更新と解の更新
    belongs[c] = d;
    eq[d].push({rates[c], c});
    emax[d] = max(emax[d], rates[c]);
    update(d, emax[d]);
    maxmin = query_(0, t, 0, 0, t);
    //転校元の最大値の更新と解の更新
    if (eq[ex].top().second == c) {
      qpop(ex);
      if ( !eq[ex].empty() ) {
        emax[ex] = eq[ex].top().first;
        update(ex, emax[ex]);
      } else{
        emax[ex] = -1;
        update(ex, llmax);
      }
      maxmin = query_(0, t, 0, 0, t);
    }
    result.push_back(maxmin);
  }
  for (auto e : result) cout << e << endl;
}