TopCoder SRM 526 過去問

SRM526 の Div2 Easy Medium を解きました。

Easy

ABC三種類の文字からなる文字列が存在する。
先頭からi文字目以降に何種類の文字があるかを格納したvectorを返す。

解法

ケツからみていくだけです。

提出コード

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

#include <algorithm> #include <iostream> #include <map> #include <numeric> #include <set> #include <sstream> #include <string> #include <vector> #include <cstring> #include <cstdio> #include <cstdlib> #include <stack> #include <deque> #include <queue> #include <functional>   using namespace std;   #define REP(i,s,e) for (int i = int(s); i != int(e); i++) #define rep(i,e) REP(i,0,e) #define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++) #define ALL(c) ((c).begin(), (c).end()) #define ll long long #define VI vector<int>   class CheatingQuiz {       public: vector<int> howMany(string answers) {         int count = 0;         bool abc[3];         memset(abc,false,sizeof(abc));         vector<int> ans;         for(int i = answers.length()-1; i >= 0;i--){             if(count == 3){                 ans.push_back(3);                 continue;             }             switch(answers[i]){             case 'A':                 if(!abc[0]){                     abc[0] = true;                     count++;                 }                 break;               case 'B':                 if(!abc[1]){                     abc[1] = true;                     count++;                 }                 break;               case 'C':                 if(!abc[2]){                     abc[2] = true;                     count++;                 }                 break;             }             ans.push_back(count);         }         reverse( ans.begin(), ans.end() );         return ans;     }   };

Medium

n行m列の行列がある。
各行、各列ごとに最大１羽、アヒルが居る。 
アヒルを移動させて、縦でも横でもいいから整列させたい。
アヒルは、移動先が空いていればどこへでも移動が可能で、移動にかかる時間はハミルトン距離によって算出される。
整列するのにかかる最小の時間を求めよ。

解法

どういう整列のさせ方をするかが決まれば、その整列の実現にかかる最小の時間は一意に定まる。
よって、全通り試して最小の時間を返せばよい。
より具体的には、例えば横に並べる場合、最も左に居るアヒルを列の最も左に移動させ、そのアヒルの次に最も左に居るアヒルをその右へ移動させ。。。と整列させる。
縦に並べる場合も同じである。
この整列のさせ方が最小の時間を取ることは、図を書けば直ちに分かる。
実装では、二次元の構造体にアヒルの位置を記憶させ、vectorにしまったのち、xとyそれぞれに対してバブルソートを行わせる関数を実装して対処した。

提出コード

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87

#include <algorithm> #include <iostream> #include <map> #include <numeric> #include <set> #include <sstream> #include <string> #include <vector> #include <cstring> #include <cstdio> #include <cstdlib> #include <stack> #include <deque> #include <queue> #include <functional>   using namespace std;   #define REP(i,s,e) for (int i = int(s); i < int(e); i++) #define rep(i,e) REP(i,0,e) #define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++) #define ALL(c) (c).begin(), (c).end() #define ll long long #define VI vector<int> #define INF 1<<30   typedef struct pos{     int x;     int y;       int hamiltone_distance(int _x, int _y){         return (abs(x - _x) + abs(y - _y));     } };   void sort_column(vector<pos>& s){     bool recursive = false;     REP(i,1,s.size()){         if(s[i-1].y > s[i].y){             swap(s[i],s[i-1]);             recursive = true;         }     }     if(recursive) sort_column(s); }   void sort_row(vector<pos>& s){     bool recursive = false;     REP(i,1,s.size()){         if(s[i-1].x > s[i].x){             swap(s[i],s[i-1]);             recursive = true;         }     }     if(recursive) sort_column(s); }   class DucksAlignment {       public: int minimumTime(vector<string> grid) {         int ans = INF;         int column = grid.size();         int row = grid[0].length();         vector<pos> ret;         rep(i,column) rep(j,row){             if(grid[i][j] == 'o'){                 pos tmp = {j,i};                 ret.push_back(tmp);             }         }         int sum;         sort_row(ret);         rep(i,column) rep(j,row-ret.size()+1){             sum = 0;             rep(k,ret.size()) sum += ret[k].hamiltone_distance(j+k,i);             ans = min(sum,ans);         }         swap(column,row);         sort_column(ret);         rep(i,column) rep(j,row-ret.size()+1){             sum = 0;             rep(k,ret.size()) sum += ret[k].hamiltone_distance(i,j+k);             ans = min(sum,ans);         }         return ans;     } };