Kawazoe(@riverplus)さんのCodeIqの問題です。
問題とテストケースはこちらにお世話になりました。解答もあります。
https://blog.goo.ne.jp/r-de-r/e/527402ab150700766b0a3341f8879816
こちらにも情報があります。
https://togetter.com/li/1174396
水平・垂直・傾き45度の線分の数は初期値として設定します。
その他の線分を直角三角形の斜辺と考え、縦横の長さが互いに素になる線分のうち、
両端から二倍に延長した点がともに正方形内に無いものを選びます。
場合分けが面倒そうなので全探索にしたらあっさりとけました。
Juliaで書きました。
j,iは左端,下端からの距離、dj,diは左下から右上に向かう線分の横,縦の長さ。
0<di<dj<nとします。
線分の右端,上端が正方形内に無いといけませんので、j<=n-dj,i<=n-diです。
線分の左側または下側の延長が正方形内に無い条件がj<=djまたはi<=diです。
線分の右側または上側の延長が正方形内に無い条件がj+2*dj>nまたはi+2*di>nです。
線分の傾きが4通りあるのでそれぞれ4倍します。
#julia ver 1.41,1.53,1.10.3
function f27(n,a)
function solve(n)
sum= n==2 ? 6 : 4 #di=dj(=1),di=0(dj=1),dj=0(di=1)
for dj in 2:n-1,di in 1:dj-1,j in 1:n-dj,i in 1:n-di
if gcd(di,dj)==1 && (j <= dj || i <= di) && (i+2*di> n || j+2*dj > n)
sum+=4 #(右上がりの直線でdi<dj)*4
end
end
return sum
end
x=solve(n)
s = a == x ? "ok " : "no "
println(s,x)
end
f27(2 ,6)
f27(3 ,12)
f27(4 ,48)
f27(5 ,108)
f27(6 ,248)
f27(7 ,428)
f27(8 ,764)
f27(9 ,1196)
f27(10 ,1900)
f27(13,5244)
f27(27, 98492)
f27(38, 388212)
f27(40, 475068)
場合分けでも解きました。Prologです。
J,Iは左下から右上に向かう線分の横、縦の長さ、Nはn-1とし、
左下から右上に伸びる線分の左下の点を基準として考えます。
0<I<N,I<J<=Nとします。（1<J<=N,0<=I<JとしてIをまとめて計算しても大差なし）
①横方向どちら側でも二倍に延長すると範囲外(2*J>N)
②延長したとき少なくとも片側は範囲外(3*J>N>=2*J)
③どちらかの側あるいは両側二倍に延長しても範囲内（3*J<=N）
となる場合に分け
①の場合では右からJ-1、上からI-1の範囲は長さが足りないので除きます。
②の場合右からJ-1の範囲は長さが足りないので除きます。
左からN-2*JとJの間（J-(N-2*J)=3*J-N）は両側とも二倍に延長すると範囲外ですので、
上からI-1の範囲を除いて追加(R2)します。
左からJ以上N-J以下((N-J)-J=N-2*J)は左側二倍に延長すると範囲内ですが、
下端からIまでは線分の上端から正方形の下端までの縦の長さが2*I未満ですので
追加します。
また右から2J以上（左からN-2J以下）では右側二倍に延長すると範囲内ですが、
上端から2*I以上Iまでは線分の下端から正方形の上端までの長さが2*I未満ですので
追加します(合わせてR3)。
③の場合、左側がJ以下で上側の空きがI以下の場合と
右側の空きがJ以下で下側がI以下の位置の線分の数を数えます。
（I<Jなので線分の左右ともJ以上あいている場合は不適合）
線分の傾きが4通りあるのでそれぞれ4倍します。
%SWI-Prolog ver 7.42,7.64
%:-initialization(start). %ideone
%start.
loop272(N,_,J,R,R):-J =:= N.
loop272(N,I,J,R1,R):-
gcd(I,J) =\= 1,!,J1 is J+1,loop272(N,I,J1,R1,R).
loop272(N,I,J,R1,R):-
J*2 > N-1,!, %両側どちらも二倍に延長すると範囲外
R2 is (N-J)*(N-I)*4,R3 is R1+R2,J1 is J+1,loop272(N,I,J1,R3,R).
loop272(N,I,J,R1,R):-
J*3 > N-1,!, %延長したとき悪くても片側は範囲外
R2 is (3*J-N)*(N-I)*4, %両側とも範囲外 % n-2*j < x < j
R3 is (N-2*J)*I*2*4, %片側が範囲内になる場合-> 正方形の端で上の場合以外
R4 is R1+R2+R3,J1 is J+1,loop272(N,I,J1,R4,R).
loop272(N,I,J,R1,R):- %どちらかの側あるいは両側二倍に延長しても範囲内
R2 is R1+I*J*2*4, %片側が範囲外になる場合のみ計算->正方形の端(n-i~n-2i)のみ
J1 is J+1,loop272(N,I,J1,R2,R).
loop271(N,N,R,R).
loop271(N,I,R1,R):-J is I+1,loop272(N,I,J,R1,R2),I1 is I+1,loop271(N,I1,R2,R).
fn27(2,6):-!. % n=2の時
fn27(N,R):-N1 is N-1,loop271(N,1,4,R),!. % 4->I=J(=1)の数
solve27(N,A):-(fn27(N,R)->(R=:=A->Str=" ok ";Str=" no ");
write(fail)),write(" "),write(Str),writeln(R),!.
start:-f27(N,A),solve27(N,A),fail.
start.
f27(2 ,6).
f27(3 ,12).
f27(4 ,48).
f27(5 ,108).
f27(6 ,248).
f27(7 ,428).
f27(8 ,764).
f27(9 ,1196).
f27(10 ,1900).
f27(13,5244).
f27(27, 98492).
f27(38, 388212).
f27(40, 475068).
全体の数から交点が3以上になるものを引いた方が簡潔かとも思いましたが
うまくいきませんでした。