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


POJ 1971 Parallelogram Counting

問題

2次元平面上の整数座標がn点(n<=1000)与えられる。4点を選んでできる平行四辺形の個数を求めよ。ただしどの4点も一直線上に並ばないものとする。

やりかた

3点を指定すると残り1点が定まり、その残りの点が与えられた中にあるかを調べる、というやりかただとTLEしてしまう。
2点を指定するとその2点の中点が定まる。このとき別の2点の中点がこの中点と同じだとすると、そこで一つの平行四辺形ができる。こう考えると、2点の中点をすべて列挙し、とある中点がkペアの2点の中点となっていたら、その中点を中心に _kC_2個の平行四辺形ができるわけだから、これを足し上げていけばいい。計算量O(N^2\log N)
ただ、G++で中点の頻度を

map<pair<long long, long long>, int> 

で管理したらTLEしたのですこし工夫した。あと、中点は整数になっていてほしいので得られた座標を原点基準で2倍することで必ず中点が整数になるようにしている。

以下ソース。

ll x[1000], y[1000];

ll base = 5000000000;

int main(){
  int t;
  scanf("%d", &t);
  while(t--){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
      scanf("%lld %lld", x + i, y + i);
      x[i] *= 2LL;
      y[i] *= 2LL;
    }

    int idx = 0;
    vector<ll> p(n * (n - 1) / 2);
    for(int i = 0; i < n; i++){
      for(int j = i + 1; j < n; j++){
	ll cx = (x[i] + x[j]) / 2;
	ll cy = (y[i] + y[j]) / 2;

	p[idx++] = cy * base + cx;
      }
    }
    sort(ALL(p));

    int c = 1;
    int ans = 0;
    for(int i = 1; i < p.size(); i++){
      if(p[i] == p[i - 1]) c++;
      else{
	ans += (c * (c - 1) / 2);
	c = 1;
      }
    }
    ans += (c * (c - 1) / 2);

    cout << ans << endl;
  }
  return 0;
}

1000msくらいだった

AtCoder ABC 125 D - Flipping Signs

問題

長さN(<=1e5)の整数列が与えられる。0-N-1までの添字iを選んでi, i+1の要素の符号を反転できる。この操作を任意の回数を行い、操作後の数列の総和を最大化せよ。

やりかた

まず、もともとの数列にある負の数の個数が偶数個の場合は操作によってすべて正(もしくは0)にできる。奇数個だとどうしても一つ残ってしまうが、操作をうまく行うと、符号がマイナスになる位置を好きに選ぶことができる。なので、数列中で絶対値の最小の要素をマイナスにしてあとはプラスにすればいい。

以下ソース。

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

  ll sum = 0;
  ll mv = LLINF;
  int minus = 0;
  for (int i = 0; i < N; i++){
    ll x;
    cin >> x;
    sum += abs(x);
    if (x < 0LL) minus++;
    mv = min(mv, abs(x));
  }
  if(minus % 2) sum -= (mv * 2LL); //絶対値最小のものを(すでに足している分もいれて)ひく
  cout << sum << endl;
  return 0;
}

はじめてのABC

POJ 2923 Realocation

問題

n個の荷物とその荷物を目的に運ぶための車が2台ある。荷物の重量はそれぞれw[i]であり、車が一回で運ぶことのできる重量はそれぞれc1,c2までである。2台の車は常に同時に動かすとする。荷物をすべて動かすのに2台の車を最低何回動かせばよいか答えよ。

やりかた

nが10以下とちいさいのでbitdpでいける。dp[S]を荷物のうち集合Sを運ぶための最小回数とする。Sの状態から次の移動で車1に残りの荷物のうちTを運ばせ、車2にUを運ばせるとしたときdp[S|T|U] = min(dp[S] + 1, dp[S|T|U])という漸化式を解いていく。

制限時間が厳しいので、車1と2が運ぶ候補をSとは無関係に全列挙すると間に合わない。すでに運んだ荷物の状態Sの補集合に対する部分集合を列挙して車1が運ぶ候補Tとし、SとTの和集合(すでに運んだ荷物と車1が今回運ぶ荷物)の補集合に対する部分集合を列挙して車2は運ぶ候補Uとした。

以下ソース。

int n, c1, c2;
int sum[1 << 10];
int dp[1 << 10];

int rec(int S){
    if(__builtin_popcount(S) == n) return 0;
    if(dp[S] != -1) return dp[S];

    int IS = ~S & ((1 << n) - 1);

    int ans = INF;
    for(int T = IS; ; T = (T - 1) & IS){
        if(sum[T] > c1) continue;

        int H = S | T;
        int IH = ~H & ((1 << n) - 1);
        for(int U = IH; ; U = (U - 1) & IH){
            if((T + U) != 0 && (sum[U] <= c2)){
                ans = min(ans, rec(S | T | U) + 1);
            }
            if(U == 0) break;
        }
        if(T == 0) break;
    } 
    return dp[S] = ans;
}

int main(){
  int T;
  int w[10];
  scanf("%d", &T);
  for(int j = 0; j < T; j++){
    scanf("%d %d %d", &n, &c1, &c2);
    for(int i = 0; i < n; i++) scanf("%d", &w[i]);

    for(int S = 0; S < 1 << n; S++){
      int s = 0;
      for(int i = 0; i < n; i++) if(S >> i & 1) s += w[i];
      sum[S] = s;
    }
    FILL(dp, -1);
    printf("Scenario #%d:\n%d\n\n", j + 1, rec(0));
  }
  return 0;
}

数日来、気落ちすることが多いので競技プログラミングをして心を落ち着けています。

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;
}
Get up! 明日のSUPER ST@R!