SRM412: StringsAndTabs

(問題概要)
２つのTAB譜の変換

(解法)
やるだけ。制限が色々めんどい。
最近なら250〜300で出ても驚かないレベルの内容。

#include <algorithm>
#include <cstdio>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class StringsAndTabs {
public:
  vector <string> transformTab(vector <string> tab, vector <int> stringsA, vector <int> stringsB, int d);
};

int num(char c){
  if(isdigit(c)) return c - '0';
  return c - 'A' + 10;
}

char toNum(int n){
  if(n < 10) return '0' + n;
  return 'A' + n - 10;
}

vector <string> StringsAndTabs::transformTab(vector <string> tab, vector <int> stringsA, vector <int> stringsB, int d){
  const int w = tab[0].size();
  const int h = tab.size();
  const int hh = stringsB.size();
  vector<vector<int> > val(w);
  vector<string> ans(hh, string(w, '-'));
  vector<pair<int, int> > idx(hh);
  REP(i,hh) idx[i] = make_pair(stringsB[i], i);
  sort(idx.rbegin(), idx.rend());

  REP(i,h) REP(j,w){
    if(tab[i][j] != '-'){
      val[j].push_back(stringsA[i] + num(tab[i][j]) + d);
    }
  }


  REP(j,w) sort(val[j].rbegin(), val[j].rend());

  REP(i,w) REP(j,val[i].size()){
    const int v = val[i][j];
    bool assign = false;
    REP(kk,hh){
      const int k = idx[kk].second;
      if(stringsB[k] <= v && v <= stringsB[k] + 35){
	if(ans[k][i] == '-'){
	  ans[k][i] = toNum(v - stringsB[k]);
	  assign = true;
	  break;
	}else{

	}
      }
    }
    if(!assign){
      REP(k,hh){
	ans[k][i] = 'x';
      }
    }
  }

  return ans;
}

SRM411: HoleCakeCuts

(問題概要)
回 ← みたいなケーキがある(真ん中に穴が空いてる)
縦と横にそれぞれ何回か包丁を入れた時に、最終的に何ピースのケーキが出来るか。

(解法)
縦横で近いカットを２つづつ選ぶとそれに囲まれた四角形ができる。
後はその頂点を見て場合分け。
関数名がクソ命名。

#include <cstdio>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <algorithm>
#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class HoleCakeCuts {
public:
  int cutTheCake(int cakeLength, int holeLength, vector <int> horizontalCuts, vector <int> verticalCuts);
};

inline bool isHole(int h, int w, int hl){
  return std::abs(w) <= hl && std::abs(h) <= hl;
}

inline bool overHole(int h1, int h2, int hl){
  return h1 < -hl && hl < h2;
}

inline bool onHole(int h1, int h2, int hl){
  return isHole(h1, 0, hl) && isHole(h2, 0, hl);
}

int HoleCakeCuts::cutTheCake(int cl, int hl, vector <int> h, vector <int> v){
  int cnt = 0;

  h.push_back(cl);
  h.push_back(-cl);
  v.push_back(cl);
  v.push_back(-cl);

  sort(h.begin(), h.end());
  sort(v.begin(), v.end());

  REP(i,h.size() - 1) REP(j,v.size() - 1){
    const int h1 = h[i];
    const int h2 = h[i + 1];
    const int v1 = v[j];
    const int v2 = v[j + 1];

    const bool hole1 = isHole(h1, v1, hl);
    const bool hole2 = isHole(h2, v2, hl);

    if(!hole1 && !hole2){
      const bool over1 = overHole(h1, h2, hl);
      const bool over2 = overHole(v1, v2, hl);

      const bool on1 = onHole(h1, h2, hl);
      const bool on2 = onHole(v1, v2, hl);

      if((over1 && on2) || (over2 && on1)) cnt++;
      cnt++;
    }else if(!hole1 || !hole2){
      cnt++;
    }
  }

  return cnt;
}

SRM410: ContiguousCache

(問題概要)
nバイトのメモリ、kバイトのキャッシュを持ったマシンを考える。
キャッシュにはメモリ上の連続したkバイトを載せることが出来る。
キャッシュを更新するには、更新前に載っていなかったバイト数だけコストがかかる。
アクセスするアドレス(a[0], a[1], ...)が前もってわかっていている場合に、最適にキャッシュにデータを乗せるとどれだけコストがかかるか。

(解法)
少し考察するとキャッシュに載せるメモリの先頭アドレスは下記のみを考えればよいような気がする。
(証明はしてないけど、任意の他のアドレスに載せた場合は以下に載せた場合のコスト以上になる)
0, n - k, a[0], a[1], ..., a[0] - k + 1, a[1] - k + 1, ...
ここまでわかれば、あとはよくあるDPなりメモ化再帰で終了。

