Hatena::Grouptopcoder

cou929のTopCoder日記

2009-09-23

SRM449 div2

02:42

250のみ解け、チャレンジ一人成功。レイティングは30ほどアップし1112。全体的に難しいラウンドでした。

Easy - MountainRoad

山脈の長さを求める問題。山脈は個別の山の和のような感じで表現され、一つ一つの山は直角二等辺三角形で、斜辺が下になるよう置いていく。

それぞれの山は直角二等辺三角形であることと山脈は絶対に一つの連なったものであるという制約があるので、単に山脈の始点・終点が斜辺となる大きい直角二等辺三角形を考えるだけですみました。思いつくのには時間がかかりましたが、結果はシンプルです。

class MountainRoad {
public:
  double findDistance(vector <int> start, vector <int> finish)
  {
    double ret = 0;
    int left = 1001;
    int right = -1001;

    for (int i=0; i<start.size(); i++)
      {
	left = min(left, start[i]);
	right = max(right, finish[i]);
      }

    ret = (double)(right - left) * sqrt(2);

    return ret;
  }
};

Medium - OddDivisors

f(x)をxの奇数の最大の約数とする。整数Nが与えられるので、f(1)+f(2)+...+f(N)を求めよ。

ストレートに考えると、1~Nまでひとつづつ、奇数ならその値素のものを、偶数なら奇数になるまで2で割っていった時の値を、結果の変数に足し込んでいけばできるはずです。しかしインプットが最大100000000なので、間に合いません。結果をメモ化してみようとしたのですが、必要な配列のサイズが大きすぎてできません。また代わりにmapでメモを作っても、速度はあまり上がりませんでした。結局良い解法が思いつかないまま終了。以下はTLEなコード。

class OddDivisors {
public:
  long long findSum(int N)
  {
    long long ret = 0;

    for (int i=1; i<=N; i++)
      {
	if (i % 2 == 1)
	    ret += i;
	else
	  {
	    int tmp = i;
	    while (tmp % 2 == 0)
	      tmp /= 2;
	    ret += tmp;
	  }
      }

    return ret;
  }
};

Hard - HexagonalBattlefieldEasy

開けてません。あとで復習したい。

Challenge Phase

とりあえず1000000000をインプットにして、500点問題を一人撃墜しました。間違えている人があと何人かいたんですが、他の人に先を越されました。

250のシステムテストで落ちている人が何人かいたんですが、僕が思いついたのと違うアプローチでやっている人のは、短時間ではコードが追いきれなかったんで、全然ミスが発見できませんでした。

Rating

30ほど上がり、1112になりました。

前回から明らかにレイティング上昇率が鈍っているので、ここが現在の自分の実力の適正ラインなんだと思います。はやく一皮むけて、div1に進みたいです。

maka776maka7762009/09/26 00:27500のOddDivisorsですが、N=20位までの結果を表にしてまとめてから、偶数の場合の結果だけ眺めて見ると、良いかもしれません。

DayaneDayane2012/07/10 08:29Ariltces like this just make me want to visit your website even more.

vouvpeunybvouvpeunyb2012/07/11 08:21yeGxre <a href="http://lkvcfmvpksva.com/">lkvcfmvpksva</a>

dfjijvygecddfjijvygecd2012/07/11 21:10Jf0InD , [url=http://hxvdojaekguw.com/]hxvdojaekguw[/url], [link=http://jcsshhazxqlk.com/]jcsshhazxqlk[/link], http://qpshsgfkhmdk.com/

jhyhejqujhyhejqu2012/07/12 12:54nknntl <a href="http://deiwdotnhqll.com/">deiwdotnhqll</a>

yjurrexxuyjurrexxu2012/07/12 18:27RmLNI7 , [url=http://vogjaljudldj.com/]vogjaljudldj[/url], [link=http://muvyghjkblcj.com/]muvyghjkblcj[/link], http://neqnwcnosays.com/