• ARC
  • C++
  • 22 Dec 2014

    AtCoder Regular Contest 031

    AtCoder Regular Contest 031

    結果 oo*-

    C. 積み木

    愚直アプローチ

    ナイーブに反転数を求める.

    #include <iostream>
    #include <sstream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <set>
    #include <map>
    #include <algorithm>
    #include <utility>
    #include <bitset>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
    #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
    
    ll solve() {
      vector<P> vp;
      for (int i = 0; i < n; i++) {
        vp.push_back(P(b[i], i));
      }
    
      sort(vp.begin(), vp.end());
    
      ll ans = 0;
    
      for(int i = 0; i < n; i++) {
        P p = vp[i];
        int idx = p.second;
        int val = p.first;
    
        // l
        ll lcnt = 0;
        for (int j = idx - 1; j >= 0; j--) {
          if (b[j] == -1) continue;
          //printf("lcnt - %d vs %d\n", val, b[j]);
          if (val < b[j]) {
            ++lcnt;
          }
        }
    
        // r
        ll rcnt = 0;
        for (int j = idx + 1; j < n; j++) {
          if (b[j] == -1) continue;
          //printf("rcnt - %d vs %d\n", val, b[j]);
          if (val < b[j]) ++rcnt;
        }
        ans += min(lcnt, rcnt);
        b[idx] = -1;
      }
      return ans;
    }
    
    int main() {
      while (cin >> n) {
        for(size_t i = 0; i < n; i++)
        {
          cin >> b[i];
        }
        printf("%lld\n", solve());
      }
      return 0;
    }
    BIT(Binary Indexed Tree)

    小さい方 or 大きい方から順番に対応する場所に add していって, 左側と右側の場合の反転数を BitlgN で計算する.

    #include <iostream>
    #include <sstream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <set>
    #include <map>
    #include <algorithm>
    #include <utility>
    #include <bitset>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
    #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
    
    int b[100020], n;
    
    struct Bit {
      const int N;
      vector<int> data;
      Bit(const int size) : N(size + 2), data(n + 4) {}
      void add(int idx, int value) {
        for (int x = idx; x <= N; x += x & -x)
          data[x] += value;
      }
      int sum(int idx) {
        int ret = 0;
        for (int x = idx; x > 0; x -= x & -x)
          ret += data[x];
        return ret;
      }
    };
    
    typedef long long ll;
    
    typedef pair<int,int> P;
    
    ll solve() {
      ll ans = 0;
      Bit bit(n);
    
      vector<P> vp;
      for(int i = 0; i < n; i++)
      {
        vp.push_back(P(b[i], i+1));
      }
    
      sort(vp.begin(), vp.end(), greater<P>());
    
      for(int i = 0; i < n; i++)
      {
        int idx = vp[i].second;
        int lhs = bit.sum(idx);
        int rhs = bit.sum(n) - lhs;
        ans += min(lhs, rhs);
        bit.add(idx, 1);
      }
      return ans;
    }
    
    int main() {
      while (cin >> n) {
        for(size_t i = 0; i < n; i++)
        {
          cin >> b[i];
        }
        printf("%lld\n", solve());
      }
      return 0;
    }

    D. 買い物上手

    全探索アプローチ

    全探索をナイーブに実装すれば部分点は取れる.

    #include <iostream>
    #include <sstream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <set>
    #include <map>
    #include <algorithm>
    #include <utility>
    #include <bitset>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
    #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
    
    int N, M;
    
    int S[102], T[102], K[102];
    
    int A[102][102];
    
    double solve() {
      double ans = 0;
      for (int Set = 0; Set < (1<<N); Set++) {
        bitset<102> bs;
        int exp = 0;
        for (int i = 0; i < N; i++) {
          if (!(Set >> i & 1)) continue;
          exp += S[i];
          for (int j = 0; j < K[i]; j++) {
            bs.set(A[i][j]);
          }
        }
        int sum = 0;
        for (int i = 0; i < M; i++) {
          if (bs[i]) sum += T[i];
        }
        ans = max(ans, (double)exp / sum);
      }
      return ans;
    }
    
    int main() {
      while (cin >> N >> M) {
        for(size_t i = 0; i < N; i++)
        {
          cin>>S[i];
        }
        for(size_t i = 0; i < M; i++)
        {
          cin>>T[i];
        }
        for(size_t i = 0; i < N; i++)
        {
          cin>>K[i];
          for(size_t j = 0; j < K[i]; j++)
          {
            cin>>A[i][j];
            A[i][j]--;
          }
        }
        printf("%lf\n", solve());
      }
    
      return 0;
    }
    最大流

    解説解読中….