torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, SRM 621, Division 2, Level 1 : TwoWaysSorting

問題概要

 文字列をソートする際、文字列同士の比較には次の二種類が考えられる。

  • 辞書式順序で早い方を手前にする
  • 長さが短い方を手前にする

 長さが相異なる文字列の配列が与えられる。この配列がどちらの基準でソートされているか求めよ。なお、どちらにも当て嵌まる場合・どちらにも当て嵌まらない場合もその旨を示せ。

解法

 制約より、どちらの基準を用いても、結果の順序は一意に定まります。それぞれの基準について、与えられた配列がそれによるソート済み順序と一致するかを調べると、後は簡単な条件判定だけで解くことができます。
 実装についてですが、判定部分に std::is_sorted を用いると楽に書けます。デフォルトの比較ファンクタは辞書式順序ですが、第三引数にファンクタを渡せるので、ここに無名関数オブジェクトを渡すことでどちらにも使えます。

コード

#define ALL( c ) (c).begin(), (c).end()

class TwoWaysSorting
{
public:
	string sortingMethod( vector <string> stringList )
	{
		bool lex = is_sorted( ALL( stringList ) );
		bool len = is_sorted( ALL( stringList ), []( string &s, string &t ){ return s.size() < t.size(); } );

		if ( lex && len )
		{
			return "both";
		}
		else if ( !( lex || len ) )
		{
			return "none";
		}
		else if ( lex )
		{
			return "lexicographically";
		}
		else
		{
			return "lengths";
		}
	}
};