2017年03月 / 01月≪ 12345678910111213141516171819202122232425262728293031≫03月

2009.09.24 (Thu)

TopCoder SRM 449 DIV2 後書き

初挑戦だった、TopCoderSRM。
結果を先に言うと、

   ・プログラムをSubmitしたもの:250pt、500pt
   ・チャレンジで崩されたもの:500pt
   ・チャレンジ成功したもの:500pt ×2
   ・チャレンジ失敗したもの:500pt ×1

   ・プログラムによるScore = 171.98 + 0
   ・チャレンジによるScore = 50 + 50 - 25
   ・合計 Score = 246.98
   ・Rating 1336


1000ptの問題には目を通してすらいません。
とりあえず、500ポイントの欠陥プログラムは落とされることは予想してました。
処理に数十秒かかってたので。
で、自分の問題点が分かっているので、あとは同じような人を探せばチャレンジが成功するわけで。。。
ただ、調子に乗って一つ失敗してしまった orz

今回参戦して思ったのは、まず英語力が欲しい。
英語がネイティブだったりする人たちとは、それだけでハンディになる。
次に、単に実力不足。
DIV2なのに500Ptで頭抱えるんだから、まだまだダメダメです。


さて、肝心の問題。
目を通した 250pt と 500pt についてだけ書きます。
ここに書くのは解答の解説ではなく、あくまで問題内容と自分の作ったプログラム・アルゴリズムについて。
まだ解法がよくわからないものもあるので。。。

では、詳しくは「追記」(More)へどうぞ。


【More・・・】

[ 250point 問題 ]
ある登山家が歩く距離を求める問題。
山は直角二等辺三角形で、直角部分が上にくる。
直角部分の反対側にある辺は、x軸上で固定。
直角三角形の山が複数連なって、一つの山が形成される。
複数与えられる場合、山が離れることは無い。
山が重なった場合、一番外側を通る。
問題にある図を見るとわかりやすい。

入力は start と finish の、2種類の配列。
start は山の左側のx座標を示し、 finish は山の右側を示す。
start と finish の要素数は同じであり、各i番目の要素により、i番目の山が来まる。

出力は、誤差が10^-9まで許される、歩いた距離。

適当に要点だけまとめたつもりだけど、自分で読んだ方が良いかも。。。


さて、これは問題読むのに時間かかったものの、割とすぐ解法に気付きました。
要は、連なった山の端点のみに注目すれば良い話。
山が必ず重なっているという点がミソですね。
その端点から作られる直角二等辺三角形の等辺の長さを求めてやれば答えになります。



public double findDistance(int[] s, int[] f)
{
int a = 1000, b = a*(-1);
for (int i = 0; i < s.Length; i++)
{
if (a > s[i]) a = s[i];
if (b < f[i]) b = f[i];
}
return ((double)(b - a) / Math.Sqrt(2.0))*2;
}





[ 500point 問題 ]
次のような関数 F(N) を求める問題。

       F(N) = f(N) + f(N-1) + f(N-2) + ....... + f(2) + f(1)

f(x) は x を割ることができる、最大の奇数を返す。

(Ex)
f(1) = 1
f(2) = 1 + 2
f(3) = 1 + 1 + 3
f(4) = 1 + 1 + 3 + 1
f(5) = 1 + 1 + 3 + 1 + 5


この問題は、答えを出すことは難しくないです。
制限時間内で解く解法を見つけることが重要。
しかし、良く分かりませんでした。

以下、実装したプログラムの簡単な概要。
(1)f(x)に与えられた数字 x が奇数であれば、 x はそのまま値を返せばOK.
(2)偶数の場合は、各偶数xについて、以下のように処理した。
  ①. if(x % 2 == 1) goto ④;
  ②. else xを2で割る。
  ③. if(x == 2) return 1; else goto ①;
  ④. return x;

しかし、これだと処理時間に時間がかかりすぎる。
最大値が1000000000(十億)だったが、それを処理するのに数十秒かかっていた。
再帰は時間がかかるから無理だろうと思っていたが、解いている人は大体が再帰だった気がする。

また時間があるときに、どこかの解説でも読んでみようと思う。
てか、問題やら作ったプログラムのアルゴリズムやら、書くのに結構時間がかかってしまった。。。
次からはもっと省くかも。



