CodeIQ MAGAZINECodeIQ MAGAZINE

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

2017.11.29 Category:CodeIQ問題解説・リーダーボード Tag: ,

  • 5
  • このエントリーをはてなブックマークに追加

「数学の問題をプログラミングで解こう!」シリーズ。
格子点を通る点の個数に関する問題でした。
ある 2 点を通る直線が満たすべき条件をうまくコードに落とし込んでやりましょう。

みなさんはうまくできましたか?
ぜひ出題者のKawazoeさんによる本記事で解法をチェックしてください!
by CodeIQ運営事務局

問題のおさらい

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 点の横方向の差 (ca) と 縦方向の差 (db) が互いに素(2 以上の約数を共通に持たない)であればよいと分かります(左図)。つまり、cadb の最大公約数が 1 であればよいということです。一方、互いに素でない場合は、途中で格子点を通ることが分かります(右図)。

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

最後に C の部分です。これは B とほとんど同じ議論です。点 (c, d) を点 (a, b) に対して折り返した位置 (2ac, 2bd) が格子点の全体の外にあれば、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 < n and y >= 0 and y < n

def f(n):
    if n == 2: return 6
    answer = 0
    for a in range(0, n):
        for b in range(0, n):
            for c in range(a+1, n):
                for d in range(0, n):
                    if b == d: continue
                    if gcd(c-a, abs(d-b)) > 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 つの整数 pq を用いて、直線の傾きを qp とします。このとき、n2 個の格子点のうちで、そこから右上方向に引いた半直線が、自身を含め 2 個以上の格子点を通るようなものはどれだけあるでしょうか? 下図は、n=16, (p, q)=(7, 3) の場合を例に、そのような点を青で表しました。青のない部分は、1 個しか通らないため当てはまりません。

そのような青の点は、全部で (np)×(nq) 個あります。

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

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

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

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

これですべての準備ができました。コード例は以下です。pq となる場合だけ実際の計算を行い、対称性を用いて、pq の場合や傾きが負になる場合を、結果を 4 倍することで求めています。また pq となる場合、つまり (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さんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

  • 5
  • このエントリーをはてなブックマークに追加

■関連記事

【謎解きプログラム】座標の移動【Matrix】解答と解説... 【謎解きプログラム】座標の移動【Matrix】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以内に...
【謎解きプログラム】この処理は?【コードを読もう】解答と解説... 【謎解きプログラム】この処理は?【コードを読もう】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以...
数学の問題をプログラミングで解こう!「ループ・トラッキング」問題解説... 問題のおさらい 自然数 n に対し、関数 Fn(x) を次のように定義します(floor():床関数)。 例えば n=10, x=1 のとき、F10(1) = floor(4×1×9÷10) = 3 です。 さて、整数 k(0 ≦ k ≦ n)に対して、関数 Fn による変換を繰り返し行い...
【謎解きプログラム】どんな結果になる?【アロー関数】解答と解説... 【謎解きプログラム】どんな結果になる?【アロー関数】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...
数学の問題をプログラミングで解こう!「カウント・スリー」問題解説... 問題のおさらい 自然数を 1 から順に書き並べていきます。 このとき、3 の数字が現れる回数を数えます。 自然数 n に対し、ちょうど n 個目の 3 の数字が現れたときに書いている数を F(n) と定義します。 例えば F(10)=35 です。 下の通り、10 個目の 3 は、35 を書いて...
【息抜き】カードを上手く並べよう【言語不問】解答と解説... 【息抜き】カードを上手く並べよう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 あなたは、11から99までの、89枚のカードを持っています。問題では、横幅と高さの整数が与えられます。この横幅と高さで作られるマス...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