体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

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

問題のおさらい

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 の部分に格子点は存在しません。

1 2 3次のページ
CodeIQ MAGAZINEの記事一覧をみる
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。