ichirin2501's diary

いっちりーん。

SRM449 DIV2

初陣、そして心が折れた。

250pt

二等辺の直角三角形ということが分かれば解けます。
角度が全て同じなので、谷の部分は反転と平行移動で一つの二等辺直角三角形を作ることが出来る。
最小のstartから最大のfinish地点までの差の長さを持つ二等辺直角三角形の2辺の長さを求めれば良い。

500pt

謎、明らかに数学寄り。
後で解読する。
追記2:
まずxが奇数のとき、f(x)=x である。
2^nの値は偶数でしか成り立っていないため、必ずf(2^n)=1になる。
2^nの値に奇数xを掛けた値は、f( (2^n) * x)=xとなる。
ここで奇数列の級数はΣ(2n-1)=n^2
2^nを初項、数列(2^n)*xの値がNを超えない範囲で奇数xを足していけば良い。
値2^n〜Nの範囲から(2^n)*xの数列を取り除いていくと、ちょうど半分ずつになっていく。
このとき項数が奇数なら自身も含むので1個項が多くなることに注意。


f(1),f(2),f(3),f(4),f(5),f(6),f(7),f(8),f(9),f(10),f(11),f(12) → 1,3,5,7,9,11を足す

x ,f(2), x ,f(4), x ,f(6), x ,f(8), x ,f(10), x ,f(12) → 1,3,5

x , x , x ,f(4), x , x , x ,f(8), x , x , x ,f(12) → 1,3

x , x , x , x , x , x , x ,f(8), x , x , x , x → 1

x , x , x , x , x , x , x , x , x , x , x , x

こんな感じで足していけばいい。

class OddDivisors
{
public:
  long long findSum(int N){
    int n=N;
    long long ans=0;
    for(int i=0;1<<i <= N;i++){
      long long d=(long long)ceil((double)n/2.);
      ans+=d*d;
      n/=2;
    }
    return ans;
  }
};

再帰で解いてる人を多く見かけた。解釈通りならループのほうが表現し易い気がするけど、
ループは動作をそのまま書いてるだけで、プログラム的に書いているわけではないということか?…orz
追記3:
Login - TopCoder Wiki
解説を読んでみた。再帰で書く理由が分かった、そもそも視点が違っていたようだ。


1000pt

開いただけ、ヘキサゴン見て閉じた。この間3秒強


1問も解けませんでしたorz
二等辺"直角"三角形だったなんて…。
正しく問題文が読めても1問しか解けなかったなぁ。


追記1:
頭が死んでいるらしい。
別に直角じゃなくても入力からして辺の長さが一定に揃わないと答えが出せない。
よって、同角になると何故そこまで頭が廻らなかったのか。死んでいる