Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-10-23STLのsortの計算量

STLのsortの計算量

| 22:55 | STLのsortの計算量 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - STLのsortの計算量 - SRM diary(Sigmar) STLのsortの計算量 - SRM diary(Sigmar) のブックマークコメント

STLで非常によく使用するsortというアルゴリズムがあるが、規格上は実装方法が規定されていないらしい。

何となくクイックソートで実装されてて計算量はO(n log n)なんだろうと勝手に思っていたが、よく考えるとクイックソートの最悪計算量はO(n^2)である。

これを突いてチャレンジ・・なんて聞いたことがないので多分大丈夫なんだろうと思ったが心配になったので調べてみた。

計算量が規定されていれば早いのだが規定を調査しきれなかったのでソースを調べてみた。


結論:Topcoder Arenaで使用するSTLのsortは平均計算量O(n log n)、最悪計算量O(n log n)である。

ついでにVC++2010も同様。


TopcoderのWeb FAQによると、gccについては以下のような環境とのこと。

General SRM Algorithm FAQ

Linux 2.6.9-55.0.12.ELsmp, gcc 4.0.2 (RedHat EL 4), glibc-2.3.2, and libstdc++-3.

gcc 4.0.2のソースをWebでダウンロード*1すると、libstdc++-3が付いてきたので、この中にあるstl_algo.hというファイルを見てみる。

(おそらくこいつがalgorithm関連のソースだろう)


stl_algo.h内のsort関数の実装は以下のようになっていた。

  template<typename _RandomAccessIterator>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	_ValueType;

      // concept requirements
      // アルゴリズムと関係ないので中略

      if (__first != __last)
	{
	  std::__introsort_loop(__first, __last, __lg(__last - __first) * 2);
	  std::__final_insertion_sort(__first, __last);
	}
    }

見るからにイントロソートしたあと挿入ソートする、と読める。

イントロソートというのは、最初はクイックソートするのだが再帰回数がリミットを超えるとヒープソートに切り替えるというものである。

ヒープソートは最悪・平均計算量ともにO(n log n)だが、実行上はループ内部の処理の多さからクイックソートに平均計算量で劣る。

しかし最悪計算量はクイックソートより良いので、良いとこ取りをしようということである。

ここではヒープソートに切り替えるリミット(再帰の深さ)を3つ目の引数でlog2(n)*2に指定している。

なおイントロソートしているのにその後挿入ソートをしているのは高速化のためである。

実はイントロソートの関数内では要素数がある閾値以下になると処理を終了するようになっている。

その結果イントロソート終了後は、ほとんどソートされた配列ができることになる。

ほとんどソートされた配列に対しては、挿入ソートが非常に高速に(クイックソートよりも速く!)働くのでこのような実装となっている(と想定される)。


イントロソートは以下のような実装になっている。

  template<typename _RandomAccessIterator, typename _Size>
    void
    __introsort_loop(_RandomAccessIterator __first,
		     _RandomAccessIterator __last,
		     _Size __depth_limit)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	_ValueType;

      while (__last - __first > int(_S_threshold))
	{
	  if (__depth_limit == 0)
	    {
	      std::partial_sort(__first, __last, __last);
	      return;
	    }
	  --__depth_limit;
	  _RandomAccessIterator __cut =
	    std::__unguarded_partition(__first, __last,
				       _ValueType(std::__median(*__first,
								*(__first
								  + (__last
								     - __first)
								  / 2),
								*(__last
								  - 1))));
	  std::__introsort_loop(__cut, __last, __depth_limit);
	  __last = __cut;
	}
    }

__depth_limitが0になるとpartial_sortを実行している。なぜpartial_sortをするのかというと単にここではpartial_sortをヒープソートで実装しているからである。

(partial_sortはヒープソートで実装すると効率がいい)

また、要素数が_S_threshold以下になるとイントロソートを終了する。_S_thresholdはstl_algo.h内で以下のように定義されている。

  enum { _S_threshold = 16 };

