SRM571Div2

Easy:
'o'の数を数える

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)

class FoxAndGame {
public:
  int countStars(vector <string> result) {
    int res=0;
    rep(i,result.size())
      res += (int)count(result[i].begin(),result[i].end(),'o');
    return res;
  }
};

Mid:
辞書順にソートする

#include <vector>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <string>
using namespace std;
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
#define rep(i,n) for(int i=0;i<n;++i)

class FoxAndMp3Easy {
public:
  vector <string> playList(int n) {
    vector <string> res;
    rep(i,n)res.push_back(toString(i+1) + ".mp3");
    sort(res.begin(),res.end());
    while(res.size()>50)res.pop_back();
    return res;
  }
};

Hard:
解けなかったので1位の人のを参考に
O(2^k)のdfsをする

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)

class MagicMoleculeEasy {
public:
  vector<pair<int,int> > G;
  vector<int> S;
  int k;

  int dfs(vector<pair<int,int> > g, long long mask){
    int cnt = 0;
    rep(i,60)if(mask>>i&1)cnt++;

    if(cnt > k)return -1;
    if(g.empty()){
      int sum=0;
      vector<int> score;
      rep(i,S.size())
        if(mask>>i&1)sum+=S[i]; 
        else score.push_back(S[i]);
      sort(score.rbegin(),score.rend());
      rep(i,k-cnt)sum+=score[i];
      return sum;
    }

    int a = g[0].first;
    int b = g[0].second;
    vector<pair<int,int> > g1,g2;
    rep(i,g.size()){
      if(g[i].first != a && g[i].second != a)g1.push_back(g[i]);
      if(g[i].first != b && g[i].second != b)g2.push_back(g[i]);
    }
    return max(dfs(g1,mask|(1LL<<a)), dfs(g2,mask|(1LL<<b)));
  }

  int maxMagicPower(vector <int> magicPower, vector <string> magicBond, int _k) {
    G.clear();
    S = magicPower;
    k = _k;
    int n = magicBond.size();
    rep(i,n)rep(j,n)if(magicBond[i][j]=='Y')G.push_back(make_pair(i,j));
    return dfs(G,0);
  }
};

SRM555Div2

Mid:
ビット列が文字列で与えられる。
5の倍数の文字列で、与えられた文字列を分割していった時に、最小で何分割で済むか。
ただし不可能な場合は-1を返す。

ナップサックなDPをする。汚い。

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

#define rep(i,n) for(int i=0;i<n;++i)
class CuttingBitString {
public:
  int getmin(string S) {
    vector<string> tbl;
    for(long long i=1; i<(1LL<<51); i*=5LL)
    {
      string s;
      for(int j=60; j>=0; --j)
      {
        if(s.size() && !((1LL<<j)&i))s+="0";
        if((1LL<<j)&i) s+="1";
      }
      tbl.push_back(s);
    }

    vector<int> dp(300,-1);
    dp[0] = 0;

    rep(i,S.size()){
      if(dp[i]!=-1){
        rep(j,tbl.size()){
          if(i+tbl[j].size() > S.size())continue;
          bool ok=true;
          rep(k,tbl[j].size()){
            if(S[i+k] != tbl[j][k]){ok=false;break;}
          }
          if(!ok)continue;
          if(S.size() == i+tbl[j].size() || ((S.size() >= i+tbl[j].size()) && (S[i+tbl[j].size()] == '1'))){
            if(dp[i+tbl[j].size()] < 0)dp[i+tbl[j].size()] = dp[i] + 1;
            else dp[i+tbl[j].size()] = min(dp[i+tbl[j].size()], dp[i] + 1);
          }
        }
      }
    }
    return dp[S.size()];
  }
};

SRM561Div2

Mid:
以前本番で解けなかったので復習
制約が n < 50 だったら O(n^2) か O(n^3)を
制約が n < 15 だったら O(2^n) を考えよう。(なんか方向が違う)

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

