AOJ 1084 K Cards

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1084。

日本語

解法

全探索で解けます。計算量はどれくらいなのかな。どうやって表記するのかよくわからない。 単純にループのとこだけでやるとO(n(n-1)/2(n-k))とか？こんな複雑な書き方ないよね。 O(n³)には収まります。nが100なので大きくてもn⁶*だよね。

コード

int main(){
  int n, k;
  while(scanf("%d%d", &n, &k) && n+k){
    int c[128];
    rep(i, n) scanf("%d", c+i);

    int ck = 1;
    rep(i, k) ck *= c[i];
    int t = ck;
    rep(i, n-k){
      ck /= c[i];
      ck *= c[i+k];
      t = max(t, ck);
    }

    int res = 0;
    rep(i, n)  REP(j, i+1, n){
      swap(c[i], c[j]);
      int ck = 1;
      rep(l, k) ck *= c[l];
      res = max(res, ck);
      rep(l, n-k){
    ck /= c[l];
    ck *= c[l+k];
    res = max(res, ck);
      }
      swap(c[i], c[j]);
    }

    if(res < t) puts("NO GAME");
    else printf("%d\n", res-t);
  }
  return 0;
}

もっときれいにかける気がする。アホですね、これは。やり直し。

int a[128], n, k;

int Ck(){
  int res, t = 1;
  rep(i, k) t *= c[i];
  res = t;
  rep(i, n-k){
    t /= c[i];
    t *= c[i+k];
    res = max(res, t);
  }
  return res;
}

int main(){
  while(scanf("%d%d", &n, &k) && n+k){
    rep(i, n) scanf("%d", c+i);

    t = Ck();

    int res = 0;
    rep(i, n)  REP(j, i+1, n){
      swap(c[i], c[j]);
      res = max(res, Ck());
      swap(c[i], c[j]);
    }

    if(res < t) puts("NO GAME");
    else printf("%d\n", res-t);
  }
  return 0;
}

だいぶ良くなった？