ガジェット通信 GetNews

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

「放物線とマス目の関係」問題の解答と解説

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

table.nabe{
margin-left:30px;
}
.nabefloat{
float:right;
}
table.nabe td, table.nabe th{
padding:3px;
}
table.nabe th{
background-color: #ccc;
}
table.nabe td{
background-color: #ddd;
}
code.nabe{
border:solid 1px #ccc;
font-family:”Courier”;
}
td code.nabe{
border:none;
}
ol.nabe li{
margin-left:2em;
}
ul.nabe li{
margin-left: :1em;
}
blockquote.nabe{
border:solid 1px;
padding:1mm 1mm 1mm 1mm ;
}
img.nabe{
width:240px;
}
code.expr{
display:block;
margin-left:2em;
}
.nabe_q{
height:10em;
overflow:scroll;
border:black solid 1px;
}
blockquote.nabe{
height:10em;
overflow:scroll;
border:#888 solid 1px;
}

概要とか

「放物線とマス目の関係」という問題が先日締め切られました。多数の挑戦をいただいたんですが、初回投稿の正解率5%以下という状況でした。
間違ってしまった方のために、どうすればよかったのかをコードを交えて解説させていただきたいと思います。

まずは問題のおさらいです。今回は以下のような問題でした:

【概要】

放物線の方程式とマス目を指定するので、位置関係がどうなっているのかを計算して下さい。
【詳細】

放物線とマス目の位置関係は下表の5種類があります(以下、y 座標が大きい方向が上、x座標が大きい方向が右、になります):

記号
状況

U

完全に放物線より上にある

「放物線とマス目の関係」問題の解答と解説

u

マス目の内部は放物線より上にあるが、マス目と放物線に共有点がある。

「放物線とマス目の関係」問題の解答と解説

S

マス目を放物線が分断し、放物線より上にも下にも 0 より大きな面積がある

「放物線とマス目の関係」問題の解答と解説

L

完全に放物線より下にある

「放物線とマス目の関係」問題の解答と解説

l

マス目の内部は放物線より下にあるが、マス目と放物線に共有点がある。

「放物線とマス目の関係」問題の解答と解説
【入出力】

入力は

1 0 0 0 -3

のようになっています。

空白区切りになっていて、順に a, b, c, X, Y です。

a, b, c は、放物線y=ax2+bx+cの係数です。

X, Y はマス目の左下隅の座標です。マス目の大きさは、 1×1 です。

つまり、マス目の領域は
(x,y) = { |x,y| X≦x≦X+1, Y≦y≦Y+1 }
です。

出力は、

L

のような感じです。

U
,
u
,
S
,
L
,
l
のいずれかを出力して下さい。

【補足】
不正な入力に対処する必要はありません。
a は、-100000 以上 100000 以下のゼロではない整数です。
b, c, X, Y は、-100000 以上 100000 以下の整数です。

問題の方は、1×1のマス目と放物線の位置関係を、5つに分類するというものでした。

放物線は整数係数で、マス目の位置も整数です。

実際のテストケースは以下の通りでした:

#
入力
期待
0

8 -8 2 0 -1

l

1

110 -198 90 0 0

S

2

40 -40 10 0 1

S

3

10 -5 0 0 2

S

4

10 -10 0 0 2

U

5

-8 8 -2 0 1

U

6

-3 7 4 -2 -6

u

7

1 -10 25 3 4

u

8

-200 5160 -33275 12 6

S

9

4 -4 1 0 0

S

10

10 -18 9 0 0

S

11

-1 3 0 1 1

l

改めて見直してみると L が入っていませんね。ちょっと自分でびっくりしました。

実装

キーになる x 座標が3つ、あるいは2つあります。

まずはマス目の左端と右端です。必ずキーになります。

もうひとつは放物線の軸です。ただし、軸がマス目を通らない場合はキーにはならなくなります。

キーになる x 座標を放物線の式に代入して、出て来る値がマス目の上にあるのか、あるいは下にあるのかを観察すればよいわけです。

全てマス目の上辺より上→U
全てマス目の下辺より下→L
マス目の上辺より上と、マス目の上辺ぴったり → u
マス目の下辺より下と、マス目の下辺ぴったり → l
それ以外 → S

です。ruby で書くとこんな感じです:

#二次式クラス
class Poly
def initialize( a, b, c )
@a=a; @b=b; @c=c
end
def f(x); @a*x*x+@b*x+@c; end
def axis; -@b/(2*@a); end
end

#条件の評価
def evaluate( q )
case q.uniq.sort.join(“,”)
when “-1”; “U”
when “-1,0”; “u”
when “1”; “L”
when “0,1”; “l”
else; “S”
end
end

#問題を解く
def solve(s)
a, b, c, x, y = s.split(” “).map(&:to_r)
poly = Poly.new( a, b, c )
y0=poly.f(x)
y1=poly.f(x+1)
q=[y0y, y0(y+1), y1y, y1y+1]
if (x..x+1)===poly.axis
ya = poly.f( poly.axis )
q+=[yay, ya(y+1) ]
end
evaluate(q)
end

puts( solve( gets.strip ) )

実装のポイントですが、まずは、有理数の利用です。「接する」というデリケートな情報を扱うので、誤差のない計算が必要です。有理数を使うことで、頭を使うポイントを減らすことができます。

次に、条件の整理です。

4個または6個の評価ポイント(x座標が2個または3個。y座標が2個なので、都合4個または6個になります)が、放物線よりも上か下かを演算子を使って評価しています。

全てマス目の上辺より上 → 全部 -1 → U
全てマス目の下辺より下 → 全部 1 → L
マス目の上辺より上と、マス目の上辺ぴったり → 0 と-1→ u
マス目の下辺より下と、マス目の下辺ぴったり → 0と1 → l
それ以外 → S

という具合です。

「全部-1」とか「0と1」という条件を簡単に評価するために、uniq.sortという処理を行っています。

ちょっと長くなりますが、上記のコードをそのまま C言語(C99)に移植するとこんな感じです:

// clang -std=c99 -Wall
#include
#include
#include
#include

//有理数
struct rational
{
int64_t n, d;
};

// 有理数の生成
struct rational rational( int64_t n, int64_t d )
{
return ( struct rational ){ n, d };
}

// 有理数の乗算
struct rational mul( struct rational a, struct rational b )
{
return rational( a.n*b.n, a.d*b.d );
}

// 有理数の加算
struct rational add( struct rational a, struct rational b )
{
return rational( a.n*b.d+b.n*a.d, a.d*b.d );
}

// 分母を正の数にする
struct rational normalize( struct rational a )
{
return ( a.d

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