crossing.c

問題はこちら
http://nabetani.sakura.ne.jp/hena/ord14crosscircle/

他の解答例はこちら
http://qiita.com/Nabetani/items/66806c9dc14a96f2fd42

＊＊＊　aabbca1bcbのときを例に解説　＊＊＊
＜概要＞
このコードは、円周上に並んだ点aabbca1bcbに1本ずつ線を引いていき、
その線を引いた時に交差した線の本数を積算しています。

＜流れ＞
最初は、円周上にaabbca1bcbと点が並んでいるだけで、線は一本も引かれていない状態です。

まず先頭のaから線を引きます。2番目のaと6番目のaに線が１本ずつ引けるので、それぞれのLineCntをカウントアップします。この２本の線を引いたときには1本も線を交差しないので、交点の数pは0のまま。

次に2番目のaから線を引きます。6番目のaに線が1本引けるので、6番目のaのLineCntをカウントアップします。この線を引いた時も1本も線を交差しないので、交点の数pは0のまま。

次に3番目のbから線を引きます。4番目、8番目、10番目のbに線が引けるので、それぞれのLineCntをカウントアップします。8番目と10番目の線を引くときに、6番目のaの線２本と交差するので、pは4となります。

この作業を最後の文字まで繰り返せば、すべての交点の数を数えることができます。

#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int c[100];
} LineCnt;

int solve(const char *in)
{
	LineCnt l={0}, t={0};
	int i, j, p=0, tp=0;

	for(i=0; in[i]!='\0'; i++, l=t, tp=0) {
		for(j=i+1; in[j]!='\0'; j++) {
			if(in[j]==in[i]) {
				t.c[j]++;
				p+=tp;
			}
			tp += l.c[j];
		}
	}
	return p;
}

void test(const char *in, const char *a)
{
	int r = solve(in);
	printf("%d\t%s\n", r, (r==atoi(a)) ? "ok": "***NG***");
}

int main()
{
/*0*/ test( "aabbca1bcb", "14" );    
/*1*/ test( "111ZZZ", "0" );    
/*2*/ test( "v", "0" );    
/*3*/ test( "ww", "0" );    
/*4*/ test( "xxx", "0" );    
/*5*/ test( "yyyy", "1" );    
/*6*/ test( "zzzzz", "5" );    
/*7*/ test( "abcdef", "0" );    
/*8*/ test( "abcaef", "0" );    
/*9*/ test( "abbaee", "0" );    
/*10*/ test( "abcacb", "2" );    
/*11*/ test( "abcabc", "3" );    
/*12*/ test( "abcdabcd", "6" );    
/*13*/ test( "abcadeabcade", "23" );    
/*14*/ test( "abcdeedcba", "0" );    
/*15*/ test( "abcdeaedcba", "8" );    
/*16*/ test( "abcdeaedcbad", "16" );    
/*17*/ test( "QQQQXXXX", "2" );    
/*18*/ test( "QwQQmQXmXXwX", "14" );    
/*19*/ test( "111222333", "0" );    
/*20*/ test( "aaAAaA", "4" );    
/*21*/ test( "121232313", "12" );    
/*22*/ test( "1ab1b", "1" );    
/*23*/ test( "abcdefbadcfe", "12" );    
/*24*/ test( "abxcdefbadcfex", "14" );    
/*25*/ test( "dtnwtkt", "0" );    
/*26*/ test( "mvubvpp", "0" );    
/*27*/ test( "moggscd", "0" );    
/*28*/ test( "kzkjzpkw", "2" );    
/*29*/ test( "fbifybre", "1" );    
/*30*/ test( "rrrfjryki", "1" );    
/*31*/ test( "wrbbdwsdwtx", "2" );    
/*32*/ test( "vvucugvxbvgx", "9" );    
/*33*/ test( "ojkjzyasjwbfjj", "5" );    
/*34*/ test( "ggffyuxnkyypifff", "5" );    
/*35*/ test( "vcgtcqlwrepwvkkogl", "4" );    
/*36*/ test( "xeqtmmgppwcjpcisogxbs", "4" );    
/*37*/ test( "lukltpeucrqfvcupnpxwmoj", "6" );    
/*38*/ test( "zpzswlkkoqwwndwpfdpkhtzgtn", "31" );    
/*39*/ test( "bkfeflagfvluelududqjcvfyvytfw", "45" );    
/*40*/ test( "rvqbhfmcjjqlpqzulzerxgyowiwrfkmhw", "26" );    
/*41*/ test( "qyxvpdtoeexbqsethwjwmqszcxxjnsdoeaet", "144" );    
/*42*/ test( "rjmsgmswhcolmpbhmpncziymydyalrcnevsrespj", "133" );    
/*43*/ test( "oxetnyjzjbysnwktfwzndlejfndsqeetsnjvsicyjehd", "395" );    
/*44*/ test( "wzvddnddzogywcqxbyvagbzmsmtcmrrlbnebmvhaemjouaqim", "219" );    
/*45*/ test( "karhphxcxqgsyorhusbumbqzocuzvnwzwcpxgsksrviihxrgsrhji", "461" );    
/*46*/ test( "oxgbononhqdxzmkysgijwvxljpaazmgkurkpffeuwywwuyxhyfkicgyzyc", "441" );    
/*47*/ test( "sdgsrddwsrwqthhdvhrjhgtxwgurgyiygtktgtughtogzaqmcafkljgpniddsvb", "1077" );    
/*48*/ test( "qemhecchkgzhxmdcsltwhpoyhkapckkkzosmklcvzkiiucrvzzznmhjfcdumuflavxik", "1711" );    
/*49*/ test( "ffqmsirwpxrzfkbvmmfeptkbhnrvfcywthkwkbycmayhhkgvuyecbwwofwthlmzruphrcujwhr", "2440" );
	return 0;
}