class ICPCBalloons {
public:
  int minRepaintings(vector <int> Count, string Size, vector <int> AC) {
    int res=1<<30;

    int M=0,L=0;
    vector<int> vM,vL;
    for(int i=0; i<Count.size(); ++i)
    {
      if(Size[i] == 'M')vM.push_back(Count[i]),M+=Count[i];
      if(Size[i] == 'L')vL.push_back(Count[i]),L+=Count[i];
    }
    sort(vM.rbegin(),vM.rend());
    sort(vL.rbegin(),vL.rend());

    int n = AC.size();
    for(int i=0; i<(1<<n); ++i)
    {
      int m=0,l=0;
      for(int j=0; j<n; ++j)
      {
        if(i&(1<<j))l+=AC[j];
        else m+=AC[j];
      }
      if(m>M || l>L)continue;


      vector<int> useM,useL;
      for(int j=0; j<n; ++j)
      {
        if(i&(1<<j))useL.push_back(AC[j]);
        else useM.push_back(AC[j]);
      }
      sort(useM.rbegin(),useM.rend());
      sort(useL.rbegin(),useL.rend());

      int cnt = 0;
      for(int j=0; j<useM.size(); ++j)
      {
        if(j<vM.size())cnt += max(0, useM[j] - vM[j]);
        else cnt += useM[j];
      }

      for(int j=0; j<useL.size(); ++j)
      {
        if(j<vL.size())cnt += max(0, useL[j] - vL[j]);
        else cnt += useL[j];
      }

      res = min(res, cnt);
    }

    if(res == 1<<30)return -1;
    return res;
  }
};

AOJ0200

