Codeforces Round # 185 Div II

Codeforces Round # 185 Div II

http://codeforces.com/contest/312

Codeforces Round # 185 Div IIに参加。システムテストに不備があったようで、Unratedであった。

A. Whose sentence is it?

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

やるだけの問題であったのだが、C++での行指向の入力の実装がうまく行えずPythonを選択。システムテストで落とした。

  • 行末の改行を削除するためにstr.strip()を使った
    • str.strip()は行末の改行だけではなく、空白も削除してしまう。そのため、"lala. "等のような空白を含む行で誤判定をしていた
  • 初めはどこが悪いのか思い当たらなかった。@hogeover30さんに指摘いただいてやっと理解することができた

  • @hogeover30さん、どうもありがとうございます
  • さて、今回はC++での行指向の読み取りをまとめる。特に>>オペレータとstd::getline()を混ぜた場合について考える
  • 今回の問題で与えられる入力は以下のようなものであった
5
I will go to play with you lala.
wow, welcome.
miao.lala.
miao.
miao .
  • 以下のような実装ではこの入力を適切に読むことができない
  int         n;
  std::string s;

  std::cin >> n;

  for (int i = 0; i < n; i ++) {
    std::getline(std::cin, s);

    std::cout << s << std::endl;
  }
  • 結果的に1行目の内容が空となり、本来の5行目は読まれない
I will go to play with you lala.
wow, welcome.
miao.lala.
miao.
  • >>演算子による読み込みが終わった後にストリームの位置が同一行の改行文字の前で止るのが原因だ


  • 1行目の内容が空となるのは、std::getline()が「現在の位置から改行文字が見つかるまで読む。改行文字は読み捨てる」からだ


  • 次の行からは本来意図した動きにはなる


  • 初めの行を読み損ねているので、結果的に入力の最後まで到達できない


  • 数値を読んだ後に、1回改行を読み捨てるのが良さそうだ
    • 提出された実装を読んでみる
    • std::istream::ignore()を使っている実装が多い
  std::cin >> n;

  std::cin.ignore();

  for (int i = 0; i < n; i ++) {
    std::getline(std::cin, s);

    std::cout << s << std::endl;
  }
  • std::istream::ignore()はストリームからn文字を読み捨てる
    • デフォルトでは1文字だ
  • これで望む挙動になった
  • 実験として次のような入力を用意してみた
    • 恐らくCodeforcesではこのような入力を想定しなくても良さそうだが、数値の直後に空白が入っているパターンだ


  • この場合、一文字読み捨てるだけでは誤動作してしまう
    • std::istream::ignore()が1文字読み捨てた状態が以下のような状態となっているからだ


  • このような入力を想定しなければいけない場合は、以下のようにするのがベストプラクティスのようだ
  std::cin >> n;

  std::cin.ignore(1024, '\n');		// 1024は1行としての十分大きな値

  for (int i = 0; i < n; i ++) {
    std::getline(std::cin, s);

    std::cout << s << std::endl;
  }
  • 2つの引数を伴ったstd::istream::ignore()は以下のような挙動となる
    • 第2引数の文字を読んだら終了
    • また、最大で第1引数の文字数をストリームから読んだら終了
  • これでやっと望む挙動になった

C++で書き直した実装は以下のようになった(システムテストを通る)。

#include <iostream>
#include <string>


int main(int argc, char** argv)
{
  int n;

  std::cin >> n;

  std::cin.ignore(1024, '\n');

  for (int i = 0; i < n; i ++) {
    std::string s;

    std::getline(std::cin, s);

    bool freda   = s.rfind("lala.") == (s.size() - 5);
    bool rainbow = s. find("miao.") == 0;

    if (freda == rainbow) {
      std::cout << "OMG>.< I don't know!" << std::endl;
    }
    else if (freda) {
      std::cout << "Freda's" << std::endl;
    }
    else if (! freda && rainbow) {
      std::cout << "Rainbow's" << std::endl;
    }
  }
}
  • 以下のような実装でもよいかもしれない
  std::cin >> n;

  std::getline(std::cin, s);		// 空読みする

  for (int i = 0; i < n; i ++) {
    std::getline(std::cin, s);

    std::cout << s << std::endl;
  }

まとめ

  • >>演算子とstd::getline()を併用するときは、改行の扱いに気をつける
  • そのとき、std::istream::ignore()を活用すると便利