ferinの競プロ帳

競プロについてのメモ

SRM614 div1 easy MinimumSquare

SRM 競技プログラミング

概要

xy座標上の点がn個与えられる。このうち少なくともk点を含むような正方形のうち面積が最小のものを求めろ。

考えたこと

x座標、y座標でそれぞれソートして小さい方からk点取る貪欲をしようとする。正方形を長方形だと誤読したりなぜか実装をバグらせたりした結果1時間くらい実装にかかる。サンプルを試すと落ちる。よくよく考えてみると貪欲が嘘。二分探索を思い浮かべ幅Xの正方形をつくることができるかの判定について考えてみる。各頂点が正方形の4隅になるパターンを試して判定するコードを実装するとサンプルが通った。提出するとシステスで落ちる。よくよく考えると二分探索の判定が嘘（4隅以外にすべきパターンが自明に存在する）。
解説記事を読むと2辺固定すればk点を貪欲に取れるのでO(n^3logn)で解けるとある。実装するとk=1のときの処理がバグっていてシステスで一回落とす。k=1で4を返すようにしたら通った。
色々難しく考えすぎて方針迷走&&実装バグらせまくりと色々ひどかった。n <= 10^5に慣れすぎてn <= 100が解けない。

学び

オーダーが大きめの解法もちゃんと思考に入れる。誤読しない。変な実装ミスをしない。

// BEGIN CUT HERE
// END CUT HERE
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a <= x && x < b)
#define MP make_pair
#define PB push_back
const int INF = (1LL << 30);
const ll LLINF = (1LL << 60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
// #define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class MinimumSquare {
public:
  long long minArea(vector<int> X, vector<int> Y, int K) {
    int n = X.size();
    if(K == 1) return 4;
    ll ret = LLONG_MAX;
    REP(i, n) FOR(j, i+1, n) {
      ll sx = min(X[i], X[j]), gx = max(X[i], X[j]);
      VL v;
      REP(k, n) if(sx<=X[k] && X[k]<=gx) v.PB(Y[k]);
      if((int)v.size() < K) continue;
      sort(ALL(v));
      ll l = LLONG_MAX;
      FOR(k, K-1, v.size()) {
        chmin(l, v[k]-v[k-K+1]);
      }
      l+=2;
      chmax(l, gx-sx+2);
      chmin(ret, l*l);
    }
    return ret;
  }
};

AOJ0633 ぬいぐるみ

AOJ 競技プログラミング

問題ページ
Plush Toys | Aizu Online Judge

解法

bitDPをする。dp[S] = (集合Sの要素に含まれる種類を左から並べたときの最小の並べ替え回数) とする。dp[S|1<<i] = dp[S] + (並び替えに必要な回数) と遷移できる。並べ替えに必要な回数は並べる区間に含まれていない種類iの個数なので、種類別に累積和を取っておけばO(1)で求めることができる。したがってO(M2^M)で解ける。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[100010], b[25][100010], cnt[25];
PII dp[1LL<<20];
signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, n) {
    cin >> a[i];
    cnt[a[i]-1]++;
    b[a[i]-1][i] = 1;
  }

  REP(i, m) FOR(j, 1, n) b[i][j] += b[i][j-1];

  REP(i, 1LL<<20) dp[i] = {INF, INF};
  dp[0] = {0, 0};

  REP(i, (1LL<<m)-1) REP(j, m) if(!(i>>j&1)) {
    int tmp = dp[i].second == 0 ? 0 : b[j][dp[i].second-1],
        kind = b[j][dp[i].second+cnt[j]-1] - tmp;
    chmin(dp[i|1LL<<j], MP(dp[i].first+cnt[j]-kind, dp[i].second+cnt[j]));
  }

  cout << dp[(1LL<<m)-1].first << endl;

  return 0;
}

JOI2008 春合宿 Cheating

AOJ 競技プログラミング

問題ページ
http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day2_21.pdf

考えたこと

最大の最小化と言われたので二分探索をする。幅Xで実現することができるかの判定について考える。x方向、y方向についてそれぞれ貪欲に決めていくと幅Xで必要なカメラの台数をO(M)で判定できる。したがってO(Mlog(max(X,Y)))で解くことができ間に合う。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int n, m;
VI x, y;

