プログラミング雑記 #2 （2016/01/14）

気が向いた時に更新するのでプログラミング雑記．

試しにC++の正規表現を使ったプログラムを書いたのですが，なんかうまく行かなかったのでその話です．

練習がてらこの問題を解いていました．

http://codeforces.com/contest/616/problem/A

問題の概要としては，2つの数字列が与えられる（ただし長さは10^6もあり，leading zeroが含まれる場合もある）ので，その大きさを比べて結果を返せ，ということになります．

ここでピンときた方もいると思いますが，正規表現を使えば，leading zeroの部分をマッチさせることができますよね？それを使って今回は置換を行おうと考えました．

参考にしたのは以下のサイトです．

本の虫: C++の正規表現ライブラリ: std::regex

C++で正規表現を用いるためには，regexをincludeする必要があります．なのでまずはこれをinclude．．．

次にregexクラスの初期化子として，正規表現のパターンを与えられるので，

regex re("^0+");

みたいな感じで宣言しました．（参照先はRって言う文字が入っていましたが，Rなしじゃないとコンパイル通らなかった）

これと，regex_replace(str, pattern, replace_word) っていうメソッドを使うと，正規表現にマッチした文字列部分を置き換えることが可能です．つまり今回なら，

string first;
cin >> first;
regex re("^0+");
first = regex_replace(first, re, "");

と書いてあげれば，leading zeroを消すことができそうです．

leading zeroを消したあとは，1つ目と2つ目の文字列の長さを比べてみて，違っていれば長さの比較をして，一緒ならば，辞書順で考えた時にどちらが先なのかで判断します（この場合は数字の大小でなく，辞書順で考えても大丈夫なケースのため，もちろんダメな場合もある）

ラムダ式も用いて，遊びながら以下のコードを書きました．

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(16);
  
  string first, second;
  cin >> first >> second;
  
  cout << [=] (regex pattern) {
      return [=] (string f, string s) {
          if(f.size() != s.size()) return f.size() > s.size() ? ">" : "<";
          return f == s ? "=" :
          f > s ? ">" : "<";
      } (regex_replace(first, pattern, ""), regex_replace(second, pattern, ""));
  } (regex("^0+")) << endl;
  
  return 0;
}

で，提出してみると．

Memory limit exceeded on test 20

おいおいまじかよ…．しかも思っていた以上に遅い…．実際の提出結果は次のリンクです．

http://codeforces.com/contest/616/submission/15342567

というわけで，0が大量に続くようなパターンではメモリをどか食いしてしまうようです…．

こんな単純な文字列でも，こういう罠が潜んでいるんですね…．

というわけで，正規表現を使わず，forループで頭から見ていった時に0以外の数値になるような時に，新しくleading zeroを省いた文字列を作るようなコードにして提出しなおしましたとさ．以下のとおり．

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(16);
  
  string first, second;
  cin >> first >> second;
  
  cout << [=] () {
      auto shaping = [=] (string str) {
          int length = str.size();
          for(int i = 0; i < length; i++) 
              if(str[i] != '0') return str.substr(i);
          return string("");
      };
      return [=] (string f, string s) {
          if(f.size() != s.size()) return f.size() > s.size() ? ">" : "<";
          return f == s ? "=" :
          f > s ? ">" : "<";
      } ( shaping(first), shaping(second) );
  } () << endl;
  
  return 0;
}