Traveling Alone: One-way Ticket of Youth
ワーシャルフロイド法って実は使ったことなかった。
mの存在感がない。
timeって使ったらgccさんが怒るらしいのでtimuにした(恥ずかしい）。

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 110;
int timu[N][N];
int cost[N][N];

int main()
{
  int n,m;
  while(cin >> n >> m ,n|m)
  {
    for(int i=0;i<N;++i)
    for(int j=0;j<N;++j)
      timu[i][j] = cost[i][j] = 1<<30;

    for(int i=0;i<n;++i)
    {
      int a,b,c,t;
      cin >> a >> b >> c >> t;
      cost[a][b] = cost[b][a] = c;
      timu[a][b] = timu[b][a] = t;
    }

    for(int k=0;k<N;++k)
    for(int i=0;i<N;++i)
    for(int j=0;j<N;++j)
    {
      cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
      timu[i][j] = min(timu[i][j], timu[i][k] + timu[k][j]);
    }

    int k;
    cin >> k;
    while(k--)
    {
      int p,q,r;
      cin >> p >> q >> r;
      if(r)
        cout << timu[p][q] << endl;
      else
        cout << cost[p][q] << endl;
    }
  }
  return 0;
}

SRM568Div2

Mid:
箱が何個かあって、i番目の箱には赤いボールがR[i]個、緑のボールがG[i]個、青いボールがB[i]個入っている。
それぞれの箱で、1色のボールのみ入っている状態にするために、必要なボールの移動回数を求める。
これも本番で解けなかったorz..

まず箱が2以下だったら不可能なので問答無用で-1を返す。
3以上の時は、先にRGBそれぞれ専用の箱を確定して、後は箱の中で一番数が多いボールを残すようにgreedy.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class BallsSeparating {
public:
  int minOperations(vector <int> R, vector <int> G, vector <int> B) {
    int res=1<<30;
    int N = R.size();
    if(N<3)return -1;

    for(int r=0; r<N; ++r)
    {
      for(int g=0; g<N; ++g)
      {
        if(r==g)continue;
        for(int b=0; b<N; ++b)
        {
          if(r==b || g==b)continue;
          int m=0;
          m += G[r] + B[r];
          m += R[g] + B[g];
          m += R[b] + G[b];

          for(int i=0;i<N; ++i)
          {
            if(i==r || i==g || i==b)continue;
            int sum = R[i] + G[i] + B[i];
            int me  = max(R[i], max(G[i],B[i]));
            m += sum - me;
          }

          res = min(res,m);
        }
      }
    }
    return res;
  }
};

Hard:
手札をシャッフルして、一番上のカードが手札の中で一番小さい数だったらテーブルに置く。
じゃなかったらもう一回シャッフル。を手札がなくなるまで繰り返すときシャッフル回数の期待値を求める。
Hardにしては簡単すぎでは・・

#include <vector>
#include <map>
#include <iostream>
using namespace std;

#define rep(i,n) for(int i=0;i<n;++i)
class ShuffleSort {
public:
  double shuffle(vector <int> cards) {
    sort(cards.begin(),cards.end());
    map<int,int> cnt;
    rep(i,cards.size())
      cnt[cards[i]]++;
    double res=1;
    rep(i,cards.size())
      res += double(cards.size()-i)/(cnt[cards[i]]--) - 1;
    return res;
  }
};

SRM567Div2

Mid:
SSR(A,B) = (√A,√B)^2
という関数があって、1<=A<=N,1<=B<=Mを満たす整数A,B組み合わせの中でSSR(A,B)が整数となるものの数を求める。
本番で解けなかった。

SSR(A,B) = (√A,√B)^2 = A^2 + B^2 + 2*√(AB)
より、√(AB)の値が整数なら条件を満たす。

例えばA=2に固定した時
√2 * √2、
√2 * √8、
√2 * √18なども整数になり条件を満たす。
なのでこのような数は全部√2として扱う。

√の中に平方数を残さない（中学でやる簡単化?）よう処理をしてあげた後、
√の中が同じ物の組み同士を計算。

割と愚直にやっても計算が間に合ってしまう。

#include <vector>
#include <iostream>
using namespace std;
class TheSquareRootDilemma {
public:
    int div(int N)
    {
      for(int i=2; i*i<=N; ++i)
      {
        while(N%(i*i)==0)
        {
          N /= (i*i);
        }
      }
      return N;
    }

    int countPairs(int N, int M) {
      vector<int> A(80000,0),B(80000,0);
      for(int i=1; i<=N; ++i) A[div(i)]++;
      for(int i=1; i<=M; ++i) B[div(i)]++;

      int res=0;
      for(int i=1; i<80000; ++i)
        res += A[i]*B[i];
      return res;
    }
};

AOJ0131

問題:Doctor's Strange Particles
ライツアウトの解を求める。１個しか解がないと言う甘え仕様。
上から順番に処理していく。
まず1行目について全パターンの押し方を試す。
i行目はi-1行目を全て消さないと行けないので、押し方は一意に定まる。
そして一番下の行が全て消えていたらOK。
bitset便利。

#include<iostream>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;

void flip(vector<bitset<10> >& field, int y, int pos)
{
  field[y].flip(pos);
  if(pos+1<10)field[y].flip(pos+1);
  if(pos-1>=0)field[y].flip(pos-1);
  if(y+1<10)field[y+1].flip(pos);
  if(y-1>=0)field[y-1].flip(pos);
}

int main()
{
  int _;
  cin >> _;
  while(_--)
  {
    vector<bitset<10> > f(10,0);
    for(int i=0;i<10;++i)
    {
      int a;
      for(int j=0;j<10;++j)
      {
        cin >> a;
        if(a) f[i].flip(9-j);
      }
    }

    for(int v=0; v<(1<<10); ++v)
    {
      vector<pair<int,int> > ans;
      vector<bitset<10> > field = f;
      for(int i=0;i<10; ++i)
      {
        if(v&(1<<i))
        {
          flip(field,0,i);
          ans.push_back(make_pair(0,i));
        }
      }

      for(int j=1; j<10; ++j)
      {
        for(int k=0; k<10; ++k)
        {
          if(field[j-1][k])
          {
            flip(field,j,k);
            ans.push_back(make_pair(j,k));
          }
        }
      }

      bool clear = !field[9].any();
      if(clear)
      {
        sort(ans.begin(),ans.end());
        for(int i=0; i<10; ++i)
        {
          for(int j=0; j<10; ++j)
          {
            cout << binary_search(ans.begin(),ans.end(),make_pair(i,9-j));
            if(j!=9)cout << " ";
          }
          cout << endl;
        }
      }
    }
  }
  return 0;
}