要素数は同じであり、各i番目の要素により、i番目の山が来まる。出力は、誤差が10^-9まで許される、歩いた距離。適当に要点だけまとめたつもりだけど、自分で読んだ方が良いかも。これは問題読むのに時間かかったものの、割とすぐ解法に気付きました。要は、連なった山の端点のみに注目すれば良い話。山が必ず重なっているという点がミソですね。その端点から作られる直角二等辺三角形の等辺の長さを求めてやれば答えになります。割ることができる、最大の奇数を返す。5この問題は、答えを出すことは難しくないです。制限時間内で解く解法を見つけることが重要。以下、実装したプログラムの簡単な概要。そのまま値を返せばOK.(2)偶数の場合は、各偶数xについて、以下のように処理した。x;しかし、これだと処理時間に時間がかかりすぎる。最大値が1000000000(十億)だったが、それを処理するのに数十秒かかっていた。再帰は時間がかかるから無理だろうと思っていたが、解いている人は大体が再帰だった気がする。時間があるときに、どこかの解説でも読んでみようと思う。問題やら作ったプログラムのアルゴリズムやら、書くのに結構時間がかかってしまった。次からはもっと省くかも。[2009/09/24:追記]講義中に500ptの問題を出しました。10~20分くらいで解かれてしまった。計算量のアルゴリズム。この問題は、コンテスト中に私が書いたようなO(N・logN)や、O(N)のやり方ではTimeOutになる。そのため、以下にO(logN)で解く方法を説明する。この問題の解法でキーとなるのは次の2点。1奇数の和は次のようにあらわされる。次のような場合を考える。この例では一番右の項が奇数と仮定しているが、偶数であればその隣を考えれば良い。すると、次のようにまとめることができる。