なんか直感的にはグリーディー的にやればもうひとつオーダー下がる気がするけど、問題のサイズから不要。

typedef long long ll;

#include <map>
#include <algorithm>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class ContiguousCache {
public:
  long long minimumReads(int n, int k, vector <int> addresses);
};

long long ContiguousCache::minimumReads(int n, int k, vector <int> addresses){
  vector<int> a;
  REP(i,addresses.size()){
    if(addresses[i] + k <= n)
      a.push_back(addresses[i]);
    if(addresses[i] - k >= 0)
      a.push_back(addresses[i] - k + 1);
  }
  a.push_back(0);
  a.push_back(n - k);
  sort(a.begin(), a.end());
  a.erase(unique(a.begin(), a.end()), a.end());

  map<int, int> memo;
  REP(i,a.size()) memo[a[i]] = i;

  const ll inf = 1ll << 60;
  vector<ll> dp(a.size(), k);

  REP(i,addresses.size()){
    const int address = addresses[i];
    vector<ll> next(a.size(), inf);

    REP(j,a.size()) if(dp[j] != inf){
      REP(p,a.size()){
	if(a[p] <= address && address < a[p] + k){
	  const ll cost = min(k, std::abs(a[j] - a[p]));
	  next[p] = min(next[p], dp[j] + cost);
	}
      }
    }

    dp.swap(next);
  }

  return *min_element(dp.begin(), dp.end());
}

SRM 409: MagicalSpheres

(問題概要)
本物がspheresCount個、偽物がfakeSpheresCount個、全体からspheresCount個選んで全部正しいかを試す。
全通りを何グループかで試すとき、各グループが同じ通り数を試すには、gnomesAvailable以下で最大何グループ選べるか。
(nCk % m == 0 となる gnomeAvailable以下の最大のmを計算)

(解法)
gnomeAvailable以下の数を全部試す。
素因数分解してチェック。素因数分解は頑張らなくても計算量的に余裕。

#include <cstdio>
typedef long long ll;

#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class MagicalSpheres {
public:
  int divideWork(int spheresCount, int fakeSpheresCount, int gnomesAvailable);
};

vector<pair<int, int> > factorize(int n){
  vector<pair<int, int> > ret;

  for(int i = 2; i * i <= n; i++){
    if(n % i == 0){
      int cnt = 0;
      while(n % i == 0){
	n /= i;
	cnt++;
      }
      ret.push_back(make_pair(i, cnt));
    }
  }
  if(n > 1) ret.push_back(make_pair(n, 1));

  return ret;
}

bool check(int n, int k, const vector<pair<int, int> > &fact){
  REP(i, fact.size()){
    const int fct = fact[i].first;
    const int cnt = fact[i].second;

    int c = 0;
    ll f = fct;

    while(f <= n){
      c += n / f;
      c -= (n - k) / f;
      c -= k / f;

      f *= fct;
    }

    // printf("%d : %d\n", fct, c);

    if(c < cnt) return false;
  }

  return true;
}

int MagicalSpheres::divideWork(int spheresCount, int fakeSpheresCount, int gnomesAvailable){
  for(int i = gnomesAvailable; i > 0; i--){
    if(check(spheresCount + fakeSpheresCount, spheresCount, factorize(i)))
      return i;
  }
  return 0;
}

SRM408: CandyGame

(問題概要)
acyclicなグラフ(|G| <= 50)に対して
操作： ノードに2つの飴があるとき、ひとつ食べて、ひとつを隣接ノードに移動
という操作が可能。
操作を繰り返して、目的のノードに飴を置くことが"できない"ようにする時に、最大何個飴を置けるか。

(解法)
少し考えると、目的のノードから遠いところに飴をおいたほうが良いことが分かる。
あとは分岐に対して全探索しつつ、メモ化再帰で適当に。

#include <numeric>
#include <map>
#include <cstdio>
typedef long long ll;

#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class CandyGame {
public:
  int maximumCandy(vector <string> graph, int target);
};

const int MAX = 1000;
int dist[50][50];
int n;
int t;
map<ll, ll> dp[50];

int solve(int pos, ll num){
  if(dp[pos].count(num)) return dp[pos][num];

  vector<int> v;

  REP(i,n) if(dist[pos][i] == 1 && dist[t][pos] + 1 == dist[t][i])
    v.push_back(i);

  const int cnt = v.size();

  if(cnt == 0) return dp[pos][num] = num;
  if(cnt == 1) return dp[pos][num] = solve(v[0], num * 2 + 1);

  ll ret = 0;

  vector<ll> memo(cnt);
  REP(i,cnt)
    memo[i] = solve(v[i], 1);

  const ll all = accumulate(memo.begin(), memo.end(), 0ll);
  REP(i,cnt){
    ll tmp = all - memo[i] + solve(v[i], num * 2 + 1);
    // cout << pos << " " << num << " " << v[i] << ": " << tmp << endl;
    ret = max(ret, tmp);
  }
  return dp[pos][num] = ret;
}

