文字列の同じ文字を含むか判定(ABCコンテスト063B問題)

#問題文
英小文字からなる文字列
Sが与えられます。Sに含まれる文字がすべて異なるか判定してください。

#制約
2≤|S|≤26, ここで|S|は Sの長さを表す。Sは英小文字のみからなる。

とある中で自分は

#include <iostream>
using std::string;
using std::cin;
using std::cout;

int main(){
  string s;
  cin >> s;
  
  int n=s.length();
  for (int i=0;i<n;++i){
    for (int j=i+1;j<n;++j){
      if (s[i]!=s[j]){
        cout << "yes"  << endl;
      }
      else {
        cout << "no" << endl;
      }
    }
  }
}

で提出したところWA(WrongAnswer)となってしまいました。解説PDFではfor文のまえにstring ans = "yes";を用意してs[i]==s[j]のときans="no"を出力しそれ以外のときans="yes"を出力していたのですが自分のやり方でWAになる原因がわかりません。原因がわかる方いらっしゃいましたら教えていただけると嬉しいです。よろしくお願い致します・

LouiS0616

2020/04/17 05:41

いきなり提出するのではなく、手元で試してみましたか。

yumetodo

2020/04/17 06:10

手元で実行してみればすぐに気がつくと思うんだよなぁ。

cunwe

2020/04/17 09:58

ブラウザで実行できるcpp.shというのに自分のソースコードを貼って実行してみたところmaisumakunさんがおっしゃるように何個もyesやnoが出てしまいましたがそれぞれの文の直後でreturn 0;の記述を追加したところ1回しか表示されなくなったので改善されたと思いそれを提出したところまたもやWAでした。。cpp.shで実行するとCE(Compile Error)は具体的な箇所が表示されるのですがWAは表示されないのでどこがダメかわからないものなのでしょうか？

Zuishin

2020/04/18 13:42 編集

どれか一つでも no なら no と出力しなければいけないわけですが、途中一回みつからなかっただけで yes と表示すると、最後までやったら no だった場合に間違いになります。

cunwe

2020/04/19 02:42

僕のコードですとそういった場合に対応していないのですね、ご指摘ありがとうございます。ということはcout << "yes" << endl;やcout << "no" << endl;をもう少し外に出すと良さそうですがそうすると今cout << "yes" << endl;を書いているところはどうしたらいいでしょうか？

Zuishin

2020/04/19 03:36 編集

回答が複数ついていますが、それではいけないんでしょうか。質問のアルゴリズムに一番近い方法なら、まずフラグ変数を用意し、同じ文字が見つかった時点でフラグを立ててループを終了するという方法がよく使われていました。ループを抜けた時に、フラグが立っていれば同じ文字が見つかった、立っていなければ見つかっていないということになるので、それによって出力を変えます。

cunwe

2020/04/19 08:00

boolでやるやつですか確かに過去にもやったことがあります、ありがとうございます。

行動規範の内容に同意します

回答3件

原因がわかる方いらっしゃいましたら教えていただけると嬉しいです。

ループを脱出する条件がないので、1つの文字列に対して何度もyesやnoを出力してしまいます。

投稿2020/04/17 06:20

maisumakun

総合スコア145183

僕ならこうするかな。

C++
1#include <iostream>
2#include <string>
3#include <set>
4
5int main(){
6  std::string s;
7  std::cin >> s;
8  // sを構成する全文字を"重複を許さない集合"に挿入し、要素数が変化したら重複がある
9  if ( std::set<char>(s.begin(), s.end()).size() == s.size() ) {
10    std::cout << "ぜんぶちがう"  << std::endl;
11  } else {
12    std::cout << "おなじもじがある"  << std::endl;
13  }
14}

投稿2020/04/19 00:02

episteme

総合スコア16614

cunwe

2020/04/19 02:43

setで今回の問題を解くとそこまでシンプルになるのですね、勉強になりましたありがとうございます。

行動規範の内容に同意します

ベストアンサー

それぞれの文の直後でreturn 0;の記述を

追加したところ1回しか表示されなくなったので改善されたと思いそれを提出したところまたもやWAでした。

そりゃまあそうでしょうね。まあ

「Sに含まれる文字がすべて異なる」という命題の逆がなにかを考えてみてください。そうすればループの継続条件がおのずからわかるでしょう。

まあしかし、それをして正しい答えは出るでしょうが、依然として問題が残ります。つまり、計算数が多すぎるということです。そこで活躍するのは投票(ヒストリグラム)という考え方です。一般にはstd::unorded_setを使う案件ですが、今回「Sは英小文字のみからなる」という制約がありますから、高々26種類しかないわけです。すると単なる配列を使って投票ができますね。まあ今回は最大でも26^2回の比較が26回に減るだけなのでそこまで実行時間に効いてこないかもしれないですが。

なんかstd::setを使っている回答を見たが、そんなものを使う必要はないと言ったはずである。

cpp
1#include <string>
2#include <iostream>
3int main()
4{
5    std::string input;
6    std::cin >> input;
7    bool found[26]{};
8    // 入力がASCII互換であると決め打ちする
9    for(auto c : input) {
10        if (found[c - 'a']){
11            std::cout << "no" << std::endl;
12            return 0;
13        }
14        found[c - 'a'] = true;
15    }
16    std::cout << "yes" << std::endl;
17}

https://atcoder.jp/contests/abc063/submissions/12063799

ちなみに上記コードでは入力される文字エンコードがASCII互換のようなa～zまで連続していると仮定しています。C++規格書では、0～9の文字エンコードの連続は保証されていますが、それ以外については保証がありません。競技プログラミングの文脈ではこの仮定はできるでしょうが、現実のコードで書いたらぶっ飛ばされるでしょう。つまり公平のために書くと、そういうportableなコードにするためにはstd::set/std::unorded_setを使うのは一つの選択肢です(殆どの文脈でstd::unorded_setはstd::setより優れています、今回の例では差がつかないかbucketのメモリ確保分だけstd::unorded_setのほうが遅いでしょうが)。

投稿2020/04/18 04:24

編集2020/04/19 04:35

yumetodo

総合スコア5850