解いた問題のソースコードと解説など。


POJ 3494 Largest Submatrix of All 1’s

問題

0と1からなるnxmのマスが与えられる。この中に含まれる1のみからなるx軸とy軸に平行な長方形で最大の長方形の面積を求めよ。

やりかた

ヒストグラム内の最大長方形の面積を求めるアルゴリズムを応用する。マスから一行読むごとにこのアルゴリズムを実施する。そのときにどれだけy軸方向に1が連続しているかを列ごとに蓄積しておくことで、その値をその行を読んだときのヒストグラムの高さとして考える事ができる。計算量O(nm)

以下ソース。

int m, n;
int h[2010];
int R[2010], L[2010];

int largest_hist(){
  stack<int> S;
  for(ll i = 0; i < n; i++){
    while(S.size() && h[S.top()] >= h[i]) S.pop();
    L[i] = S.size() ? S.top() + 1 : 0;
    S.push(i);
  }
  S = stack<int>();
  for(ll i = n - 1; i >= 0; i--){
    while(S.size() && h[S.top()] >= h[i]) S.pop();
    R[i] = S.size() ? S.top() : n;
    S.push(i);
  }

  int ans = 0;
  for(int i = 0; i < n; i++)
    ans = max(ans, h[i] * (R[i] - L[i]));
  return ans;
}

int main(int argc, char **argv){
  while(cin >> m >> n){
    FILL(h, 0);
    int ans = 0;
    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
	int d; scanf("%d", &d);
	h[j] = d ? h[j] + 1 : 0;
      }
      ans = max(ans, largest_hist());
    }
    cout << ans << endl;
  }
  return 0;
}

POJ 3390 Print Words in Lines

問題

N個の文字があり、各文字の文字数が数値として与えられる。文字は与えられた順に(間にスペースを一つ入れて)連結して出力することができ、一行あたり最大でM文字出力する事ができる。ただし文字の途中で改行してはいけない。
出力する各行には(M-行の文字数)の二乗のペナルティが加算され、これらの総和を全体のペナルティとして計算する。
全体のペナルティを最小化せよ。

やりかた

dp[i]:=(i番目の文字までを使ったときのペナルティの最小値)でDP。

更新式は
L = \sum_{j}^i len[j]としてdp[i] = \min_j(dp[j-1] + (M - L)^2)
で、プログラム上はO(MN)で計算できる。

以下ソース。

int len[10001];
int dp[10001];

int main(int argc, char **argv){
  int T, M, N;
  scanf("%d", &T);
  while(T--){
    scanf("%d %d", &M, &N);
    for(int i = 0; i < N; i++)
      scanf("%d", len + i);

    FILL(dp, INF);
    for(int i = 0; i < N; i++){
      int L = 0;
      for(int j = i; j >= 0; j--){
	L += len[j];
	if(L > M) break;
	int v = j == 0 ? 0 : dp[j - 1];
	dp[i] = min(dp[i], v + (M - L) * (M - L));
	L++; //a space between two words
      }
    }
    printf("%d\n", dp[N - 1]);
  }
  return 0;
}

POJ 3275 Ranking the Cows

問題

牛がN匹いて、それぞれの牛の牛乳の生産量は異なっている。2匹の牛の牛乳の生産量の大小を表すクエリがM個与えられる。生産量の順番を確定するために必要になる追加のクエリ数を求めよ。

やりかた

牛がN匹いるとすると順番を確定するための関係は {}_NC_2 = \frac{N(N - 1)}{2}になる。あたえられたM個のクエリのうち確定している関係の個数からこれを引いたものが答えになる。M個のクエリをグラフの構造にすると、あるノード(牛)に着目したときにそのノードより小さいノードの個数というのが、その牛より少ない生産量の牛との関係の個数を表す。これをすべてのノードについて計算すれば確定している関係性の個数が判定できる。小さいノードを調べるのは普通に深さ優先でいい。

以下ソース。

vector<int> g[1001];
bool vis[1001];

int dfs(int idx){
  int s = 0;
  vis[idx] = true;
  for(int i = 0; i < g[idx].size(); i++){
    int to = g[idx][i];
    if(!vis[to]) s += dfs(to) + 1;
  }
  return s;
}

int main(int argc, char **argv){
  FILL(header, -1);
  
  int N, M;
  scanf("%d %d", &N, &M);
  for(int i = 0; i < M; i++){
    int a, b;
    scanf("%d %d", &a, &b);
    a--, b--;
    g[a].push_back(b);
  }

  int s = 0;
  for(int i = 0; i < N; i++){
    FILL(vis, false);
    s += dfs(i);
  }

  printf("%d\n", N * (N - 1) / 2 - s);
  return 0;
}

POJ 2773 Happy 2006

問題

自然数m, Kが与えられる。mと互いに素なK番目の自然数を返せ。

