水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

プログラミング雑記 #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;
}


実際の提出結果はこちら.


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



正規表現の練習のために書いてみたのに通らないとは非常に悲しい結果になりましたね….


他言語でやった場合どうなるんでしょうね? あと正規表現がどうしてこんなにメモリを食っているのか,疑問に思ったので,機会があれば調査したいと思います.ただ,C++はあんまりやる気が…(ごめんなさい)



最後に,ラムダ式を書く際に参考にしたのは以下のサイトです….あと私のローカルだと,-std=c++11を指定しないとコンパイルうまくいかないので,alias貼っておこうかなあ….

ラムダ式 - C++入門


あとTextMateで初めてプログラム書いたけど,動作が軽量で非常に気持が良かったです.まる.


yumechi0525.hatenablog.com

10 / 300