naoya_t@topcoder

過去問マラソン(#10):SRM152

過去問マラソン | 23:40 |

過去問マラソン10回目。

• （いまさらですが）listとかstackとかも使うようになった
• （いまさらですが）vector<char>とstringの相互変換とか
• （いまさらですが）assignが使いこなせるようになった
• cpprefがすごく便利なのでボウズラボに足を向けて寝られない

Easy(250): LeaguePicks

• 問題文の意味がいまいち分からない
• だが解く
  • Sample Caseが通るように修正していく感じ
  • 不安なのでテストケースを追加
• 218.14pt (11'11'')
  • passed system test
• 問題読めてないのに通るのはあまり楽しくない

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class LeaguePicks {
 public:
  vector <int> returnPicks(int position, int friends, int picks) {
    vector<int> res;
    for(int q=0;;){
      int next = q+position;
      if (next>picks) break;
      res.pb(next);
      q+=friends;

      next = q+(friends+1-position);
      if (next>picks) break;
      res.pb(next);
      q+=friends;
    }
    return res;
  }
};

Medium(500): QuiningTopCoder

• Unefungeな言語で書かれたプログラムソースが与えられ、これがQuineになってるかを調べる。
• とりあえずエミュレータ書いて
• 80000サイクルでQuineな出力が得られない場合はTIMEOUT判定
  • 環境(IP,D,stack)をメモ化してみたりとか
• 1投目: failed
  • 環境とっとくなら出力文字列も保存しないと駄目だ
• 2投目: failed
  • ":"１文字のコードでメモ化が破綻する。メモ化やめてみてもいい？...別に80000サイクル回してもTLEにならないっぽいし
• 3投目: passed

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

// BEGIN CUT HERE
void dump_stack(stack<int> st){
  int n = st.size();
  vector<int> vec(n);
  rep(i,n) {
    vec[i] = st.top(); st.pop();
  }
  reverse(all(vec));
  rep(i,n) st.push(vec[i]);
  cout << vec << endl;
}
// END CUT HERE

class UnefungeEmulator {
 private:
  string code; int N;
  int IP, D, cycles;
  stack<int> st;
  stringstream output;
  bool error; string errormsg;

  //set<pair<pair<int,string>,pair<int,stack<int> > > > known;
  
 public:
  UnefungeEmulator(string source) {
    code = source; N = source.size();
    IP = 0;
    D = 1;
    cycles = 0;
    error = false; errormsg = "";
    //known.clear();
  }

  void push(int x) {
    if (x < -1000000000 || 1000000000 < x) {
      error = true;
      errormsg = "OVERFLOW";
      return;
    }
    st.push(x);
  }
  int pop(){
    if (st.empty()) return 0;
    int x = st.top(); st.pop();
    return x;
  }

  void run(){
    while (1) {
      if (error) break;

      string ostr = output.str();
      if (ostr.length() > 0) {
        if (ostr.length() == code.length()) {
          if (ostr == code) break; // QUINE
          else {
            error = true;
            errormsg  = "MISMATCH";
            break;
          }
        }
        if (ostr != code.substr(0,ostr.length())) {
          error = true;
          errormsg  = "MISMATCH";
          break;
        }
      }

      /*
      pair<pair<int,string>,pair<int,stack<int> > > key =
          make_pair(make_pair(IP,ostr), make_pair(D, st) );
      if (found(known,key)) {
        cycles = 80001;
        return;
      }
      known.insert(key);
      */
      
      int D_for_this_cycle = D;
      cycles++; if (cycles > 80000) break;

      switch (code[IP]){
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
          {
            push( code[IP] - '0' );
          }
          break;
        case '$':
          {
            pop();
          }
          break;
        case ':':
          {
            int x = pop();
            push(x); push(x);
          }
          break;
        case 'W':
          {
            int a = pop(), b = pop();
            push(a); push(b);
          }
          break;
        case ',':
          {
            int x = pop();
            char p = code[ abs(x) % N ];
            output << p;
          }
          break;
        case '+':
          {
            int a = pop(), b = pop();
            push( a + b );
          }
          break;
        case '-':
          {
            int a = pop(), b = pop();
            push( a - b );
          }
          break;
        case '#':
          {
            D_for_this_cycle *= 2;
          }
          break;
        case 'R':
          {
            D_for_this_cycle = D = -D;
          }
          break;
        case 'S':
          {
            int x = pop();
            push( x > 0 ? 1 : -1 );
          }
          break;
        case '_':
          {
            int x = pop();
            D_for_this_cycle = D = x % N; // ここの D_for_this_cycle = を忘れてて結果が合わず延々と悩んだ
          }
          break;
        case 'J': // jump
          {
            int x = pop();
            IP = abs(x) % N;
            continue;
          }
          break;
        case '@': // stops the program
          return;
        default: // illegal
          printf("ILLEGAL OP %c\n", code[IP]);
          break;
      }
      IP = (3 * N + IP + D_for_this_cycle) % N;
    }
    // next
  }

  string result(){
    if (cycles > 80000) return "TIMEOUT";
    
    stringstream msg;
    if (error) {
      msg << errormsg;
    } else if (output.str() == code) {
      msg << "QUINES";
    } else {
      msg << "BADEND";
    }
    msg << " " << (cycles - 1);
    return msg.str();
  }
  
};

class QuiningTopCoder {
 public:
  string testCode(string source) {
    UnefungeEmulator emulator(source);
    emulator.run();
    return emulator.result();
  }
};

Hard(1000):