SRM 384 DIV1 Easy - Library

問題

http://community.topcoder.com/stat?c=problem_statement&pm=7659&rd=10808

解き方

解くだけ。
setを使えば重複の考慮も不要で、条件を満たしているかも簡単に判断できる。

コード

class Library {

public: int documentAccess(vector<string> records, vector<string> userGroups, vector<string> roomRights) {
set<string> user,room;
FORE(i,0,userGroups.size())user.insert(userGroups[i]);
FORE(i,0,roomRights.size())room.insert(roomRights[i]);

set<string> ans;
FORE(i,0,records.size()){
stringstream out(records[i]);
string doc,u,r;
out >> doc >> r >> u;
if(room.find(r)!=room.end() && user.find(u)!=user.end()){
ans.insert(doc);
}
}

return ans.size();
}

};

SRM 393 DIV1 Easy - InstantRunoffVoting

問題

http://community.topcoder.com/stat?c=problem_statement&pm=8607&rd=11127

解き方

問題分の通り実装し、収束するまで繰り返せば良い。

コード

class InstantRunoffVoting {

public: int winner(vector<string> voters) {
int n=voters.size(),m=voters[0].size();
int used[10],v[10];
memset(used,0,sizeof(used));

while(1){
memset(v,0,sizeof(v));
int finish=1;
FORE(i,0,m)if(used[i]==0)finish=0;
if(finish)break;

FORE(i,0,n){
int idx=0;
while(used[voters[i][idx]-'0']==1)idx++;
v[voters[i][idx]-'0']++;
}
FORE(i,0,m)if(v[i]>n*0.5)return i;
int mx=100;
FORE(i,0,m)if(used[i]==0)mx=min(mx,v[i]);
FORE(i,0,m)if(v[i]==mx)used[i]=1;
}

return -1;
}

};

SRM 648 DIV1 Easy - AB (×)

問題

・文字の長さがNであり、’A’か’B’から成る文字列を作りたい。
・ただし、Aより後ろのどこかにBがあるペアをK個作りたい。
・そのような文字列を作れない場合は-1を、作れる場合はそのような文字列のうち一つを出力する。

解き方

・最大のペア数はN/2 * (N-N/2)であるので、これよりもKが大きければそのような文字列を
　作れない。

・作れる場合は実装するだけ。Aを出力するときに、それより右にあるべきBの数を保存してあげるように解いた。

コード

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 AB {

public: string createString(int N, int K) {

string ret="";
for(int a=0;a<=N/2;a++){
int b=N-a;
if(a*b<K)continue;

vector<int> v;
FORE(i,0,a){
int x=min(b,K);
v.push_back(x);
K-=x;
}

FORE(i,0,v.size()){
while(v[i]<b){
ret+='B';
b--;
}
ret+='A';
}
while(b){
ret+='B';
b--;
}

return ret;
}

return "";
}

};

SRM 637 DIV1 Easy - DivisorsPower (○)

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13504&rd=16080

・1から2Nまで書かれた、2N枚のカードがあり、2人でゲームを行う。
・このカードが自分と相手それぞれ均等に配られる。
・2人が一枚ずつカードを出し、大きい数字の方が１ポイント得られる。
・自分のカードについては、何が配られたかわかっている。
・相手のカードについては自分のカードから推測できるが、カードを出す順番もわかっている。
　ただし、-1で示されているときは何が出されるかわかっていない。
・このとき、自分が得ることのできるスコアの最大の期待値を求める。

解き方

・まず、自分のカードから相手のカードを推測し配列に保存する。
・相手のカードについて、出すものがわかっているものに対しては最適な戦略を取る。
・つまり、ある相手のわかっているカードについてそれより大きい数のカードがある場合は
　そのうち最小のものを出す。
・大きい数のカードがない場合は一番小さいカードを出す。
・残りのカードについては総当たりで計算して期待値を足していけばよい。

→System Passed

・もっとシンプルな解き方があるのか他のコードをみてみたが、この方法が一番シンプルそう。
　紙に書いて手順を整理すれば着実に解ける。

コード

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 GreaterGame {

public: double calc(vector<int> hand, vector<int> sothe) {
int n=hand.size();

vector<int> me(2*n+1,0),you(2*n+1,0);
FORE(i,0,n)me[hand[i]]=1;
FORE(i,0,2*n+1)you[i]=1-me[i];

int cnt=0;
FORE(i,0,n)if(sothe[i]==-1)cnt++;

double ret=0.0;
sort(all(sothe));
FORE(i,0,n)if(sothe[i]!=-1){
int win=0;
FORE(j,sothe[i]+1,2*n+1)if(me[j]){
me[j]=0;
ret++;
win=1;
break;
}
you[sothe[i]]=0;

if(!win){
FORE(j,1,2*n+1)if(me[j]==1){
me[j]=0;
break;
}
}
}

FORE(i,1,2*n+1)if(me[i]){
int tmp=0;
FORE(j,1,i)if(you[j])tmp++;
ret+=(double)tmp/cnt;
}

return ret;
}

};

SRM 417 DIV1 Easy - TemplateMatching

問題

http://community.topcoder.com/stat?c=problem_statement&pm=9943&rd=13508

ある文字列と、接頭辞と接尾辞が与えられる。
ある文字列のサブ文字列について、接頭辞と接尾辞ができるだけマッチするものを求める。

ただし、接頭辞と接尾辞のマッチ数が同じときは接頭辞のマッチ数が大きいものにする。
また、上記も同じであれば文字の昇順のものにする。

解き方

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

接頭辞の一致に時間がかかってしまったので、例とＦＯＲを回してみて正しく実装してみるか机上で検証してみるのがやはり大事。

コード

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()

string P,S;

class TemplateMatching {

public:

int prefixes(string str){
int score=0;
int n1=str.size(),n2=P.size();
FOR(i,0,min(n1,n2)){
string s1=str.substr(0,i+1);
string s2=P.substr(n2-1-i,i+1);
if(s1==s2)score=max(score,i+1);
}
return score;
}

int suffixes(string str){
int score=0;
int n1=str.size(),n2=S.size();
FOR(i,0,min(n1,n2)){
string s1=str.substr(n1-1-i,i+1);
string s2=S.substr(0,i+1);
if(s1==s2)score=max(score,i+1);
}
return score;
}

bool valid(int pre,int suf,int maxprev,int maxsuf,string ret,string str){
if(ret=="")return true;
if(pre+suf>maxprev+maxsuf)return true;
if(pre+suf==maxprev+maxsuf && pre>maxprev)return true;
if(pre+suf==maxprev+maxsuf && pre==maxprev && str<ret)return true;
return false;
}

string bestMatch(string text, string prefix, string suffix) {
string ret="";
int maxprev=0,maxsuf=0;
P=prefix;
S=suffix;

FORE(i,0,text.size()){
string str="";
FORE(j,i,text.size()){
str+=text[j];
int pre=prefixes(str);
int suf=suffixes(str);
if(valid(pre,suf,maxprev,maxsuf,ret,str)){
ret=str;
maxprev=pre;
maxsuf=suf;
}
}
}
return ret;
}

};