技術的な課題：
あなたはN個の回転式時計を与えられます。
各時計にはMの針があり、これらの針は位置1、2、3、...、P（これらの数字は時計の表面を囲む数を表します）を指すことができます。時計はN行M列の整数行列Aで表されます。最初の行は最初の時計の針を表し、以下に続きます。
例えば、五つの行と二つの列をもつ行列Aを与えられ、P=4の場合：
<tt> A[0][0] = 1 A[0][1] = 2
A[1][0] = 2 A[1][1] = 4
A[2][0] = 4 A[2][1] = 3
A[3][0] = 2 A[3][1] = 3
A[4][0] = 1 A[4][1] = 3</tt>
時計を回転させることで、いくつかの時計が同じように見えることができます。例えば、第三、第四、第五の時計を回転させると、以下の時計を得ることができます：
回転後、四つの時計のペアが同じように見えます：(1,3)、(1,4)、(2,5)、(3,4)。
type TMatrix = array of array of longint;
以下の関数を記述します：
int solution(int **A, int N, int M, int P);
int solution(NSMutableArray *A, int P);
int solution(const vector< vector<int> > &A, int P);
class Solution { int solution(int[][] A, int P); }
class Solution { public int solution(int[][] A, int P); }
object Solution { def solution(A: Array[Array[Int]], P: Int): Int }
function solution(A, P);
function solution(A, P)
function solution($A, $P);
function solution(A: TMatrix; N: longint; M: longint; P: longint): longint;
def solution(A, P)
sub solution { my ($A, $P)=@_; my @A=@$A; ... }
def solution(a, p)
Private Function solution ( A As Integer()(), P As Integer ) as Integer
時計を回転させた後に同じように見える時計のペア数の最大値を返します。
例えば、以下の配列AとP=4を与えられた場合：
<tt> A[0][0] = 1 A[0][1] = 2
A[1][0] = 2 A[1][1] = 4
A[2][0] = 4 A[2][1] = 3
A[3][0] = 2 A[3][1] = 3
A[4][0] = 1 A[4][1] = 3</tt>
関数は4を返します、理由は上記にあるようにです。
前提条件：
- Nは1..500の範囲にある整数です；
- Mは1..500の範囲にある整数です；
- Pは1..1,000,000,000の範囲にある整数です；
- 行列Aの各要素は1..Pの範囲にある整数です；
- 行列Aの各行の要素はすべて異なります。
複雑さ：
- 最悪ケースの時間計算量はO(NMlog(M)+N*log(N))です；
- 最悪ケースの空間計算量はO(N*M)です。
以下が私の解決策です：
1 class Program
2 {
3 static void Main(string[] args)
4 {
5 int[][] Testcase = new int[][] { new int[] { 7, 16, 20, 24 }, new int[] { 5, 14, 18, 22 },
6 new int[] { 6, 7, 10, 15 }, new int[]{ 6, 7, 10, 15 },
7 new int[]{ 3, 7, 11, 18 }, new int[]{ 4, 8, 12, 19 } };
8 //結果は7であるべきです
9 Console.WriteLine(new Solution().solution(Testcase, 24));
10 }
11 }
12
13 class Solution
14 {
15 public int solution(int[][] A, int P)
16 {
17 int result = 0;
18 int hands = A[0].Length;
19
20 Dictionary<int[], int> buckets = new Dictionary<int[], int>();
21 buckets.Add (A[0],0);
22
23 //バケツを埋める
24 bool flgFind = false;
25 foreach(int[] oneClock in A)
26 {
27 flgFind = false;
28 foreach(int[] bucket in buckets.Keys)
29 {
30 if (CanbeRotatedToEqual(oneClock, bucket,P) == true)
31 {
32 buckets[bucket] += 1;
33 flgFind = true;
34 break;
35 }
36 }
37 if(flgFind == false)
38 buckets.Add(oneClock, 1);
39
40 }
41
42 //ペア数を計算する
43 foreach (int k in buckets.Values)
44 result += k * (k - 1) / 2;
45
46 return result;
47
48 }
49
50 bool CanbeRotatedToEqual(int[] source, int[] target, int P)
51 {
52 bool flgJ = false;
53 int hands = source.Length;
54 for (int i = 0; i < hands; i++)
55 {
56 int subValue = target[0] - source[i];
57
58 flgJ = false;
59 for (int j = 0; j < hands; j++)
60 {
61 int newS = source[(i + j) % hands] + subValue;
62 if (newS <= 0)
63 newS += P;
64 if (newS != target[j])
65 {
66 flgJ = true;
67 break;
68 }
69 }
70 //flgJがまだfalseの場合は、source時計がsubValueステップ回転後に、
71 //target時計と同じになることを意味します。
72 if (flgJ == false)
73 return true;
74 }
75 //このループが正常に終了した場合、source時計はtarget時計と同じになることができません。
76 return false;
77 }
78 }
2013/8/18: このバージョンは無効です。