ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

TopCoder SRM 648 Div1 Easy : AB

概要

以下の条件を満たす文字列が存在するか求めよ。

・N文字
・文字列sは'A'と'B'の2種類からなる
・s[i]=='A'かつs[j]=='B'となるペア(i,j)がK組ある (0 <= i < j < N)

解法

[2015/2/3:別解(動的計画法)を追加]

== 貪欲 ==
'A'と'B'のそれぞれの個数の積がK以上になるものを見つける。
そのあと'A'を左側、'B'を右側に寄せて、ペアの数がKになるまで'A'と'B'が隣り合っているもののうち最も左側にあるやつをswapしていけばよい。

(例)
AAAABBB

AAABABB

AABAABB

ABAAABB

BAAAABB

BAAABAB
...


== 動的計画法 ==
動的計画法+経路復元で解くことができる。

式は以下のようにして、'A'を0、'B'を1とした。

dp[i文字目][それまでに'A'を何回使ったか][ペアの合計] := i文字目の文字(A or B)

rep(i, N) rep(j, N) rep(k, 2000) {
      if(dp[i][j][k] < 0) continue;
      dp[i + 1][j + 1][k] = 0; // Aを追加
      dp[i + 1][j][j + k] = 1; // Bを追加
    }

i文字目に'A'を置く場合は'A'の個数が1つ増え、'B'を置く場合はそれまで使った'A'を個数分だけペアの数が増える。

この計算が終わったら経路復元をしてやればよい。

余談

コンテスト中では思いつくのが遅くてレートは下がったけど、久々にEasy通せた気がするしまぁよしとする。次頑張ろう。

コンテスト中に通したソースコード

class AB {
public:

  string createString(int N, int K) {
    rep(a, N + 1) {
      int b = N - a;
      if(a * b >= K) {
        string ans = "";
        rep(i, b) ans += "A";
        rep(i, a) ans += "B";
        int cnt = a * b;
        if(cnt == K) return ans;
        for(int i = b; i < N; i++) {
          for(int j = b - 1; j >= i - b; j--) {
            cnt--;
            if(cnt == K) {
              swap(ans[i], ans[j]);
              return ans;
            }
            if(j == i - b) swap(ans[i], ans[j]);
          }
        }
      }
    }
    return "";
  }
};

別解のソースコード

// A = 0, B = 1
int dp[51][51][2200];

class AB {
public:

  string createString(int N, int K) {
    memset(dp, -1, sizeof(dp));
    dp[0][0][0] = 0;

    rep(i, N) rep(j, N) rep(k, 2000) {
      if(dp[i][j][k] < 0) continue;
      dp[i + 1][j + 1][k] = 0;
      dp[i + 1][j][j + k] = 1;
    }

    rep(j, N + 1) {
      if(dp[N][j][K] >= 0) {
        string ans = "";
        for(int i = N; i > 0; i--) {
          if(dp[i][j][K] == 0) {
            ans += "A";
            j--;
          }
          else {
            ans += "B";
            K -= j;
          }
        }
        reverse(all(ans));
        return ans;
      }
    }

    return "";
  }
};