方針
既存確認済みの流れ図を、 を満たす自然数の組を小さい から調べ、出力個数 を数える処理として読む。(2) は円を含む第1象限内の整数長方形だけを探索範囲にし、各格子点が円内にあるかを判定する。個数を増やす処理と、原点からの距離最大かつ同距離なら 座標最大という更新条件を分けて設計する。
解答
(1)
この流れ図は、 を満たす自然数の組を、 の小さい順に調べて出力し、その個数を として最後に出力する処理である。 の正の約数は である。したがって、出力される は順に である。組の個数は8個なので、最後に を出力する。
(2)
方針は、円を含む最小限の整数長方形を調べ、その中で第1象限にある格子点だけを判定することである。
まず探索する の範囲は でよく、 の範囲は でよい。ここで下限を1以上にするのは、第1象限で 軸、 軸を含まないからである。
各格子点 について を満たすなら、その点は円の内部または周上にあるので、個数 を1増やす。
さらに、最大距離の点を記録するため、現在の記録を 、最大距離の2乗を とする。新しい点が円内にあるとき なら記録を更新する。また で、かつ なら、問題の指定に従って 座標が大きい点へ更新する。
すべての候補を調べ終えたら を出力すればよい。流れ図では、外側の繰り返しで を動かし、内側の繰り返しで を動かすようにすれば実現できる。
別解
解法2(反復条件と不変量)
方針
(1) は外側ループごとに が1増え、内側ループ終了時に となることを使う。(2) は疑似コードで探索範囲・個数・最良点の不変量を明示する。
解答
(1)
各 について、内側の反復が終了した時点でである。そこで のときだけ出力されるから、出力は の正の約数
と商 の組である。 では最後に が出力される。
(2) とし、次の疑似コードを流れ図へ移せばよい。各反復の終了時に、 は調査済みの円内格子点数、 は調査済み点の
うち指定順序で最大の点を表す。よって全候補の調査後に正しい値が出力される。
総評
難度6、計算量5。目安時間は16〜22分。採点ポイントは、(1) で流れ図の処理を約数対の出力として読み、 の約数対を漏れなく出すこと、(2) で円を含む有限範囲に探索を絞ること、最大距離が同じ場合に 座標が大きい点を選ぶ処理を明記することです。
誤りやすいのは、第1象限に軸を含めて や を探索してしまうことです。また距離比較では平方根を取る必要はなく、 の大小で十分です。流れ図を書く場合も、個数を数える更新と、最大点を更新する条件を別々に置くと誤作動を避けられます。