118D - Caesars Legions

問題

シーザーは兵士を整列させるのが大好きで、n1人の歩兵とn2人の騎兵を所有しています。彼にはこだわりがあって、k1人より多く歩兵が連続して並んでいたり、k2人より多く騎兵が連続して並んでいるのは、美しくない並び方だと思っています。n1,n2,k1,k2が与えられたとき、シーザーが美しいと思う並べ方の総数を答えなさい。(n1,n2<=100 k1,k2<=10)

解法

dp[n][m][k][l]:=「歩兵をn人,騎兵をm人使って,最後にl人の(歩兵(k=0)or騎兵(k=1))が連続するような並べ方の総数」
と定義すると

  • dp[n+1][m][0][0] = Σdp[n][m][1][l] (l=0,...,k2-1) (1が並んでいるところに0を追加する。)
  • dp[n][m+1][1][0] = Σdp[n][m][0][l] (l=0,...,k1-1) (0が並んでいるところに1を追加する。)
  • dp[n+1][m][0][l+1] = dp[n][m][0][l] (0が並んでいるところに0を追加する)
  • dp[n][m+1][1][l+1] = dp[n][m][1][l] (1が並んでいるところに1を追加する)

が成り立つので、ループを使って計算する。
答えは Σdp[n1][n2][k][l]

コード

int main(){
  int n1,n2,k1,k2;
  cin>>n1>>n2>>k1>>k2;
  int dp[102][102][2][11]={};
  dp[1][0][0][0] = 1;
  dp[0][1][1][0] = 1;
  FOR(i,0,n1+1)FOR(j,0,n2+1)REP(k,10){
    dp[i+1][j][0][0] += dp[i][j][1][k];
    dp[i][j+1][1][0] += dp[i][j][0][k];
    if(k+2 <= k1)dp[i+1][j][0][k+1] += dp[i][j][0][k];
    if(k+2 <= k2)dp[i][j+1][1][k+1] += dp[i][j][1][k];
    dp[i+1][j][0][0] %= MOD;
    dp[i][j+1][1][0] %= MOD;
    dp[i+1][j][0][k+1] %= MOD;
    dp[i][j+1][1][k+1] %= MOD;
  }
  int ans = 0;
  REP(i,2)REP(j,10)ans = (ans+dp[n1][n2][i][j])%MOD;
  cout<<ans<<endl;
  return 0;
}

9C - Hexadecimal's Numbers

問題

自然数nが与えられる。各桁が0と1だけで表される数が、1からnの範囲にいくつあるか答えよ。(n<=10^9)

解法

2進表記を10進数とみなした数を作って比較する。

コード

int tob(int n){
  int b = 0;
  stack<int> stk;
  while(n){
    stk.push(n%2);
    n/=2;
  }
  while(!stk.empty()){
    b = b*10 + stk.top(); stk.pop();
  }
  return b;
}
int main(){
  int n;
  cin>>n;
  FOR(ans,2,1024){
    int bnum = tob(ans);
    if(bnum > n){
      cout<<ans-1<<endl;
      break;
    }
  }
  return 0;
}

58B - Coins

問題

バーランド国は新しい硬貨を作ろうと考えた。その硬貨は、それよりも安いすべての硬貨で割り切れるものでなくてはならない。一番高い硬貨の値が与えられるので、なるべく硬貨の数が多くなるように硬貨を構成せよ。

解法

1になるまで、割れる素数で割っていけば良い。

コード

int main(){
  int n;
  cin>>n;
  vector<int> ans;
  ans.push_back(n);
  while(n!=1){
    FOR(i,2,n+1){
      if(n % i == 0){
        n /= i;
        ans.push_back(n);
        break;
      }
    }
  }
  REP(i,ans.size()){
    cout<<ans[i];
    putchar((i==ans.size()-1)?'\n':' ');
  }
  return 0;
}

131C - The World is a Theatre

問題

n人の男と、m人の女がいる。t人の選び方が何通りあるか求めよ。ただし、t人の中に少なくとも4人の男と1人の女が含まなければならない。(n,m<=30 t<=n+m)

解法

combinationを使って計算。

コード

int main(){
  ll comb[50][50];
  REP(i,50)comb[i][0] = comb[i][i] = 1;
  FOR(i,1,50)FOR(j,1,50)comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
  int n,m,t;
  cin>>n>>m>>t;
  ll ans = 0;
  FOR(man,4,t+1){
    int woman = t - man;
    if(woman > 0 && man <= n && woman <= m){
      ans += comb[n][man] * comb[m][woman];
    }
  }
  cout<<ans<<endl;

  return 0;
}

ZOJ 2886 Look and Say

問題

122344→11221324のような変換をする。(1個の1,2個の2,1個の3,2個の4).。

コード

int main(){
  int n;
  cin>>n;
  while(n--){
    string s;
    cin>>s;
    s += '#';
    int count = 1;
    FOR(i,1,s.size()){
      if(s[i]!=s[i-1]){
        printf("%d%c",count,s[i-1]);
        count = 1;
      }else{
        count++;
      }
    }
    putchar('\n');
  }
  return 0;
}