int CandyGame::maximumCandy(vector <string> graph, int target){
  n = graph.size();
  t = target;
  REP(i,n) dp[i].clear();
  REP(i,n) REP(j,n) dist[i][j] = graph[i][j] == 'Y' ? 1 : MAX;
  REP(i,n) dist[i][i] = 0;
  REP(k,n) REP(i,n) REP(j,n)
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  REP(i,n) if(dist[target][i] == MAX)
    return -1;
  ll ans = solve(target, 0);
  return ans < 2000000000 ? ans : -1;
}

SRM407: PointsGame

(問題概要)
平面上の点(12個以下)を自分が赤、相手が青で自分から交互に塗っていく。
最後に色の違う点の全対に対して、距離の和が得点になる。
相手は得点を最小にするように最適に動く。
最大何点得られるか。

(解法)
点の数が少ないので、bitDPすれば良い。
ただし愚直にやるとMLE食らったので、mapを使った。

#include <map>
#include <cstdio>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>
#include <cmath>

using namespace std;

class PointsGame {
public:
  double gameValue(vector <int> pointsX, vector <int> pointsY);
};

map<int, double> memo[1 << 12];
vector<int> x;
vector<int> y;
int n;

double dist(int i, int j){
  const double d1 = x[i] - x[j];
  const double d2 = y[i] - y[j];
  return sqrt(d1 * d1 + d2 * d2);
}

double solve(int f1, int f2){
  if(memo[f1].count(f2)) return memo[f1][f2];
  if((f1 | f2) == (1 << n) - 1){
    double p = 0;
    REP(i,n) if(f1 & (1 << i))
      REP(j,n) if(f2 & (1 << j))
	p += dist(i, j);
    return memo[f1][f2] = p;
  }

  const int k1 = __builtin_popcount(f1);
  const int k2 = __builtin_popcount(f2);

  if(k1 == k2){
    double mx = 0.0;
    REP(i,n) if( ((f1 | f2) & (1 << i)) == 0 ){
      mx = max(mx, solve(f1 | (1 << i), f2));
    }
    return memo[f1][f2] = mx;
  }else{
    double mn = 1e10;
    REP(i,n) if( ((f1 | f2) & (1 << i)) == 0 ){
      mn = min(mn, solve(f1, f2 | (1 << i)));
    }
    return memo[f1][f2] = mn;
  }
}

double PointsGame::gameValue(vector <int> pointsX, vector <int> pointsY){
  REP(i,1<<12) memo[i].clear();
  x = pointsX; y = pointsY;
  n = pointsX.size();
  return solve(0, 0);
}

SRM 406: FoldThePaper

(問題概要)
数値がグリッド上に書かれた紙を折りたたんで行って重なった数値の合計を最大化する。

(解法)
縦と横を独立に考えることができる。
縦横は各全探索

#include <algorithm>
#include <cstdio>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class FoldThePaper {
public:
  int getValue(vector <string> paper);
};

void dfs(vector<int> v, set<int> &s){
  REP(i,v.size()) s.insert(v[i]);

  REP(i,v.size() - 1){
    vector<int> next;

    int idx1 = i;
    int idx2 = i + 1;
    while(idx1 >= 0 || idx2 < (int)v.size()){
      const int aa = idx1 >= 0 ? v[idx1] : 0;
      const int bb = idx2 < (int)v.size() ? v[idx2] : 0;
      next.push_back(aa + bb);
      idx1--; idx2++;
    }

    reverse(next.begin(), next.end());
    dfs(next, s);
  }
}

vector<int> cand(const int n){
  vector<int> tmp;
  set<int> s;
  REP(i,n) tmp.push_back(1 << i);
  dfs(tmp, s);
  return vector<int>(s.begin(), s.end());
}

vector<vector<int> > parse(const vector<string> &s){
  const int h = s.size();
  vector<vector<int> > ret(h);

  REP(i,h){
    stringstream ss(s[i]);
    int p;
    while(ss >> p) ret[i].push_back(p);
  }

  return ret;
}

int FoldThePaper::getValue(vector <string> paper){
  const vector<vector<int> > p = parse(paper);
  const int h = p.size();
  const int w = p[0].size();

  const vector<int> ch = cand(h);
  const vector<int> cw = cand(w);

  int ans = -100000000;
  REP(i,ch.size()){
    const int mask = ch[i];
    vector<int> sum(w);
    REP(j,h) if(mask & (1 << j))
      REP(k,w) sum[k] += p[j][k];

    REP(j,cw.size()){
      int s = 0;
      const int mask2 = cw[j];
      REP(k,w) if(mask2 & (1 << k))
	s += sum[k];
      ans = max(ans, s);
    }
  }

  return ans;
}