やりかた

逐一調べると当然間に合わない。ここは二分探索+包除原理。まず二分探索で解の候補を上げ、その解の候補に対して、それ以下の自然数でかつmと互いに素なものの個数を計算し、その大小で探索範囲をせばめる。
ある自然数x以下の自然数でmと互いに素な自然数の数を調べるには、まずmを素因数分解し、mの素因数を列挙する。ここから包除原理によってx以下の自然数のうちmの素因数を少なくとも1つ持つ自然数の数を求めることができる。互いに素な数はこの余事象になる。

以下ソース。

vector<int> fa(int n){
  set<int> r;
  for(int i = 2; i * i <= n; i++){
    while(n % i == 0){
      r.insert(i);
      n /= i;
    }
  }
  if(n != 1) r.insert(n);
  return vector<int>(ALL(r));
}

ll relative_prime(ll x, const vector<int> &pr){
  int N = pr.size();
  ll ret = 0; //x以下の自然数でmの素因数を少なくとも一つ持つ自然数の数
  for(int S = 1; S < 1 << N; S++){
    ll a = 1;
    for(int i = 0; i < N; i++)
      if(S >> i & 1) a *= pr[i];
    int bit = __builtin_popcount(S);
    if(bit & 1) ret += (x / a);
    else ret -= (x / a);
  }
  return x - ret; //互いに素な個数
}

int main(){
  ll m, K;
  while(cin >> m >> K){
    vector<int> pf = fa(m);
    
    ll ub = LLINF, lb = 0LL;
    while(lb < ub - 1){
      ll mid = (ub + lb) / 2;
      ll rp = relative_prime(mid, pf);
      if(rp >= K) ub = mid;
      else lb = mid;
    }
    cout << ub << endl;
  }
  return 0;
}

POJ 2420 A Star not a Tree?

問題

二次元座標上に点がN個与えられる。この座標上から一点を指定し、N個の点との距離の総和を最小化せよ。

やりかた

解析的に答えが求まりそうにないので、数理最適化。自分は最急降下法でやった。
選んだ座標を(X, Y)とし、与えられたN個の点の座標を(a_i, b_i)すると距離の総和はL = \sum \sqrt{(X - a_i)^2 + (Y - b_i)^2}となる。

なのでこの関数の勾配方向は
\left( \frac{\partial L}{\partial X}, \frac{\partial L}{\partial Y} \right) = \left( \sum \frac{X-a_i}{\sqrt{(X - a_i)^2 + (Y - b_i)^2}}, \sum \frac{Y-b_i}{\sqrt{(X - a_i)^2 + (Y - b_i)^2}} \right)となるので、ここから更新式X \leftarrow X - \alpha * {\partial L}/{\partial X}, \quad Y \leftarrow Y - \alpha * {\partial L}/{\partial Y}に従って予め決めた回数だけX, Yを更新する。

関数が凸関数でないような気がしたため、局所最小値に入ってしまうかもしれないと思ったが、初期値を重心にすれば大丈夫だろとたかをくくって出した。

以下ソース。

int x[100], y[100];

int main(){
  int N; cin >> N;

  double sumX = 0, sumY = 0;
  for(int i = 0; i < N; i++){
    cin >> x[i] >> y[i];
    sumX += x[i], sumY += y[i];
  }
  
  double X = sumX / N;
  double Y = sumY / N;

  for(int i = 0; i < 100000; i++){
    double alpha = 1e-2;

    double dx = 0, dy = 0;
    for(int j = 0; j < N; j++){
      dx += (X - x[j]) / sqrt(pow(X - x[j], 2.0) + pow(Y - y[j], 2.0));
      dy += (Y - y[j]) / sqrt(pow(X - x[j], 2.0) + pow(Y - y[j], 2.0));
    }
    
    X = X - alpha * dx;
    Y = Y - alpha * dy;
  }

  double L = 0;
  for(int j = 0; j < N; j++)
    L += sqrt(pow(X - x[j], 2.0) + pow(Y - y[j], 2.0));
  printf("%d\n", (int)(L + 0.5));
  return 0;
}

最初、学習率が小さすぎて最小値までたどりつかずWA。提出する前は収束するかきちんと確かめた上で、制限時間内で収束するような学習率にするべきだとわかった。(あたりまえだが)

POJ 3422 Kaka's Matrix Travels

問題

NxNのグリッドがあり、各マスに0以上の整数が書かれている。グリッドの左上のマスからスタートして右か下に一つずつ移動して右下のマスまでたどり着きたい。通ったマスの数字は得点となり、一度通ったらそのマスの数字は0になる。K回スタートからゴールに移動したときに得られる総得点を最大化せよ。

やりかた