[2009/09/24:追記]
講義中に500ptの問題を出しました。
10~20分くらいで解かれてしまった。
もちろん、オーダーlogN の計算量のアルゴリズム。
この問題は、コンテスト中に私が書いたようなO(N・logN)や、O(N)のやり方ではTimeOutになる。
そのため、以下にO(logN)で解く方法を説明する。

さて、この問題の解法でキーとなるのは次の2点。

   ①奇数の和は次のようにあらわされる。 1 + 3 + 5 + 7 + ・・・ + N = ( (N+1)/2 ) ^ 2
   ②偶数は、2で割り続けると奇数になる

これらを考えると、次のようにして目的の F(N) を得ることができる。



まず、次のような場合を考える。
この例では一番右の項が奇数と仮定しているが、偶数であればその隣を考えれば良い。
まず、①の性質を考える。

TopCoderSRM449DIV2-2_No01

すると、次のようにまとめることができる。

TopCoderSRM449DIV2-2_No02

次に、②の偶数の性質に注目し、残った偶数部分を 2 で割る。
すると、

TopCoderSRM449DIV2-2_No03

となる。
これをみると、最初の図における奇数の列が見てとれる。
ただし、長さは半分になっている。
このように処理をしていくことで、O(logN)で解を得ることができる。

TopCoderSRM449DIV2-2_No04



[プログラム]
上の OddDivisor が再帰的な効率の良いプログラム。
下の OddDivisor2 が、コンテスト中に作ったヘタレプログラム。

OddDivisor


こんなに画像やら長文やらを使いまくった記事は久しぶりだなぁ・・・
正直疲れた。
こんなに細かくやるのは今回が最後だろう、きっと。
明日のゼミでの発表から現実逃避しているわけではありません。
決して違いますとも。


テーマ : プログラミング ジャンル : コンピュータ

03:06  |  プログラミング系  |  TB(0)  |  CM(2)  |  EDIT  |  Top↑

*Comment

■Re: Qtのパッケージ

> はじめまして。
> utamaruともうします。
>
> Qtのインストールの記事を拝見しました。
> 私もQtでインストール試したのですが、
> Gasserさんと同じところでつまづきました。
>
> その後、Qtのパッケージのインストールはできたのでしょうか?
>
> 私もQtのパッケージを探してみましたが、どれをダウンロードすれば
> いいのか分からず、インストールできていません。
>
> よければ、どこでどのQtのパッケージをダウンロードすればよいのか
> 教えて頂けないでしょうか?
>
> よろしくお願いいたします。


どうもutamaruさん、初めまして。

う~ん、確かインストールできずに終わってた気がします。
HDDの容量が足りなくなったので今ではLINUXすらありません。
まぁ、ちょっとサーバーたててみたいなぁとか思い、再インストールも考えてはいますが・・・。

少し脱線しましたが、本題について。
正直、インストールできずじまいだったのでお役には立てなさそうです。
しかし、 http://gasser.blog114.fc2.com/blog-entry-196.html#comment129 に、パッケージからインストールできるというアドバイスがありました。
なので、私は単に apt-get にあるのかなぁ、とか思ったんですが・・・。
まぁなんにせよ、楽にインストールする方法があるようです。

私は今試す環境が無く、力にはなれませんが、インストール頑張って下さい。

Gasser |  2009.09.28(月) 18:09 |  URL |  【コメント編集】

■Qtのパッケージ

はじめまして。
utamaruともうします。

Qtのインストールの記事を拝見しました。
私もQtでインストール試したのですが、
Gasserさんと同じところでつまづきました。

その後、Qtのパッケージのインストールはできたのでしょうか?

私もQtのパッケージを探してみましたが、どれをダウンロードすれば
いいのか分からず、インストールできていません。

よければ、どこでどのQtのパッケージをダウンロードすればよいのか
教えて頂けないでしょうか?

よろしくお願いいたします。
utamaru |  2009.09.27(日) 15:29 |  URL |  【コメント編集】

コメントを投稿する

URL
COMMENT
PASS  編集・削除するのに必要
SECRET  管理者だけにコメントを表示  (非公開コメント投稿可能)
 

▲PageTop

*Trackback

この記事のトラックバックURL

→http://gasser.blog114.fc2.com/tb.php/370-1798d47d

この記事にトラックバックする(FC2ブログユーザー)

この記事へのトラックバック

▲PageTop

 | BLOGTOP |