Hatena::Grouptopcoder

agwの日記 RSSフィード

 | 

2013-05-28Codeforces Round # 185 Div II

Codeforces Round # 185 Div II

11:04 |  Codeforces Round # 185 Div II - agwの日記 を含むブックマーク はてなブックマーク -  Codeforces Round # 185 Div II - agwの日記  Codeforces Round # 185 Div II - agwの日記 のブックマークコメント

http://codeforces.com/contest/312

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

A. Whose sentence is it?

11:04 |  A. Whose sentence is it? - agwの日記 を含むブックマーク はてなブックマーク -  A. Whose sentence is it? - agwの日記  A. Whose sentence is it? - agwの日記 のブックマークコメント

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.
  • >>演算子による読み込みが終わった後にストリームの位置が同一行の改行文字の前で止るのが原因だ

f:id:agw:20130527190001p:image

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

f:id:agw:20130527190024p:image

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

f:id:agw:20130527190025p:image

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

f:id:agw:20130527190026p:image

  • 数値を読んだ後に、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ではこのような入力を想定しなくても良さそうだが、数値の直後に空白が入っているパターンだ

f:id:agw:20130527190043p:image

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

f:id:agw:20130527190044p:image

  • このような入力を想定しなければいけない場合は、以下のようにするのがベストプラクティスのようだ
  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()を活用すると便利
 |