SRM566 Div1 Easy "PenguinSledding"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12336
訳
パーシーはペンギン界最大の娯楽、ペンギンソリ滑りの運営を担当している。
パーシーの仕事はそのコースの設計を手伝う事である。
パーシーはとても用心深いペンギンで、
コースの経路を交差させないようにしたいと考えている。
コースはチェックポイントと呼ばれる重要な地点と、いくつかの経路で構成されている。
チェックポイントは1~numCheckpointsの番号が振られている。
経路は2つの異なるチェックポイントを結んだ線分である。
チェックポイントは互いに異なる地点にあり、任意の3つのポイントが、
一直線上に並ぶ事は無い。
コースを設計するとき、パーシーはいくつかのチェックポイントのペアを、
経路として指定する。
2つの経路が交差するとアクシデントが起こるので、
そのような設計は避けなければならない。
残念ながら、パーシーは全てのチェックポイントについて、
正確な位置を把握していなかった。
したがってパーシーの設計は、チェックポイントがどこにあろうが、
経路が交差しないようにしなくてはならない。
パーシーは、経路が交差しないような設計を"safeな設計"と呼んでいる。
パーシーはunsafeであろう既存の設計を見つけた。
彼はこの古い設計から0以上の経路を取り除き、safeな設計に変更しようと考えている。
古い設計から得る事の出来る全てのsafeな設計の数を数えよ。
2つの設計において、片方は経路として繋がっているが、
もう片方は繋がっていないようなチェックポイントのペアが存在すれば、
それは違う設計とみなされる。
あなたは古い設計における、チェックポイントの数を表すnumCheckpointsが与えられる。
また、どのチェックポイントのペアを使って経路が出来ているかを意味する
checkpoint1 checkpoint2が与えられる。
古い設計から作ることができる、sefeな設計の数を返せ。
制約
2 <= numCheckpoints <= 50
考えた事
safeな設計を分類すると、
・まったく経路をおかない(もはや設計とはいわないような)
・ひとつだけ経路を置く
・あるチェックポイントを中心に、ウニみたいにする。
・トライアングルみたく3つ経路を置く
の4パターンなので、それぞれ数えていく。
ソースコード
class PenguinSledding { public: long long countDesigns(int numCheckpoints, vector <int> checkpoint1, vector <int> checkpoint2){ int N = numCheckpoints; int M = checkpoint1.size(); bool G[55][55]; memset( G, false, sizeof(G) ); for( int i = 0; i < M; i++ ){ int a = checkpoint1[i]; int b = checkpoint2[i]; G[a][b] = G[b][a] = true; } long long res = 0; // 1 - 2 - 3 for( int i = 1; i <= N; i++ ){ int cnt = 0; for( int j = 1; j <= N; j++ ){ if( G[i][j] ) cnt++; } if( cnt >= 2 ){ long long add = 1; for( int t = 0; t < cnt; t++ ){ add *= 2; } add = add - cnt - 1; res += add; } } // 1 - 2 - 3 - 1 for( int i = 1; i <= N; i++ ){ for( int j = i + 1; j <= N; j++ ){ for( int k = j + 1; k <= N; k++ ){ if( G[i][j] && G[j][k] && G[k][i] ){ res++; } } } } // 1 - 2 for( int i = 1; i <= N; i++ ){ for( int j = i+ 1; j <= N; j++ ){ if( G[i][j] ){ res++; } } } // 1 res++; return res; } };