最小(最大)費用流。単純に最大経路をK回調べるのでは駄目。
費用流の問題として考えるとソースから左上のマスにつながり、右下のマスからシンクにつながるネットワークにKだけ流すときの最大費用流として考えることができる。ここで問題になるのは各マスが一回通ったあとは得点が0になることであり、ネットワークフローで考えればこれは(得点があるときの)そのセルに流量1の制限があることと同じになる。そこで下の図のように各マスのコピーを作り、コピーに対して1の流量のある得点がつく辺と、流量無限大のコスト0の辺を加えてやることで、得点のある辺は一回しか使われないようにすることができる。
f:id:Area1:20171218005854p:plain

以下ソース。

int N, K;
struct min_cost_flow{
  struct edge{
    int to, cap, cost, rev;
    edge(int to, int cap, int cost, int rev) : 
      to(to), cap(cap), cost(cost), rev(rev) {};
  };
  vector<vector<edge> > G;

  min_cost_flow(int V) : G(V) {}

  void add_edge(int from, int to, int cap, int cost){
    G[from].push_back(edge(to, cap, cost, G[to].size()));
    G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));
  }

  int flow(int s, int t, int f){
    typedef pair<int, int> P;
    int V = G.size();
    vector<int> po(V);
    int res = 0;
    while(f > 0){
      vector<int> dist(V, INF), prevv(V, -1), preve(V, -1);
      priority_queue<P, vector<P>, greater<P> > Q;
      Q.push(make_pair(0, s));
      dist[s] = 0;
      while(!Q.empty()){
	P q = Q.top(); Q.pop();
	int u = q.second;
	if(dist[u] < q.first) continue;
	for(int i = 0; i < G[u].size(); i++){
	  edge &e = G[u][i];
	  if(e.cap > 0 && dist[e.to] > dist[u] + e.cost + po[u] - po[e.to]){
	    dist[e.to] = dist[u] + e.cost + po[u] - po[e.to];
	    prevv[e.to] = u;   preve[e.to] = i;
	    Q.push(P(dist[e.to], e.to));
	  }
	}
      }
      if(dist[t] == INF) return -1;
      for(int v = 0; v < V; v++) po[v] += dist[v];
      
      int scap = f;
      for(int v = t; v != s; v = prevv[v])
	scap = min(scap, G[prevv[v]][preve[v]].cap);
      
      f -= scap;
      res += scap * po[t];
      for(int v = t; v != s; v = prevv[v]){
	edge &e = G[prevv[v]][preve[v]];
	e.cap -= scap;
	G[v][e.rev].cap += scap;
      }
    }
    return res;
  }
};

int main(){
  scanf("%d %d", &N, &K);

  int V = N * N;
  int s = 2 * V, t = s + 1;
  
  min_cost_flow mcf(2 * V + 2);
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      int x;
      scanf("%d", &x);

      mcf.add_edge(i * N + j, i * N + j + V, 1, -x);//最小費用流でとくため符号を反転
      mcf.add_edge(i * N + j, i * N + j + V, INF, 0);
      
      if(j != N - 1)
	mcf.add_edge(i * N + j + V, i * N + j + 1, INF, 0);
      if(i != N - 1)
      	mcf.add_edge(i * N + j + V, (i + 1) * N + j, INF, 0);
    }
  }
  mcf.add_edge(s, 0, INF, 0);
  mcf.add_edge(2 * V - 1, t, INF, 0);
  
  printf("%d\n", -mcf.flow(s, t, K));////最小費用流でとくため符号を反転
  return 0;
}

図が薄くてすみません。

POJ 3790 Recursively Palindromic Partitions

問題

与えられた自然数を、それ以下の自然数の数列の和で表現する。これを自然数の分割と呼ぶ。回文となるような分割をPalindromic Partitionという。そのうち以下の条件を満たす分割をRecursively Palindromic Partitionsという。
条件:分割の左右それぞれがRecursively Palindromic Partitionsである。ただし分割数1の分割は常にRecursively Palindromic Partitionである。

与えられる自然数のRecursively Palindromic Partitionsの数をもとめよ。

やりかた

分割統治で真ん中から左右に分けていき、分けきれなくなるまでわけられたらひとつと数える。メモ化して計算量を落とす。

以下ソース。

int N;
ll dp[1001][1001];

ll rec(int idx, int rem){
  if(rem == 0) return 1;
  if(dp[idx][rem] != -1) return dp[idx][rem];
  
  ll ret = 0;
  for(int i = 0; i <= rem; i++){
    if((rem - i) % 2) continue;
    ret += rec(idx + 1, (rem - i) / 2);
  }
  return dp[idx][rem] = ret;
}

int main(){
  int T;
  cin >> T;
  for(int i = 1; i <= T; i++){
    cin >> N;
    FILL(dp, -1);
    cout << i << " " << rec(0, N) << endl;
  }
  return 0;
}
罪を憎んで人は憎まずにセクシー