2008-12-26
SRM387 Div1 Easy (300points): MarblesRegroupingEasy
どう解いたらよいのかぱっとは思いつかない。
全てのmarbleをjoker boxに放り込む（move回数はN-1）のが手数としては最大になるのかな、というところまで。あとで考えよう。
SRM388 Div1 Easy: SmoothNumbers
最初は上(N)から攻めていたが下(1)からに変更。
class SmoothNumbers {
int N_;
vector<int> primes;
vector<bool> memo;
void sub(int n){
tr(primes,it){
int np = *it * n;
if (np>N_) continue;
if (!memo[np]) { sub(np); memo[np]=true; }
}
}
public:
int countSmoothNumbers(int N, int k) {
N_=N;
int primes_[25] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97 };
memo.resize(N+1); fill(all(memo),false);
memo[1]=true;
rep(i,25) {
int p=primes_[i];
if(p<=k) primes.pb(p);
else break;
}
sub(1);
int cnt=0; for(int i=1;i<=N;i++) if(memo[i]) cnt++;
return cnt;
}
};
SRM389 Div1 Easy: ApproximateDivision
簡単。
class ApproximateDivision {
public:
double quotient(int a, int b, int terms) {
int t=1;
while(1){ if(t<b) t*=2; else break; }
int c=t-b;
double d=0, e=1.0/t, r=1.0*c/t;
rep(i,terms) {d+=e; e*=r;}
return d*a;
}
};
SRM390 Div1 Easy: ConcatenateNumber
余裕・・・と思ってたら循環するのを忘れててシステムテストエラー
class ConcatenateNumber {
public:
int getSmallest(int number, int k) {
long long f=1, k_=k;
for(int n=number;n>0;n/=10) f*=10;
f%=k;
long long n_=number%k, rem=n_;
if(rem==0) return 1;
set<int> rep; rep.insert(rem); // 循環検出用。bool[k]でいいんですけど
int cnt=1;
while(1){
cnt++;
long long new_rem = ((rem*f) + n_)%k_;
if(found(rep,new_rem)) return -1;
// if(new_rem==rem) return -1; // これだけだと駄目
if(new_rem==0) return cnt;
rep.insert(new_rem);
rem=new_rem;
}
}
};
SRM391 Div1 Easy: IsomorphicWords
問題を読み違えていて問題文のTest Caseすら通らず焦る。
最初はインデックスを作ろうとしていたが、比較がややこしいので総当たりに変更。
class IsomorphicWords {
int l;
bool isomor(string w1, string w2){
vector<int> oc(26,-1);
rep(i,l){
int a=w1[i]-'a', b=w2[i]-'a';
if (oc[a]<0) oc[a]=b;
else if (oc[a]!=b) return false;
}
vector<int> ck(26,0);
rep(i,26) {
if (oc[i]<0) continue;
if (++ck[oc[i]] > 1) return false;
}
return true;
}
public:
int countPairs(vector<string> words) {
int n=sz(words); //2-50
l=words[0].length();
int count=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++) {
if (isomor(words[i], words[j])) count++;
}
}
return count;
}
};
SRM392 Div1 Easy: TwoStringMasks
class TwoStringMasks {
public:
string shortestCommon(string s1, string s2) {
vector<string> v1 = split(s1,'*'), v2 = split(s2,'*');
int l1a=v1[0].length(), l1b=v1[1].length(),
l2a=v2[0].length(), l2b=v2[1].length();
int coma=min(l1a,l2a), comb=min(l1b,l2b);
if(coma>0){
if (v1[0].substr(0,coma)!=v2[0].substr(0,coma)) return "impossible";
}
if(comb>0){
if (v1[1].substr(l1b-comb,comb)!=v2[1].substr(l2b-comb,comb)) return "impossible";
}
string prefix = v1[0].substr(0,coma), suffix = v1[1].substr(l1b-comb,comb);
v1[0]=(l1a==coma)?"":v1[0].substr(coma,l1a-coma); l1a-=coma;
v2[0]=(l2a==coma)?"":v2[0].substr(coma,l2a-coma); l2a-=coma;
v1[1]=(l1b==comb)?"":v1[1].substr(0,l1b-comb); l1b-=comb; // l1b==comaとか書いてて結果が合わなかったりした。substrは長さに0を渡しても大丈夫なのでこのチェックは不要だった
v2[1]=(l2b==comb)?"":v2[1].substr(0,l2b-comb); l2b-=comb;
string a=(l1a>l2a)?v1[0]:v2[0], b=(l1b>l2b)?v1[1]:v2[1];
if ((l1a>=l2a && l1b>=l2b) || (l1a<l2a && l1b<l2b)) return prefix + a + b + suffix;
int al=a.length(), bl=b.length();
for(int l=min(al,bl);l>0;l--) {
if (a.substr(al-l,l)==b.substr(0,l))
return prefix + a + b.substr(l,bl-l) + suffix;
}
return prefix + a + b + suffix;
}
};
string.substr()の
という性質を理解していれば煩雑さが少しばかり減る：
class TwoStringMasks {
public:
string shortestCommon(string s1, string s2) {
vector<string> v1 = split(s1,'*'), v2 = split(s2,'*');
int l1a=v1[0].length(), l1b=v1[1].length(),
l2a=v2[0].length(), l2b=v2[1].length();
int coma=min(l1a,l2a), comb=min(l1b,l2b);
if(coma>0){
if (v1[0].substr(0,coma)!=v2[0].substr(0,coma)) return "impossible";
}
if(comb>0){
if (v1[1].substr(l1b-comb)!=v2[1].substr(l2b-comb)) return "impossible";
}
string prefix = v1[0].substr(0,coma), suffix = v1[1].substr(l1b-comb);
v1[0]=v1[0].substr(coma); l1a-=coma;
v2[0]=v2[0].substr(coma); l2a-=coma;
v1[1]=v1[1].substr(0,l1b-comb); l1b-=comb;
v2[1]=v2[1].substr(0,l2b-comb); l2b-=comb;
string a=(l1a>l2a)?v1[0]:v2[0], b=(l1b>l2b)?v1[1]:v2[1];
if ((l1a>=l2a && l1b>=l2b) || (l1a<l2a && l1b<l2b)) return prefix + a + b + suffix;
int al=a.length(), bl=b.length();
for(int l=min(al,bl);l>0;l--) {
if (a.substr(al-l)==b.substr(0,l))
return prefix + a + b.substr(l) + suffix;
}
return prefix + a + b + suffix;
}
};
split()
Library | | 
私家版split()関数。
まずはデリミタがintのもの。
省略時には空白をデリミタとして認識する。
#include <string>
#include <vector>
using namespace std;
vector<string> split(string str, int delim=' ')
{
vector<string> result;
const char *s = str.c_str();
if (delim == ' ') {
for (const char *p=s; *p; p++) {
if (*p == delim)
s++;
else
break;
}
if (!*s) return result;
for (const char *p=s; *p; p++) {
if (*p == delim) {
if (s < p) {
string a(s,p-s);
result.push_back(a);
}
s = p + 1;
}
}
if (*s) result.push_back(s);
} else {
for (const char *p=s; *p; p++) {
if (*p == delim) {
string a(s,p-s);
result.push_back(a);
s = p + 1;
if (*s == '\0') result.push_back("");
}
}
if (*s) result.push_back(s);
}
return result;
}
#include <string>
#include <vector>
using namespace std;
vector<string> split(string str, string delim)
{
vector<string> result;
if (str.length() == 0) return result;
if (delim.length() == 0) {
int len = str.length();
result.resize(len);
for (int i=0; i<len; i++) result[i] = str.substr(i,1);
return result;
}
int since = 0, at;
while ((at = str.find(delim, since)) != string::npos) {
result.push_back(str.substr(since, at-since));
since = at + delim.length();
}
result.push_back(str.substr(since));
return result;
}
自由に使っていいけど無保証。ご利用は計画的に。
おまけ
googletestもつけとくよ。
#include <gtest/gtest.h>
// テストケースを単体の関数として実装する
TEST(SplitTest, Split1)
{
vector<string> result;
result = split("", "<>");
EXPECT_EQ( 1, result.size() );
// "a","<>" => ["a"]
result = split("a", "<>");
EXPECT_EQ( 1, result.size() );
EXPECT_EQ( "a", result[0] );
// "a<>b<>c","<>" => ["a","b","c"]
result = split("a<>b<>c", "<>");
EXPECT_EQ( 3, result.size() );
EXPECT_EQ( "a", result[0] );
EXPECT_EQ( "b", result[1] );
EXPECT_EQ( "c", result[2] );
// "a<>b<>c<>","<>" => ["a","b","c",""]
result = split("a<>b<>c<>", "<>");
EXPECT_EQ( 4, result.size() );
EXPECT_EQ( "a", result[0] );
EXPECT_EQ( "b", result[1] );
EXPECT_EQ( "c", result[2] );
EXPECT_EQ( "" , result[3] );
// "<>a<>b<>c","<>" => ["","a","b","c"]
result = split("<>a<>b<>c", "<>");
EXPECT_EQ( 4, result.size() );
EXPECT_EQ( "" , result[0] );
EXPECT_EQ( "a", result[1] );
EXPECT_EQ( "b", result[2] );
EXPECT_EQ( "c", result[3] );
// "<>a<>","<>" => ["","a",""]
result = split("<>a<>", "<>");
EXPECT_EQ( 3, result.size() );
EXPECT_EQ( "" , result[0] );
EXPECT_EQ( "a", result[1] );
EXPECT_EQ( "" , result[2] );
// "a<><>b","<>" => ["a","","b"]
result = split("a<><>b", "<>");
EXPECT_EQ( 3, result.size() );
EXPECT_EQ( "a", result[0] );
EXPECT_EQ( "" , result[1] );
EXPECT_EQ( "b", result[2] );
// "<>","<>" => ["",""]
result = split("<>", "<>");
EXPECT_EQ( 2, result.size() );
EXPECT_EQ( "", result[0] );
EXPECT_EQ( "", result[1] );
//
result = split("", "");
EXPECT_EQ( 0, result.size() );
// 特殊用法 "abc".split('')
result = split("abc", "");
EXPECT_EQ( 3, result.size() );
EXPECT_EQ( "a", result[0] );
EXPECT_EQ( "b", result[1] );
EXPECT_EQ( "c", result[2] );
// EXPECT_TRUE_EQUAL( 2, 2 );
}
TEST(SplitTest, Split2)
{
// cout << "test_split()" << endl;
// dump_vs(result);
vector<string> result;
// "" => []
result = split("");
EXPECT_EQ( 0, result.size() );
// "a" => ["a"]
result = split("a");
EXPECT_EQ( 1, result.size() );
EXPECT_EQ( "a", result[0] );
// "a b c" => ["a","b","c"]
result = split("a b c");
EXPECT_EQ( 3, result.size() );
EXPECT_EQ( "a", result[0] );
EXPECT_EQ( "b", result[1] );
EXPECT_EQ( "c", result[2] );
// "a " => ["a"]
result = split("a ");
EXPECT_EQ( 1, result.size() );
EXPECT_EQ( "a", result[0] );
// " a" => ["a"]
result = split(" a");
EXPECT_EQ( 1, result.size() );
EXPECT_EQ( "a", result[0] );
// " a " => ["a"]
result = split(" a ");
EXPECT_EQ( 1, result.size() );
EXPECT_EQ( "a", result[0] );
// "a b" => ["a","b"]
result = split("a b");
EXPECT_EQ( 2, result.size() );
EXPECT_EQ( "a", result[0] );
EXPECT_EQ( "b", result[1] );
// "a b" => ["a","b"]
result = split("a b");
EXPECT_EQ( 2, result.size() );
EXPECT_EQ( "a", result[0] );
EXPECT_EQ( "b", result[1] );
// "a b c",'b' => ["a "," c"]
result = split("a b c",'b');
EXPECT_EQ( 2, result.size() );
EXPECT_EQ( "a ", result[0] );
EXPECT_EQ( " c", result[1] );
// "a,b",',' => ["a","b"]
result = split("a,b", ',');
EXPECT_EQ( 2, result.size() );
EXPECT_EQ( "a", result[0] );
EXPECT_EQ( "b", result[1] );
// "a,,b",',' => ["a","","b"]
result = split("a,,b", ',');
EXPECT_EQ( 3, result.size() );
EXPECT_EQ( "a", result[0] );
EXPECT_EQ( "" , result[1] );
EXPECT_EQ( "b", result[2] );
// ",a",',' => ["","a"]
result = split(",a", ',');
EXPECT_EQ( 2, result.size() );
EXPECT_EQ( "" , result[0] );
EXPECT_EQ( "a", result[1] );
// "a,",',' => ["a",""]
result = split("a,", ',');
EXPECT_EQ( 2, result.size() );
EXPECT_EQ( "a", result[0] );
EXPECT_EQ( "" , result[1] );
// ",a,",',' => ["","a",""]
result = split(",a,", ',');
EXPECT_EQ( 3, result.size() );
EXPECT_EQ( "" , result[0] );
EXPECT_EQ( "a", result[1] );
EXPECT_EQ( "" , result[2] );
}
int main(int argc, char** argv)
{
testing::InitGoogleTest(&argc, argv);
return RUN_ALL_TESTS();
}
SRM393 Div1 Easy: InstantRunoffVoting
問題文のルールを素直にコーディングしたら解ける問題。のはずがちょっと手間取り。
vector<int> voからvo[0]の値と同じ値の要素をすべて捨てるための自作マクロremove_()を使っているが、remove_(vo,vo[0])は予期しない結果を生む。これでハマった。
あと、得票ゼロの候補者を捨て忘れていてシステムテストに引っかかるなど。
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define found(s,e) ((s).find(e)!=(s).end())
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())
class InstantRunoffVoting {
public:
int winner(vector<string> voters) {
int population=sz(voters), // 1-50
N=voters[0].length(); //1-10
set<int> s; rep(i,N) s.insert(i);
while(sz(s)>0){
vector<int> votes(N,0);
rep(p,population){
rep(i,N) {
int c=voters[p][i]-'0';
if(found(s,c)) { votes[c]++; break; }
}
}
vector<int> vo(all(votes));
rep(i,N) if(votes[i]==0) s.erase(i); //これが抜けてた
remove_(vo,0);
sort(all(vo));
if(sz(vo)==0) return -1;
if(sz(vo)==1) rep(i,N) if(votes[i]==vo[0]) return i;
int minvote=vo[0];
rep(i,N) if(votes[i]==minvote) s.erase(i);
remove_(vo,minvote); // ※
if(sz(vo)==0) return -1;
if(sz(vo)==1) rep(i,N) if(votes[i]==vo[0]) return i;
}
}
};
SRM394 Div1 Easy: RoughStrings
TLE
・・・メモ化しないと駄目です
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define found(s,e) ((s).find(e)!=(s).end())
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())
class RoughStrings {
int n_;
map<vector<int>,int> memo;
int sub(vector<int> v, int d){
remove_(v,0); // メモ参照の前に0要素を消さないと激しく遅い
if(found(memo,v)) return memo[v]; // これが後
int l=v.size(); if(l<=1) return 0;
sort(all(v));
int minr = v[l-1]-v[0];
if(d==n_) return memo[v]=minr;
if (v[0]>0) {
v[0]--;
minr = min(minr,sub(v,d+1));
v[0]++;
}
v[l-1]--;
minr = min(minr,sub(v,d+1));
v[l-1]++;
return memo[v]=minr;
}
public:
int minRoughness(string s, int n) {
n_=n;
vector<int>cn(26,0);
int m=s.length(); //1-50
rep(i,m) cn[s[i]-'a']++;
return sub(cn,0);
}
};
SRM395 Div1 Easy: StreetWalking
これは速解き問題。Test Caseが親切。（斜め／＼に進んだほうが速いケースとか）
class StreetWalking {
public:
long long minTime(int X, int Y, int walkTime, int sneakTime) {
if(X>Y)swap(X,Y);
long long a=Y-X, b=X, h=a/2, m=a%2;
long long t = min(b*2*walkTime, b*sneakTime)
+ min(a*walkTime, h*2*sneakTime+m*walkTime);
return t;
}
};
SRM396 Div1 Easy: DNAString
よくわからないままコーディングしてたらTest Case全て通ったので投稿。システムテストも１発。12分前後。
maxPeriod以内の周期pを全て試してみて、各位置 mod pについて出現頻度が最大の文字に置き換える場合の変更字数を数えているだけ。
class DNAString {
public:
int acgt(int ch) {
switch(ch) {
case 'A': return 0;
case 'C': return 1;
case 'G': return 2;
case 'T': return 3;
}
}
int minChanges(int maxPeriod, vector<string> dna) {//42937
string dnac = ""; tr(dna,it) dnac += *it; int n=dnac.length();
int minch = INT_MAX;
for(int p=1;p<=maxPeriod;p++) {
vector<vector<int> > st(p);
int changes=0;
tr(st,it) { it->resize(4); fill(all(*it),0);}
rep(i,n) st[i%p][acgt(dnac[i])]++;
rep(i,p) {
int maxc=0,totc=0;
rep(j,4) {
totc+=st[i][j]; if(st[i][j]>maxc) maxc=st[i][j];
}
changes+=totc-maxc;
}
if (minch>changes)minch=changes;
}
return minch;
}
};
SRM397 Div1 Easy: SortingGame
手間取った。BFSしてみた。ここで馬鹿の一つ覚え的にpriority_queueを使っているが普通のキューないしvector<int>でも深度を１つずつ下げていけば十分。（とTOPの人のコードを見て悟った）
class SortingGame {
int n;
int sig(const vector<int> &b){
int s=0;
tr(b,it){s=s*n+(*it)-1;}
return s;
}
void reset(vector<int> &b,int sig) {
for (int i=n-1,s=sig;i>=0;i--,s/=n) b[i]=(s%n)+1;
}
public:
int fewestMoves(vector<int> board, int k) {
n=sz(board);
int board_sig=sig(board);
vector<int> sorted(all(board)); sort(all(sorted));
int sorted_sig=sig(sorted);
if(board_sig==sorted_sig) return 0;
priority_queue<pair<int,int> > pq;
for(int b=0;b<=n-k;b++) {
reverse(board.begin()+b,board.begin()+b+k);
int newsig=sig(board);
if(newsig==sorted_sig) return 1;
pq.push(make_pair(-1,newsig));
reset(board,board_sig);
}
map<int,int> visited; visited[board_sig]=0;
while(!pq.empty()) {
int depth=pq.top().first, sg=pq.top().second;
pq.pop();
if(visited.find(sg)!=visited.end()) continue;
visited[sg]=depth;
for(int b=0;b<=n-k;b++) {
reset(board,sg);
reverse(board.begin()+b,board.begin()+b+k);
int newsig=sig(board);
if(newsig==sorted_sig) return -depth+1;
pq.push(make_pair(depth-1,newsig));
}
}
return -1;
}
};
SRM398 Div1 Easy: CountExpressions
夜中ですが。目がさめたので練習でもするかと思い
答えが合わないのでおかしいと思ったらaを上書きしまくってた件
投稿まで11分超かかった...
class CountExpressions {
int op(int x,int y,int opid){
int val=0;
switch(opid){
case 0: val=x+y;break;
case 1: val=x-y;break;
case 2: val=x*y;break;
}
return val;
}
public:
int calcExpressions(int x, int y, int val) {
int cnt=0;
vector<int> n(4); n[0]=n[1]=min(x,y); n[2]=n[3]=max(x,y);
while(1){
int a=n[0];
rep(op1,3) {
int k=a;
a=op(a,n[1],op1);
rep(op2,3) {
int j=a;
a=op(a,n[2],op2);
rep(op3,3) {
int i=a;
a=op(a,n[3],op3);
if (a==val) cnt++;
a=i;
}
a=j;
}
a=k;
}
if(!next_permutation(all(n)))break;
}
return cnt;
}
};
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081226