ガジェット通信 GetNews

見たことのないものを見に行こう

数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説

DATE:
  • ガジェット通信 GetNewsを≫

問題のおさらい

2 以上の自然数 n に対し、n×n の格子状に並んだ点を考えます。

これらの点のうちちょうど 2 個の点を通る直線の数を F(n) と定義します。

例えば F(2)=6 です。題意を満たす直線は以下の 6 通りです。

数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説

また、F(3)=12 です。題意を満たす直線は以下の 12 通りです。

数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説

同様に、F(4)=48, F(5)=108, F(6)=248, F(7)=428, F(10)=1900 となることが確かめられます。

標準入力から、自然数 n (2 ≦ n ≦ 40)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

方針:2 点をまずは固定しよう

ちょうど 2 つの格子点を通る直線の数を求める問題です。「最初にどの値を固定して考えるか」という視点で考えていきましょう。

n2 個の格子点が登場します。ここから 2 点をまず最初に選び(固定し)、その 2 点を通る直線がほかのどの点も通らないかどうかチェックするという方針を考えましょう。今回は幸い、n の上限は 40 とさほど大きくありません。格子点の総数 n2 はたかだか 1600 個で、そのうちの 2 個の選び方は 1600C2 = 1600×1599÷2 ≒ 128 万通り。このぐらいなら、これらを全てチェックする総当たりのコードでも、なんとか 1 秒の制限時間で答えが出せるのではと予想が立ちます。

以下、考えやすくするために座標平面を導入します。左下の点を (0, 0)、右上の点を (n-1, n-1) とします。いま、2 点 (a, b), (c, d) を固定したとき、この 2 点を通る直線がほかの点を通らないという条件は、a, b, c, d を用いてどのように表されるでしょうか?

下図のように、3 つの部分に分けて考えましょう。

数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説

まず A の部分です。この部分にほかの格子点が存在しないことは、どのように表されるでしょうか。考えてみると、2 点の横方向の差 (c-a) と 縦方向の差 (d-b) が互いに素(2 以上の約数を共通に持たない)であればよいと分かります(左図)。つまり、c-a と d-b の最大公約数が 1 であればよいということです。一方、互いに素でない場合は、途中で格子点を通ることが分かります(右図)。

数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説

次に B の部分です。上の A の条件が成り立っていたとしましょう。点 (a, b) を点 (c, d) に対して折り返した位置 (2c-a, 2d-b) が格子点の全体の外にあれば、B の部分に格子点は存在しないことになります。

数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説

最後に C の部分です。これは B とほとんど同じ議論です。点 (c, d) を点 (a, b) に対して折り返した位置 (2a-c, 2b-d) が格子点の全体の外にあれば、C の部分に格子点は存在しません。

数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説

以上でコードを書く準備は整いました。a, b, c, d についての 4 重ループを書きましょう。A, B, C の条件をひとつひとつチェックして、条件に合うものの個数を数えていきましょう。n=2 の場合は水平方向や鉛直方向の直線も考えなければなりませんので、ここではズルをして固定の正答値を返しています。次のようなコード(Python)になります。なお A で最大公約数を求めるには下記のページ等を参照して下さい。

def gcd(x, y):
return gcd(y % x, x) if x > 0 else y

def inside(x, y, n):
return x >= 0 and x = 0 and y 1: continue
if inside(2*c-a, 2*d-b, n): continue
if inside(2*a-c, 2*b-d, n): continue
answer += 1
return answer

n = input()
print f(n)

参考:Greatest Common Divisor(外部サイト)

以上で本問のクリアが可能です。

さらなる高速化:直線の傾きを固定しよう

さて、本問には別の解法があります。上の解法では最初に 2 点を固定していましたが、こちらの方法は、最初に直線の傾きを固定することが特徴です。

具体例を見ながら考えていきましょう。はじめに、互いに素である 2 つの整数 p と q を用いて、直線の傾きを q/p とします。このとき、n2 個の格子点のうちで、そこから右上方向に引いた半直線が、自身を含め 2 個以上の格子点を通るようなものはどれだけあるでしょうか? 下図は、n=16, (p, q)=(7, 3) の場合を例に、そのような点を青で表しました。青のない部分は、1 個しか通らないため当てはまりません。

数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説

そのような青の点は、全部で (n-p)×(n-q) 個あります。

次に、これらの格子点の中で、この点を通る直線が、自身を含め 3 個以上の格子点を通るようなものはどれだけあるでしょうか? 下図は、そのような点を赤で示したものです。青の領域の右上と左下に、それぞれ (n-2p)×(n-2q) 個のかたまりで存在します。

数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説

ですので、題意の「ちょうど 2 個の格子点を通るような点」の個数は、青の全体の (n-p)×(n-q) から、赤の部分 2×(n-2p)×(n-2q) を引けばよさそうです。

ただ、ここには一つ罠があります。例えば下記の n=16, (p, q)=(5, 3) の場合は、赤の領域が部分的に重なるため、2×(n-2p)×(n-2q) をそのまま引くのは正しくありません。重なる緑の部分の個数である (n-3p)×(n-3q) を、引きすぎた分として足してやらないといけません。

数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説

したがって、求めるべき、ちょうど 2 個の格子点を通るような点の個数は以下の式で計算できます。引き算した結果が負のときに誤った結果にならないように max を通しています。

数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説

これですべての準備ができました。コード例は以下です。p>q となる場合だけ実際の計算を行い、対称性を用いて、p<q の場合や傾きが負になる場合を、結果を 4 倍することで求めています。また p=q となる場合、つまり (p, q)=(1, 1) の場合の答え(4 通り)を固定的に足しています。

def gcd(x, y):
return gcd(y % x, x) if x > 0 else y

def f(n):
if n == 2: return 6
answer = 4
for p in range(1, n+1):
for q in range(1, p):
if gcd(p, q) > 1: continue
a = max(n-p, 0) * max(n-q, 0)
b = max(n-2*p, 0) * max(n-2*q, 0)
c = max(n-3*p, 0) * max(n-3*q, 0)
answer += 4*(a-2*b+c)
return answer

n = input()
print f(n)

これで始めのやり方よりずっと短い計算時間で答えを出すことができます。

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)こちらもぜひチェックして下さい。

CodeIQ「ストレート・ラインズ」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
現在、Kawazoeさんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。