上記以外の場合、クイックソートを実行する。これは__unguarded_partitionで実現されている。(クイックソートのpartition操作にあたる)


partial_sortは以下のようになっている。

  template<typename _RandomAccessIterator>
    void
    partial_sort(_RandomAccessIterator __first,
		 _RandomAccessIterator __middle,
		 _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	_ValueType;

      // concept requirements
      // アルゴリズムと関係ないので中略

      std::make_heap(__first, __middle);
      for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
	if (*__i < *__first)
	  std::__pop_heap(__first, __middle, __i, _ValueType(*__i));
      std::sort_heap(__first, __middle);
    }

見ての通りヒープソートのようである。


ということでSTLのsortは最悪時でも高速そうだということが分かったので安心した。


ついでに普段ローカルで使用しているVC++2010についても調べてみた。

(インストールするとSTLのソースが付いてきます)

書き方やパラメータは多少異なるが考え方は同じで、イントロソート+挿入ソートで書かれていた。

以上から類推するに、sortの実装はイントロソート+挿入ソートが一般的に効率的な手法なんでしょうね。

*1:Red Hatのglibcは色々バグ修正などがバックポートされていたりするので正確にはコミュニティ版とは異なるところもありますが、アルゴリズムに大きな違いはないだろうと思うので今回はコミュニティ版で確認しています。正確を期すなら、RedHatからSRPMをダウンロードする必要があります。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111023

2011-09-25KISSの原則 その3

KISSの原則 その3

| 22:27 | KISSの原則 その3 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - KISSの原則 その3 - SRM diary(Sigmar) KISSの原則 その3 - SRM diary(Sigmar) のブックマークコメント

の続き。考え方をシンプルにすることで楽に解くための考察。


少し趣向を変えますがコーディング時間を短くする工夫について。


SRM421 Div2 1000 FloorIndicator

Problem Statement

1階から10^N-1階までの階があるビルがある。エレベータ内の階の表示は丁度N桁の数で表される。(0で始まる表示でも良い)

