トップ› 九州大学› 2003年› 文系第5問

九州大学 2003年文系第5問解説

注意画像に「(1)の問題に付随する流れ図」が含まれておらず、(1)を解答するための情報が不足しています。以下は(1)を解答不能とし、「(2)の解答解説」として解釈した場合の出力です。

方針・初手

(2)は、円 $(x-A)^2+(y-B)^2 \le R^2$ の内部および周上かつ $x>0, y>0$ を満たす格子点 $(x, y)$ を全探索する方針をとる。
探索範囲は $A-R \le x \le A+R$ かつ $B-R \le y \le B+R$ の範囲内の正の整数とすれば十分である。
条件を満たす格子点が見つかるたびに個数をインクリメントし、原点からの距離の2乗 $x^2+y^2$ を計算して最大値を更新する。
距離が等しい場合は $x$ 座標が最大のものを選ぶという条件に注意して更新処理を行う。

解法1

(2)の方針

自然数 $A, B, R$ が与えられたとき、調べるべき格子点 $(x, y)$ は第1象限（$x$ 軸、$y$ 軸を含まない）にあるため、$x \ge 1$ かつ $y \ge 1$ を満たす。また、円 $(x-A)^2+(y-B)^2 \le R^2$ の内部および周上にあるため、存在し得る範囲は $$A-R \le x \le A+R$$ $$B-R \le y \le B+R$$ である。したがって、$x$ および $y$ の探索範囲をそれぞれ $\max(1, A-R) \le x \le A+R$、$\max(1, B-R) \le y \le B+R$ として全探索を行えばよい。

各格子点 $(x, y)$ について、 $$(x-A)^2 + (y-B)^2 \le R^2$$ を満たすか判定する。満たす場合は、格子点の個数 $N$ を $1$ 増やす。さらに、原点からの距離の2乗 $D = x^2+y^2$ を計算し、これまでに見つかった最大距離の2乗 $D_{\max}$ と比較する。

$D > D_{\max}$ の場合：最大値を更新し、そのときの座標 $(X, Y)$ を $(x, y)$ で上書きする。
$D = D_{\max}$ の場合：複数個ある場合は $x$ 座標が最大のものを記録するため、$x > X$ であれば座標 $(X, Y)$ を $(x, y)$ で上書きする。

以上の方針に基づくプログラムの流れを以下に記述する。

流れ図の構成（処理手順）

[入力] $A, B, R$ を入力する。
[初期化] $N \leftarrow 0$ $D_{\max} \leftarrow 0$ $X \leftarrow 0, Y \leftarrow 0$
[変数設定] $x_{\min} \leftarrow \max(1, A - R)$ $x_{\max} \leftarrow A + R$ $y_{\min} \leftarrow \max(1, B - R)$ $y_{\max} \leftarrow B + R$
[外部ループ] $x$ を $x_{\min}$ から $x_{\max}$ まで $1$ ずつ増やしながら以下を繰り返す。
1. [内部ループ] $y$ を $y_{\min}$ から $y_{\max}$ まで $1$ ずつ増やしながら以下を繰り返す。
  1. [条件判定] $(x-A)^2 + (y-B)^2 \le R^2$ か？
    - 満たす場合： $N \leftarrow N + 1$ $D \leftarrow x^2 + y^2$
      - [条件判定] $D > D_{\max}$ か？
        
        満たす場合： $D_{\max} \leftarrow D$ $X \leftarrow x$ $Y \leftarrow y$
        
        満たさない場合：
        
        [条件判定] $D = D_{\max}$ かつ $x > X$ か？
        
        満たす場合： $X \leftarrow x$ $Y \leftarrow y$
[出力] $N, X, Y$ を出力する。
[終了]

解説

(1)については問題文に不可欠な「流れ図」の画像が欠落しているため解答不可能である。(2)は数学的な条件をプログラム上の反復処理と条件分岐に落とし込む典型的なアルゴリズム問題である。

第1象限という条件から $x \ge 1, y \ge 1$ を忘れずに設定することが重要である。また、距離の比較においては平方根を計算すると浮動小数点数の誤差が生じる可能性があるため、プログラムでは距離の2乗である $x^2+y^2$ を用いて整数値のまま比較するのが定石である。さらに、最大値が等しい場合のタイブレーク条件（$x$ 座標が最大のものを選ぶ）を正しく組み込む必要がある。