bool check(ll mid) {
  int tmp = 0;
  // x方向
  int i = 0;
  while(i < (int)x.size()) {
    int st = i;
    while(i < (int)x.size() && x[i] - x[st] <= mid) ++i;
    ++tmp;
  }
  // y方向
  i = 0;
  while(i < (int)y.size()) {
    int st = i;
    while(i < (int)y.size() && y[i] - y[st] <= mid) ++i;
    ++tmp;
  }
  if(tmp <= n) return true;
  return false;
}

signed main(void)
{
  cin >> n >> m;
  REP(i, m) {
    int xx, yy;
    cin >> xx >> yy;
    x.PB(xx); y.PB(yy);
  }

  sort(ALL(x));
  x.erase(unique(ALL(x)), x.end());
  sort(ALL(y));
  y.erase(unique(ALL(y)), y.end());

  // (low, high]
  ll low = -1, high = 1000000000;
  while(high-low>1) {
    ll mid = (low+high)/2;
    if(check(mid)) {
      high = mid;
    } else {
      low = mid;
    }
  }

  cout << high << endl;

  return 0;
}

JOI2008 春合宿 sheet

競技プログラミング AOJ

問題ページ
http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf

考えたこと

色iが色jの上に乗っていることをjからiへの有向辺が張られている状態と考えるとトポロジカルソートをすればよい。O(HWN)で辺を張ればよく、トポロジカルソートはO(N^2)でできるので計算量は問題ない。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int c[105][105], sx[1010], sy[1010], gx[1010], gy[1010];
//グラフの隣接リスト
VI g[100010];
//頂点の入次数を管理
int h[100010];
signed main(void)
{
  int hh, w, n;
  cin >> n >> w >> hh;
  REP(i, hh) REP(j, w) cin >> c[i][j];

  memset(sx, 0x3f, sizeof(sx));
  memset(sy, 0x3f, sizeof(sy));
  REP(i, hh) REP(j, w) {
    chmin(sx[c[i][j]], (int)j);
    chmin(sy[c[i][j]], (int)i);
    chmax(gx[c[i][j]], (int)j);
    chmax(gy[c[i][j]], (int)i);
  }

  REP(i, hh) REP(j, w) FOR(k, 1, n+1) {
    int co = c[i][j];
    if(co == 0 || co == k) continue;
    if(IN(sx[k], gx[k]+1, j) && IN(sy[k], gy[k]+1, i)) {
      // coがkの上に乗っている
      g[k].push_back(co);
      h[co]++;
    }
  }

  //入次数が0の頂点の集合
  stack<int> st;

  //入次数が0の頂点であればstに追加
  FOR(i, 1, n+1) if(h[i] == 0) st.push(i);

  //ソートされた後のグラフ
  VI ans;
  //stがなくなるまでループ
  while(st.size()) {
    //stの集合のから一つ取り出す
    int i = st.top(); st.pop();
    ans.push_back(i);
    for(auto& j: g[i]) {
      //隣接する頂点の入次数をマイナス1
      h[j]--;
      //これによって入次数が0になればstに追加
      if(h[j] == 0) st.push(j);
    }
  }

  //ansを順に出力
  REP(i, ans.size()) {
    cout << ans[i];
    if(i != ans.size()-1) cout << " ";
  }
  cout << endl;

  return 0;
}

JOI2008 春合宿 Committee

AOJ 競技プログラミング

問題ページ
http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf

考えたこと

N頂点の木で値の総和が最大になるような連結成分を求めればいい。dp[i] = (頂点iの部分木で最大の値の総和) とするとdp[i] = sum(dp[j], 頂点jが頂点iの子でdp[j]>0) + a[i] とすることで求められる。あとは最大のdp[i]を答えとして出力すればよい。
なぜか頂点1を必ず含むような連結成分のみを答えとして出力するような実装をして3WA出して反省。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[100010], dp[100010];
VI g[100010];
int dfs(int num) {
  if(dp[num] != -1) return dp[num];
  // cout << num << endl;
  int ret = 0;
  for(int i: g[num]) {
    if(dfs(i) > 0) ret += dfs(i);
  }
  return dp[num] = ret + a[num];
}

signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) {
    int x;
    cin >> x >> a[i+1];
    g[x].PB(i+1);
  }
  
  memset(dp, -1, sizeof(dp));
  dfs(0);

  int ret = -INF;
  FOR(i, 1, n+1) chmax(ret, dp[i]);
  cout << ret << endl;

  return 0;
}

AOJ0616 JOI公園

AOJ 競技プログラミング

問題ページ
JOI 公園 | Aizu Online Judge

考えたこと

とりあえず広場1から各広場への最短距離はdijkstraで求まる。Xを決めれば各辺について両端の頂点への最短距離がX以下かどうかでその辺が撤去される辺か判断できるのでO(M)でできる。max(X) = 10^10 でまず間に合わない。Xとして取りうる値は各頂点で最短距離となる値しかありえず、O(N)で抑えられる。しかしこれでもO(NM)で不可能。
各辺について両端の頂点の最短距離の大きい方をXに選択するときその辺を撤去する。したがって各Xの撤去すべき辺の合計をO(M)で前計算しておける。Xの候補のうち小さいものから考えていけば一度撤去した辺が撤去されないことはありえない。したがってO(N+M)で解ける。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

struct edge{ll to, cost;};

int n, d[100010];
vector<edge> g[100010];

void dijkstra(int s) {
  priority_queue<PII, vector<PII>, greater<PII>> que;
  fill(d, d+n, INF);
  d[s] = 0;
  que.push(PII{0, s});

  while(que.size()) {
    PII p = que.top(); que.pop();
    int v = p.second;
    if(d[v] < p.first) continue;
    for(edge e: g[v]) {
      if(d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(PII{d[e.to], e.to});
      }
    }
  }
}

int a[200010], b[200010], cost[200010];
map<ll, ll> mp;
signed main(void)
{
  int m, c;
  cin >> n >> m >> c;
  ll sum = 0;
  REP(i, m) {
    cin >> a[i] >> b[i] >> cost[i];
    a[i]--, b[i]--;
    g[a[i]].PB({b[i], cost[i]});
    g[b[i]].PB({a[i], cost[i]});
    sum += cost[i];
  }

  dijkstra(0);

  VL v;
  REP(i, n) v.PB(d[i]);
  sort(ALL(v));
  v.erase(unique(ALL(v)), v.end());

  //辺について見ていく
  REP(i, m) {
    ll tmp = max(d[a[i]], d[b[i]]);
    if(mp.find(tmp) == mp.end()) mp[tmp] = cost[i];
    else mp[tmp] += cost[i];
  }

  ll ret = LLINF;
  for(int i: v) {
    chmin(ret, c*i+(sum-mp[i]));
    sum -= mp[i];
  }
  cout << ret << endl;

  return 0;
}

AOJ0600 バームクーヘン

AOJ 競技プログラミング

問題ページ
バームクーヘン | Aizu Online Judge

考えたこと

最小値の最大化と言われたので二分探索。判定がO(f(n))であればO(f(n)log(max(A_i)))となる。始点を一箇所固定すればmid以上の最小となるように2箇所切っていくのが最善になる。全パターン確認すれば判定できるのでO(n^2)かけていいなら簡単。判定をO(nlogn)とかO(n)でできれば解けそう。累積和を取っておいて二分探索すれば各始点についてO(logn)で判定できそうなので全体でO(nlognlog(max(A_i)))で解けそう。
累積和が明らかにintに収まる範囲内ではないのでlong longを使う。円環を扱うときは二周分とっておくと実装が楽。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int n;
ll a[200010], b[200010];

bool check(int m) {
  REP(i, n) {
    int tmp = i==0 ? 0 : b[i-1];
    int itr1 = lower_bound(b+i, b+i+n, tmp+m) - b;
    int itr2 = lower_bound(b+i, b+i+n, b[itr1]+m) - b;
    if(b[n+i-1] - b[itr2] >= m) return true;
  }
  return false;
}

signed main(void)
{
  cin >> n;
  REP(i, n) cin >> a[i];
  FOR(i, n, 2*n) a[i] = a[i-n];
  b[0] = a[0];
  FOR(i, 1, 2*n) b[i] = a[i] + b[i-1];

  // [low, high)
  ll low=1, high=b[n-1];
  while(high-low>1) {
    ll mid = (low+high)/2;
    if(check(mid)) {
      low = mid;
    } else {
      high = mid;
    }
  }
  cout << low << endl;

  return 0;
}