【問題1】 石の位置を●で表す。 ○○○○● ○○○●○ ○○○○○ ○○○○● ●●○○○  考え方:なるべく距離の長い配置を先に決定し、残り石で調整した。 【問題2】 (答え) (2つしかない解のうちの1つ) ●○○○○○ ○○○○●● ○○○●○○ ●○○○○○ ○○○○○○ ●○○○○○ 【おまけ1】 (答え) 5x5の解の数    35通り。ただし、鏡像解を別解としてカウントする場合は280通り。 (解法)   プログラムによる探索で全数を求めた。(プログラムは、最後に添付)   5x5の領域を2x3の4つの領域A,B,C,Dと中央に1x1のEの領域に分けて考える。2x3   の領域の中に配置された石の配置をもとめ、それを基に、5x5の領域の配置を求めた。 (2x3の領域に配置できる石の数は最大で3個である)      +---------+------+      |    |   |       | A  | B |       +-----+---+  | | | E | | | +---+------+       | C |   |      |   |  D  |       +-----+----------+ 【おまけ2】 (答え) 6x6の解の数    以下の2通り。ただし、鏡像解を別解としてカウントする場合は16通り。 ●○○○○○ ○○○○●● ○○○●○○ ●○○○○○ ○○○○○○ ●○○○○○ ○○○●○● ○○○○○○ ○●○○○○ ○○○○○● ●○○○○○ ●○○○○○ (解法)   プログラムによる探索で全数を求めた。(プログラムは、5x5と類似しているので割愛した)   6x6の領域を3x3の4つの領域A,B,C,Dに分けて考える。3x3の領域の中に配置された石の   配置をもとめ、それを基に、6x6の領域の配置を求めた。 (3x3の領域に配置できる石の数は最大で3個である)      +−−−+−−−+      |   |   |       | A | B |       |   |   |       +−−−+−−−+       |   |   |      | C | D |       |   |   |      +−−−+−−−+ --------5x5の配置を求めるプログラム------------------------------------------------------------ ##### 20004.04.18 # # Size = 5 def exe() : global Ans out = open("w5log.txt","w") M = Init(out) Ans = [] Total = 0 for E in range(0,2) : for A in range(3,1,-1) : for B in range(A,-1,-1) : for C in range(A,-1,-1) : if C > B : continue D = 5 - (A+B+C+E) if D < 0 : continue if D > A : break Cnt = Join(M,A,B,C,D,E,out) Total += Cnt WriteLog(out,"\n (%d,%d,%d,%d,%d) : %4d %4d" % (A,B,C,D,E,Cnt,Total)) out.close() ### def Init(out) : global BitMask BitMask = [1L] for i in range(1,34) : BitMask += [BitMask[i-1] << 1] M = [[],[],[],[]] for k in range(0,64) : b = Bits(k) if b > 3 : continue w = k p = 0 pos = [] while w != 0 : if w & 0x01 : pos += [[p%3,p/3]] w = w >> 1 p += 1 [m,pos2] = NormCheck(0,[],pos) if m == -1 : continue M[b] += [[k,pos]] # for i in range(0,4) : # WriteLog(out,"\n ==== %d ====" % (i)) # k = 0 # for e in M[i] : # k += 1 # Line = " %2d " % (k) # for pos in e[1] : # Line += " [%d,%d]" % (pos[0],pos[1]) # WriteLog(out,Line) return M ### def NormCheck(Mask,Pos,Pos2) : global BitMask pos = Pos + Pos2 m = Mask for i in range(len(Pos),len(pos)) : for j in range(0,i) : dx = pos[i][0] - pos[j][0] dy = pos[i][1] - pos[j][1] d2 = dx*dx + dy*dy if m & BitMask[d2] : return [-1,[]] m |= BitMask[d2] return [m,pos] ### def Join(M,A,B,C,D,E,out) : if E == 0 : me = 0L Pe = [] else : me = BitMask[2*5+2] Pe = [[2,2]] Cnt = 0 for [a,pa] in M[A] : [ma,Pa] = NormCheck(me,Pe,pa) for [b,pb] in M[B] : pb2 = Shift(pb,3,0,1) [mb,Pb] = NormCheck(ma,Pa,pb2) if mb == -1 : continue for [c,pc] in M[C] : pc2 = Shift(pc,0,2,1) [mc,Pc] = NormCheck(mb,Pb,pc2) if mc == -1 : continue for [d,pd] in M[D] : pd2 = Shift(pd,2,3,0) [md,Pd] = NormCheck(mc,Pc,pd2) if md == -1 : continue Cnt += DupCheck(Pd,out) return Cnt ### def Shift(Pos,dx,dy,t) : if Pos == [] : return [] pos = [] for [x,y] in Pos : if t == 0 : pos += [[x+dx,y+dy]] else : pos += [[y+dx,x+dy]] return pos ### def DupCheck(Pos,out) : global Ans,BitMask V = BitMask[33] for t in range(0,8) : pos = [] v = 0L for [x,y] in Pos : if t & 0x01 : x = 4-x if t & 0x02 : y = 4-y if t & 0x04 : w = x x = y y = w pos += [[x,y]] v |= BitMask[5*y+x] V = min(v,V) for ans in Ans : if ans == V : return 0 Ans += [V] printMap(out,len(Ans),V) return 1 ### def Bits(K) : w = K c = 0 while w != 0 : c += 1 w = w & (w-1) return c ### def printMap(out,Cnt,Map) : Line ="\n%4d " % (Cnt) WriteLog(out,Line) C = ["○","●"] map = Map for i in range(0,5) : Line = " " for j in range(0,5) : m = map & 0x01 map = map >> 1 Line += C[m] WriteLog(out,Line) ### def WriteLog(out,Line) : print Line out.write(Line+"\n") out.flush() --------終わり----------------------------------------------------------------------------------