各数字は5×3のランプで表示される。0~9の表示を以下に示す。(#が点灯)

###...#.###.###.#.#.###.###.###.###.###
#.#...#...#...#.#.#.#...#.....#.#.#.#.#
#.#...#.###.###.###.###.###...#.###.###
#.#...#.#.....#...#...#.#.#...#.#.#...#
###...#.###.###...#.###.###...#.###.###

数字の境界は1列の消灯ランプで表される。

なお、いくつかのランプが壊れており、常に消灯されている。(どれが壊れているか分からない)

あるランプ表示のパターンが与えられるので、可能性のある全ての階の平均を取ったものがいくつになるか答えよ。

可能な階が一つもない場合は-1を返せ。

double averageFloor(int N, vector <string> indicator);

1<=N<=9

indicator.size()=5

indicatorの要素は4*N-1文字

indicatorの要素は'#'と'.'のみで構成される

indicatorの中で各数字の区切り線となるはずの列の要素は全て'.'


indicatorの例は以下のようなの。

{"###.###",
 "#.#.#.#",
 "#.#.###",
 "#.#...#",
 "###.###"}

この場合、1文字目は0もしくは8、2文字目は9もしくは8となる。

解は09,08,89,88の平均を取って48.5


以下、僕の考える解答例です。


解法自体は比較的ストレートフォワード。

各数字を表す3*5のランプがどの数字となりうるかを調べる。

つまり、0~9を表すパターンに対して、indicatorが'#'となっているところが全て'#'であればその数字となりうる。

逆に言えば、indicatorが'#'で、数字パターンが'.'であるところが一つでもあれば、その数字にはならない。

各桁は独立に考えられるので、各桁の平均値を取って足し合わせれば良い。

候補となる数字が1つもない桁があれば、解は-1になる。


では何が大変かというと、実は数字のパターンを作るのが一番面倒な気がします。

手動で作ると、それだけでかなり時間を食います。やってみてください。

各行について、3文字分ずつコピーして、貼りつけて、コピーして、貼りつけて、・・・、1数字につき5行で10数字分、合計50回もコピペしていられません。

(AA用エディタを使えば長方形領域をコピーできるので10回で済みますが・・・)

問題文に与えられた文字列をそのまま使うのが楽だと思います。

文字列の整形は人間でなく機械にやらせるということです。


ということで、以下ソースコード例です。

Topcoderでは仮引数名を勝手に変えても問題ないのでindicatorはindに変えてます。


class FloorIndicator {
public:
	double averageFloor(int N, vector <string> ind) {
		double res=0;
		vector <vector <string> > dig(10, vector <string>(5));
		string org[5]={
			"###...#.###.###.#.#.###.###.###.###.###", 
			"#.#...#...#...#.#.#.#...#.....#.#.#.#.#",
			"#.#...#.###.###.###.###.###...#.###.###", 
			"#.#...#.#.....#...#...#.#.#...#.#.#...#", 
			"###...#.###.###...#.###.###...#.###.###"
		};
		
		//数字パターンのparse
		//dig[j]に数字jの3*5のパターンを格納する
		for(int i=0; i<5; i++) {
			int idx=0;
			for(int j=0; j<10; j++) {
				for(int k=0; k<3; k++) {
					dig[j][i].push_back(org[i][idx]);
					idx++;
				}
				idx++;
			}
		}

		//各桁について候補として可能な数字をcandに格納
		vector <vector <int> > cand(N);
		for(int i=0; i<N; i++) {
			for(int j=0; j<10; j++) {
				bool ok=true;
				for(int k=0; k<5; k++) {
					for(int l=0; l<3; l++) {
						if(ind[k][i*4+l]=='#' && dig[j][k][l]=='.') {
							ok=false;
							break;
						}
					}
				}
				if(ok) cand[i].push_back(j);
			}
		}

		//candから各桁の平均を算出し、解を出す
		res=0;
		for(int i=0; i<N; i++) {
			if(cand[i].empty()) return -1;
			double sum=accumulate(cand[i].begin(), cand[i].end(), 0);
			double ave=sum/cand[i].size();
			res*=10;
			res+=ave;
		}
		return res;
	}
};

ところでこのプログラム、書いてから思いましたがすごく勿体無いことをしています。

indicatorのparseと、問題文で与えられる数字のパターンのparseは本質的に同じことをしているはずなのに、違うコードを書いています。

同じことをするプログラムは関数化して再利用すべきですね。

逆に言うと、この問題を見たときに、同じparseのプログラムが使えることに気づかなければならないんだと思います。そうすれば、そもそも数字パターンを手動入力しようなどとは思わないでしょう。


結構、こういう文字列パターンが問題文で与えられる問題はあります。

手動でパターンを分解したりすると意外と大変だったりするので、こういうテクニックが役立つときがあります。


  • 文字列等の整形はなるべくプログラムでやる。

 手動でやるよりはるかに早い場合があります。


続きがあるかも

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110925

2011-09-02KISSの原則 その2

KISSの原則 その2

| 17:45 | KISSの原則 その2 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - KISSの原則 その2 - SRM diary(Sigmar) KISSの原則 その2 - SRM diary(Sigmar) のブックマークコメント

の続き。考え方をシンプルにすることで楽に解くための考察。


突然ですが、以下のような問題について、どう解くべきでしょうか?


SRM481 Div1 250 ChickenOracle

Problem Statement

卵が先か、鶏が先か?どちらが先に存在したのか、神様に聞くことにした。

ところが神様はこれまでn人に対してその回答をしたので、答えを教えてくれない。

しかも、n人のうちlieCount人に対しては嘘の回答をしたとのこと。

そのn人に尋ねたところ、eggCount人は卵が先だと言い、n-eggCount人は鶏が先だと言う。

しかし、n人のうちliarCount人は嘘を付いているらしい。

以上の状況で、真実が導き出せるだろうか?

この問題を解く以下の関数を書くこと。

string theTruth(int n, int eggCount, int lieCount, int liarCount);

真実が導き出せて、卵が先なら"The egg"、鶏が先なら"The chicken"を返せ。

両方の解があり得るなら、"Ambiguous"、両方あり得ないなら、"The oracle is a lie"を返せ。

制約条件は以下の通り。

1<=n<=1000000

0<=eggCount, lieCount, liarCount<=n


以下、僕の考える解答例です。


場合分け解法

ある意味数学的に解くという方法。コンピュータの力(高速で正確な計算)を使わない。

前回と同じですが、この問題を場合分けで解くと、非常に難しいコーナーケースが発生します。

私はお勧めしません。


探索による解法

もし嘘を付いている人が一人もいなかったらどうでしょうか?

chickenCount:=n-eggCountとおくと、

当然、eggCount==lieCountなら答えは"The chicken"、chickenCount==lieCountなら"The egg"、それ以外なら"The oracle is a lie"となります。

ただし、eggCount==chickenCount==lieCountの場合のみ"Ambiguous"となります。

これは自明だと思います。

ここで、eggCountのうちi人が嘘を付いているとすると、chickenCountのうちliarCount-i人が嘘を付いていることになります。

iを決めてやると、嘘を付いている人の数だけeggCountを増減させてやれば良いです。

eggCount:=eggCount-i+(liarCount-i)

ただし、0<=i<=eggCount、0<=liarCount-i<=chickenCount

これが分かれば、探索で解けますね!!


ということで、以下ソースコード例です。


class ChickenOracle {
public:
	string theTruth(int n, int eggCount, int lieCount, int liarCount) {
		int chickenCount=n-eggCount;

		bool egg=false, chicken=false;
		for(int i=0; i<=eggCount; i++) {
			if(liarCount-i<0 || liarCount-i>chickenCount) continue;

			int neweggCount=eggCount-i+(liarCount-i);
			int newchickenCount=n-neweggCount;

			if(neweggCount==lieCount) chicken=true;
			if(newchickenCount==lieCount) egg=true;
		}

		string res;
		if(egg&&chicken) res="Ambiguous";
		else if(egg&&!chicken) res="The egg";
		else if(!egg&&chicken) res="The chicken";
		else if(!egg&&!chicken) res="The oracle is a lie";

		return res;
	}
};

結局今回も言いたいことは、コンピュータ君の得意技である探索を利用しようということです。

意外と探索できなさそうでも探索で楽になることって多いし、僕は何をおいてもまず単純に探索できないか考えます。

単純化のための第一の方法は、とにかくまずは探索を考えてみることであると思います。

ただし、単に探索できそうでできないこともあるので、計算量の見極めは必要です!何が何でも探索ではないので!


  • なるべく場合分けしない。探索で解決できるなら探索する。

 コンピュータが得意な探索を使えば、難しく考える必要がなくなる場合があります。


続きがあるかも

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110902

2011-08-27KISSの原則

KISSの原則

| 14:34 | KISSの原則 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - KISSの原則 - SRM diary(Sigmar) KISSの原則 - SRM diary(Sigmar) のブックマークコメント

KISSの原則といって、プログラムは単純であることが望ましいと言われるが、基本的に大賛成である。

確かに、コンテストにおいても工夫することでよりシンプルな考え方で解けるものや、考え方によってコーディングがシンプルになる問題がある。

特に、場合分けが多くコーナーケースでWAしそうな場合や、コーディングが大量・複雑になるような場合には、何かしら単純化を図ったほうがいいことが多いと思う。

しかしこれがなかなか難しくて、単純化する方法に容易には気づかないことが多い。

苦労して解いたあとに他人のコードを見て、こんな簡単にできたんだ、みたいに思うこともしばしばある。

ということで、過去に解いた問題を振り返りながら、どうすれば問題を単純化できるのか、色々考えてみたい。


とりあえずは分かりやすい例として、以下考え方によって解くのが楽になる問題の一例です。


Codeforces 78 Div1 A.Help Victoria the Wise

Problem Statement

6面のサイコロがある。1面につき1つgemを取り付けることができる。gemが6つ渡されるので、取り付け方が何通りあるか答えよ。

ただし、gemはまったく同一のものが複数渡される可能性があり、回転して同一になるつけ方は同じ取り付け方とみなす。

gemの種類は最大6種類。

gemの種類は6文字の文字列で与えられる。同じ文字は同一のgem。

例:入力=BOOOOB、解=2

制約:1問2秒以内


数学的に解けそうですが、これはプログラミングコンテストの問題であるというところが1つのポイントです。


以下、僕の考える解答例です。


場合分け解法

ある意味数学的に解くという方法。コンピュータの力(高速で正確な計算)を使わない。

プログラミングコンテストに慣れていない場合、この方法で解くことをまず考えるのではないでしょうか。

つまり、gemの種類と数についてあり得るパターンを全て列挙し、それらについて注意深く検討し、場合分けで解答をするという方法です。

この方法でももちろん解けますが、あり得るパターンの列挙及び各パターンの組み合わせ数を検討することは非常に難しいと思います。

おそらく検討には相当時間を要するだろうし、コーナーケースでWAを出す可能性が非常に高くなるでしょう。


探索による解法

サイコロの各面に0~5のindexをつけて、各indexに対応するgemを1文字で表すことで、6文字の文字列でgemのつけ方を表現します。

そして、gemの全ての取り付け方を探索するため、その文字列の全ての並べ方を列挙します。

さらに、各並べ方を回転させた場合に、これまでにその並べ方が登場していないか調べ、登場していない場合のみ解に加算します。

回転は文字列の要素の入れ替えで表現できるので、それほど難しいものではないです。

こちらの解答のほうが早く書けると思います。また、回転の方法さえ正しく書ければ、間違った解答を返すことはほぼないと思います。

もちろん、プログラムの実行時間はこちらのほうがはるかに遅いです。しかし、制約の2秒を超えることはありません。また、その代わりとして、コーディング時間の短縮化と正確性の向上が図れるのです。


以下のソースコードは僕が実際に本番で提出したものです。

変数名があまり実態を表してませんがご容赦ください。


int main() {
	//デバッグ用にfin,foutを定義しているがcin,coutをそのまま使用してOK
	istream &fin=cin;
	ostream &fout=cout;
	
	//回転その1。どの面を最初の要素に持ってくるかという考え方で回転する。
	int perm[6][6]={{0,1,2,3,4,5},{1,0,4,5,2,3},{2,0,1,5,3,4},{3,0,2,5,4,1},{4,0,3,5,1,2},{5,4,3,2,1,0}};
	//回転その2。最初の要素が表す面とその対面を軸として回転する。
	int rot[4][6]={{0,1,2,3,4,5},{0,2,3,4,1,5},{0,3,4,1,2,5},{0,4,1,2,3,5}};

	string s;
	fin >> s;

	sort(s.begin(), s.end());
	set <string> all;
	int res=0;
	do {
		bool ok=true;
		for(int i=0; i<6; i++) {
			string t=s;
			for(int j=0; j<6; j++) t[j]=s[perm[i][j]];
			for(int j=0; j<4; j++) {
				string t2=t;
				for(int k=0; k<6; k++) t2[k]=t[rot[j][k]];
				if(all.count(t2)) {
					ok=false;
					break;
				}
			}
			if(!ok) break;
		}
		if(ok) {
			res++;
			all.insert(s);
		}
	} while(next_permutation(s.begin(), s.end()));

	fout << res << endl;
	
}

自分で書いておいて何ですが、このコードは、改良の余地があると思います。

回転の種類を合計10種も書いていますが、実際は2種で十分だと思います。2種にすると、コーディング時間はもっと短くなりそう。


今回のポイントは、以下の点です。

  • なるべく場合分けしない。探索で解決できるなら探索する。

  コンピュータが得意な探索を使えば、難しく考える必要がなくなる場合があります。

  • 対称性のある図形の問題は、回転/反転等の操作を利用する。

  回転/反転等の操作を施すと、同じコードを使いまわせます。


以上ですがまた続きを書くかも

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110827

2010-08-04SRM478 Div1

ビットによる部分集合の列挙

| 01:02 | ビットによる部分集合の列挙 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - ビットによる部分集合の列挙 - SRM diary(Sigmar) ビットによる部分集合の列挙 - SRM diary(Sigmar) のブックマークコメント

SRM478 Div1 500のように、ビットDPを使うときなどに、ある集合(maskとする)の全ての部分集合を列挙したい場合があります。

(maskは整数値、maskのビット数はn、maskのビットのうち1が立っているところをmaskが表す集合の要素とみなします。また、maskの部分集合をiで表します。)

この場合、iを0から2^n-1まで全部列挙してmaskの部分集合となっている場合のみ評価するというやり方だと、計算量が多くなってしまうので、ビット論理積とデクリメントを使って本当にmaskの部分集合のみを列挙する方法があります。

ただしこの方法は気をつけないと無限ループになったり注意が必要なので少しまとめておきたいと思います。


例えば、mask=100101とすると、その部分集合である000000, 000001, 000100, 000101, 100000, 100001, 100100, 100101を列挙するのが今回の目的です。


何となくのやり方は、TopcoderのAlgorithm TutorialのAll the subsetsの欄を見てください。


1. maskの部分集合を列挙する

	a. i==0を評価しない
		for(int i=mask; i>0; i=(i-1)&mask) {
		}
	b. i==0を評価する
		for(int i=mask; i>=0; i--) {
			i&=mask;
		}

i==0を評価する(for文の継続条件をi>=0とする)とき、1.aのようにfor文の更新文の中でmaskとビット論理積を取ると、いつまで経ってもiが負の値にならず、無限ループします。

また、i==0を評価しない(for文の継続条件をi>0とする)場合、1.bのようにfor文の次の文でmaskとビット論理積をとると、i==0を評価してしまい意図した結果になりません。(1.aの書き方にするなり、break文を入れるなりしましょう)


2. maskを含む集合を列挙する

少し目的は変わりますが同じようなやり方でできる処理が、maskを含む集合の列挙です。

	for(int i=mask; i<(1<<n); i=(i+1)|mask) {
	}

なお初期値をmaskでなく0にすると、i==maskの値を評価できない場合があるため避けたほうが良いと思います。


1.aを用いたビットDP(メモ化)の例(擬似コード)です。

int memo[1<<n];
int rec(int mask) {
	int res=init;
	if(mask==0) return init;
	if(memo[mask]>=0) return memo[mask];
	for(int i=mask; i>0; i=(i-1)&mask) {
		res=best(res, calc(rec(mask^i), i));
	}
	memo[mask]=res;
	return res;
}

このようなDPの場合、計算量はmaskのビットが1のときのみiのビットを0か1から選ぶため、ビット単位で考えると(mask:0,i:0), (mask:1,i:0), (mask:1,i:1)の3通りをビット数分累乗したパターンの計算で3^nの計算量となります。


誤り等ありましたらご指摘くださいませ。

ElizaFerrerElizaFerrer2018/11/20 05:13AIやコグニティブ・コンピューティングを利用する場合、その最終的な目標は、機械が画像・音声解釈機能で人間のプロセスをシミュレートし、人間と理路整然と会話できるようにすることです。 <a href=https://jamedbook.com/12-8/>https://jamedbook.com/12-8/</a> ぬれたタオルやトイレの便座などからも感染することがあります。 女性の場合、外陰部にかゆみや灼熱感があったり、おりものが増えたりします。