SRM 242 DIV1 Easy - GuessCard (復習○)

February 11, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=4490&rd=7217

行と列の長さが与えられ、最初は１行目から順に１，２、３・・・と数字が入っている。
ここで、ある数字を思い浮かべたとき、その数字が何列目に入っているか答える。
答えた後は行と列の数字を入れ替えて、また何列目に入っているか答える。

この操作を繰り返した時、最後に思い浮かべた数字のある行を答える。
複数存在しうるとき、またひとつも存在しないときはー１を返す。

解き方

シミュレーション問題なので、いかにシンプルに実装するか。

候補の数の更新には配列で＆を使ってもよいが、insertのすでに入っているかの判定を使うことでよりシンプルになる。

数字の入れ替えは間違えやすいので例を出しながら確かめる。

コード

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class GuessCard {

public: int whichRow(int width, int height, vector<int> columns) {
set<int> s;
FORE(n,1,height*width+1)s.insert(n);

int p[height][width],n=1;
FORE(i,0,height)FORE(j,0,width){
p[i][j]=n;
n++;
}

FORE(i,0,columns.size()){
set<int> cs;
FORE(j,0,height)if(s.count(p[j][columns[i]]))cs.insert(p[j][columns[i]]);
s=cs;

vector<int> tmp;
FORE(b,0,width)FORE(a,0,height)tmp.push_back(p[a][b]);

if(i!=columns.size()-1){
int idx=0;
FORE(a,0,height)FORE(b,0,width){
p[a][b]=tmp[idx];
idx++;
}
}
}

if(s.size()!=1)return -1;
FORE(i,0,height)FORE(j,0,width)if(p[i][j]==*s.begin())return i;
return -1;
}

};

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class GuessCard {

public: int whichRow(int w, int h, vector<int> columns) {
int cur[h][w];
int cnt=1;
FORE(i,0,h)FORE(j,0,w)cur[i][j]=cnt++;

int num[h*w+1];
memset(num,1,sizeof(num));
FORE(i,0,columns.size()){
int tmp[h*w+1];
memset(tmp,0,sizeof(tmp));
FORE(j,0,h)tmp[cur[j][columns[i]]]=1;
FORE(j,0,h*w+1)num[j]&=tmp[j];

int next[h][w];
cnt=0;
FORE(j,0,h)FORE(k,0,w)next[j][k]=cur[cnt%h][cnt/h],cnt++;
if(i!=columns.size()-1)FORE(j,0,h)FORE(k,0,w)cur[j][k]=next[j][k];
}

int idx=-1,ret=-1;
cnt=0;
FORE(i,0,h*w+1)if(num[i])idx=i,cnt++;
if(cnt!=1)return -1;
FORE(i,0,h)FORE(j,0,w)if(cur[i][j]==idx)ret=i;
return ret;
}

};

実装