Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2008-12-26

SRM387 Div1 Easy (300points): MarblesRegroupingEasy

| 19:55 | SRM387 Div1 Easy (300points): MarblesRegroupingEasy - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM387 Div1 Easy (300points): MarblesRegroupingEasy - naoya_t@topcoder SRM387 Div1 Easy (300points): MarblesRegroupingEasy - naoya_t@topcoder のブックマークコメント

どう解いたらよいのかぱっとは思いつかない。

全てのmarblejoker boxに放り込む(move回数はN-1)のが手数としては最大になるのかな、というところまで。あとで考えよう。

SRM388 Div1 Easy: SmoothNumbers

| 11:59 | SRM388 Div1 Easy: SmoothNumbers - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM388 Div1 Easy: SmoothNumbers - naoya_t@topcoder SRM388 Div1 Easy: SmoothNumbers - naoya_t@topcoder のブックマークコメント

最初は上(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

| 10:11 | SRM389 Div1 Easy: ApproximateDivision - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM389 Div1 Easy: ApproximateDivision - naoya_t@topcoder SRM389 Div1 Easy: ApproximateDivision - naoya_t@topcoder のブックマークコメント

簡単。

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

| 09:57 | SRM390 Div1 Easy: ConcatenateNumber - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM390 Div1 Easy: ConcatenateNumber - naoya_t@topcoder SRM390 Div1 Easy: ConcatenateNumber - naoya_t@topcoder のブックマークコメント

余裕・・・と思ってたら循環するのを忘れててシステムテストエラー

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

| 09:42 | SRM391 Div1 Easy: IsomorphicWords - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM391 Div1 Easy: IsomorphicWords - naoya_t@topcoder SRM391 Div1 Easy: IsomorphicWords - naoya_t@topcoder のブックマークコメント

問題を読み違えていて問題文の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

| 08:46 | SRM392 Div1 Easy: TwoStringMasks - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM392 Div1 Easy: TwoStringMasks - naoya_t@topcoder SRM392 Div1 Easy: TwoStringMasks - naoya_t@topcoder のブックマークコメント

文字列操作。split()は自前

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

  • 長さは0でもよい
  • 長さのデフォルトはstd::npos(末尾まで)なので、文字列途中から末尾までのsubstringを取りたい場合は第2引数を省略すればいい

という性質を理解していれば煩雑さが少しばかり減る:

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

| 08:51 | split() - naoya_t@topcoder を含むブックマーク はてなブックマーク - split() - naoya_t@topcoder split() - naoya_t@topcoder のブックマークコメント

私家版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;
}

次は文字列(string)をデリミタに取るもの。

#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

| 06:39 | SRM393 Div1 Easy: InstantRunoffVoting - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM393 Div1 Easy: InstantRunoffVoting - naoya_t@topcoder SRM393 Div1 Easy: InstantRunoffVoting - naoya_t@topcoder のブックマークコメント

問題文のルールを素直にコーディングしたら解ける問題。のはずがちょっと手間取り。

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

| 05:57 | SRM394 Div1 Easy: RoughStrings - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM394 Div1 Easy: RoughStrings - naoya_t@topcoder SRM394 Div1 Easy: RoughStrings - naoya_t@topcoder のブックマークコメント

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

| 05:19 | SRM395 Div1 Easy: StreetWalking - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM395 Div1 Easy: StreetWalking - naoya_t@topcoder SRM395 Div1 Easy: StreetWalking - naoya_t@topcoder のブックマークコメント

これは速解き問題。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

| 04:46 | SRM396 Div1 Easy: DNAString - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM396 Div1 Easy: DNAString - naoya_t@topcoder SRM396 Div1 Easy: DNAString - naoya_t@topcoder のブックマークコメント

よくわからないままコーディングしてたらTest Case全て通ったので投稿。システムテストも1発。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

| 04:19 | SRM397 Div1 Easy: SortingGame - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM397 Div1 Easy: SortingGame - naoya_t@topcoder SRM397 Div1 Easy: SortingGame - naoya_t@topcoder のブックマークコメント

手間取った。BFSしてみた。ここで馬鹿の一つ覚え的にpriority_queueを使っているが普通のキューないしvector<int>でも深度を1つずつ下げていけば十分。(と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

| 03:20 | SRM398 Div1 Easy: CountExpressions - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM398 Div1 Easy: CountExpressions - naoya_t@topcoder SRM398 Div1 Easy: CountExpressions - naoya_t@topcoder のブックマークコメント

夜中ですが。目がさめたので練習でもするかと思い

答えが合わないのでおかしいと思ったら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;
  }
};