AtCoderログ：0018 - ABC 082 B

問題：ABC 082 B - Two Anagrams (AtCoder に登録したら次にやること 第02問類題)

問題文

英小文字のみからなる文字列 $s, t$ が与えられます。 あなたは、$s$ の文字を好きな順に並べ替え、文字列 $s′$ を作ります。 また、$t$ の文字を好きな順に並べ替え、文字列 $t′$ を作ります。 このとき、辞書順で $s′<t′$ となるようにできるか判定してください。

制約

・$s,t$ の長さは $1$ 以上 $100$ 以下である。
・$s,t$ は英小文字のみからなる。

回答 (AC)

文字列 $s$ を好きに並べ替えた文字列 $s'$ と、文字列 $t$ を好きに並べ替えた文字列 $t'$ が $s'<t'$ となるには、$s'$ の最大値 (つまり文字列 $s$ を降順にソートした結果) よりも $t'$ の最小値 (つまり文字列 $t$ を昇順にソートした結果) が大きくなる必要があります。従って、文字列 $s,t$ を受け取り、$s$ を昇順にソートした結果と、$t$ を降順にソートした結果を比較すれば良いです。なお、文字列 s の昇順ソートは sort(s.begin(), s.rend()), 降順ソートは sort(s.rbegin(), s.rend()) とかけます。

abc082b.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s, t;
  cin >> s >> t;

  sort( s.begin(), s.end() );
  sort( t.rbegin(), t.rend() );
  if ( s<t ) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

誤回答 (WA)

最初、この問題を「文字列 $s$ を好きに並べ替えた文字列 $s$' に対し、文字列 $t$ を並べ替えて $s'<t'$ となる文字列 $t'$ を作れるか？」と誤解して、文字列 $s,t$ を昇順にソートした結果を比べていました。日本語を微妙に読み間違えたようでした...

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s, t;
  cin >> s >> t;

  sort( s.rbegin(), s.rend() );
  sort( t.rbegin(), t.rend() );
  if ( s<t ) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

調べたこと

AtCoder の解説 → コンテスト全体の解説

回答と同じ方針でした。

学んだこと

• 文字列のソート (昇順, 降順)

リンク

• 前の記事 → AtCoderログ：0017 - ABC 069 B