JOI2008 春合宿 sheet

問題ページ
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

問題ページ
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公園

問題ページ
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 バームクーヘン

問題ページ
バームクーヘン | 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;
}

AOJ0562 JOI国のお買い物事情

問題ページ
JOI 国の買い物事情 | Aizu Online Judge

解法

最短経路問題で始点が複数あるパターンなので始点をまとめる架空の頂点をつくってやればdijkstra一回で各頂点への最短距離がわかる。各頂点への最短距離がわかっていれば各辺のどの位置が最短距離が最長になる点なのか計算できる。その点の中で最長のものを答えとして出力する。

//#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{int to, cost;};

int n, d[3010], m, k, s[3010];
vector<edge> g[3010];

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

  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[100010], b[100010], c[100010];
signed main(void)
{
  cin >> n >> m >> k;
  REP(i, m) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--, b[i]--;
    g[a[i]].PB({b[i], c[i]});
    g[b[i]].PB({a[i], c[i]});
  }
  REP(i, k) cin >> s[i], s[i]--;

  dijkstra();
  // REP(i, n) cout << d[i] << " "; cout << endl;

  int ret = 0;
  REP(i, m) chmax(ret, (d[a[i]]+d[b[i]]+c[i])/2+!!((d[a[i]]+d[b[i]]+c[i])%2));
  cout << ret << endl;

  return 0;
}

AOJ0550 お菓子の分割

問題ページ
お菓子の分割 | Aizu Online Judge

解法

いかにもDPの雰囲気があるのでDPを考える。AくんとBくんでお菓子を分け合うとして dp[k][i][j] = (k番目まででAくんがi個取って最後に取ったのがAくんならj=0、Bくんならj=1) とおいてDPをする。遷移に必要なのはk-1のときのDPの値だけなので配列は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 t[10010], dp[2][10010][2];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n-1) cin >> t[i];

  memset(dp, 0x3f, sizeof(dp));
  dp[0][1][0] = dp[0][0][1] = t[0];
  // k=0ならA、k=1ならB
  int cur = 0, nxt = 1;
  FOR(i, 1, n) {
    REP(j, n) REP(k, 2) dp[nxt][j][k] = 0x3f3f3f3f;
    REP(j, n+1) {
      REP(k, 2) {
        if(dp[cur][j][k] == 0x3f3f3f3f) continue;
        if(k == 0) {
          // Aに選ぶ
          chmin(dp[nxt][j+1][0], dp[cur][j][k] - t[i-1] + t[i]);
          // Bに選ぶ
          chmin(dp[nxt][j][1], dp[cur][j][k] + t[i]);
        } else {
          chmin(dp[nxt][j+1][0], dp[cur][j][k] + t[i]);
          chmin(dp[nxt][j][1], dp[cur][j][k] - t[i-1] + t[i]);
        }
      }
    }
    cur = !cur, nxt = !nxt;
  }

  cout << min(dp[cur][n/2][0], dp[cur][n/2][1]) << endl;

  return 0;
}

tco2017 Pittsburgh Regional round med

概要

数列のどの要素の3つ組を取っても和が9の倍数とならないような最大の部分集合の大きさを求める。

考えたこと

コンテスト中の誤った思考を書いてるだけ。
与えられる数列の要素は200以下なので3乗くらいまでできそう。試しに9の倍数になる3つ組を全列挙してみる。3つ組のいずれかの要素を部分集合に含まなければその3つ組によって条件を満たさなくなることはない。したがって全ての3つ組でいづれかの要素を答えとなる部分集合の候補から消していくと考えると集合の全ての要素を覆うような集合を選べばよさそうとなりこれを解く方法を永遠と考える。
愚直にやるとO(3ⁿ³)で明らかに不可能。フローやDPなど色々考えるが思い浮かばない。典型問題でありそうと思いググっていると集合被覆問題でこれはNP問題であることをコンテスト終了5分前に知り絶望する。
challenge中にコードを読むとmod 9を取って探索しているコードを見つける。
コンテスト終了後に解説tweetを読むとmod9が0~8の要素がそれぞれ0個、1個、2個、3個以上の4パターンに分類し4⁹の全探索をするとあるので強い人のコードを見つつ実装したら通った。

学び

典型そうな問題に帰着できたらとりあえずググる。
倍数について考えるときはmodを取る。

// 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};

int cnt[100], take[100];

bool check(int a, int b, int c) {
  int tot_a = 1+(b==a)+(c==a),
      tot_b = 1+(a==b)+(c==b),
      tot_c = 1+(a==c)+(b==c);
  return (take[a] >= tot_a && take[b] >= tot_b && take[c] >= tot_c);
}

class Avoid9 {
  public:
  int maxSizeOf9Free(vector<int> A)
  {
    memset(cnt, 0, sizeof(cnt));
    REP(i, A.size()) cnt[A[i]%9]++;

    // mod9の値の0~8が0個、1個、2個、3個以上の4パターンを全探索4^9
    int ans = -1;
    REP(i, 1LL<<18) {
      // iを4進数みたいに見る
      int tmp = i;
      REP(j, 9) {take[j] = tmp%4; tmp/=4;}
      // 4進数のそれぞれの桁の値からjの個数を決める
      int ret = 0;
      REP(j, 9) {
        if(take[j] == 3) ret += cnt[j];
        else ret += take[j];
        if(take[j] > cnt[j]) ret = -INF;
      }
      if(ret<=ans) continue;

      REP(j, 9) FOR(k, j, 9) {
        // (j, k, q) の組を選ぶと9の倍数になる
        int q = (9-(j+k)%9)%9;
        // 9の倍数となるような3つ組が部分集合に存在するような選び方
        if(check(j, k, q)) {ret = -INF; break;}
      }
      chmax(ans, ret);
    }

    // 答えが存在しない
    if(ans < 3) ans = -1;
    return ans;
  }
};