Codeforces Round #125 - 不定期プログラミング覚え書き

久しぶりのCodeforces。正直眠かったので解けなかった（開幕言い訳）
最近はコンテストやるたびに自分の頭の悪さに（#^ω^）ﾋﾟｷﾋﾟｷすることが多いです。

Problem A

ある数が、フィボナッチ数の項３つの和で表せるか調べ、表せるならその組み合わせの一つを出力せよ。
無理ならI'm too stupid to solve this problem.と返せ。

考えたこと

なあにこれえ？
10^9が上限らしいし、まずはフィボナッチを全部求めるじゃん？そうしないと解けないし。
……で、どうしろと？
なんとなくフィボナッチの定義からgreedyで良い気がぷんぷんするので書いた。出した。通った。

コード

   int n;
   cin >> n;
   vector<int> fib;
   fib.push_back(0);
   fib.push_back(1);
   int a = 0;
   int b = 1;
   int count = 2;
   while(true){
     if( a + b >= n ) break;
     fib.push_back(a+b);
     int tmp = a+b;
     a = b;
     b = tmp;
     count++;
   }
   int curn=0;
   vector<int> ans;
   for( int j = count-1; j >= 0 ; j-- ){
     int tmp = fib[j];
     if( curn+ tmp <= n ){
      curn+=tmp;
      ans.push_back(tmp);
      j++;
     }
     if( ans.size() >= 3 ) break;
   }
   
   if( ans[0]+ans[1]+ans[2] != n ) cout <<"I'm too stupid to solve this problem" << endl;
   else cout << ans[0] <<" " << ans[1] <<" "<< ans[2] << endl;
   return 0;

後日談

10^9より小さい値だと、大体フィボナッチ数は45個くらいあるらしい。
検証はしてないけどこれなら45^3かけて全探索してよかったかも。
ところでどうやってgreedy証明すればいんだろう？

problem B Special Olympics

中心の一致しない二つの円がある。
円の線には厚みがあるので、「内側の半径と外側の半径と中心の座標」が二つ与えられる。
この図から、いくつの円が切り取れるかを求めよ

考えた事

4つの円が互いに交わるかどうか判定するだけやん？
…と思ったら大嘘だった。
具体的には片方の円描画領域（内側の半径と外側の半径の間）にすっぽりともう片方の縁が入ってたりすると都合が悪い。
これを修正すればよさそうだけどまだやってない。

problem C About Bacteria

とあるバクテリアx匹は１秒ごとにkx+b匹に増える事が知られている。
今、1匹からスタートしたn秒後のバクテリアの数をzとする。
最初にt匹からスタートして、バクテリアの数がz匹になる最小の時間を求めよ

考えたこと

$z = k^n+(k^{n-1}+\cdots+k^2+k+1)b$ である。
求めたいのは
$k^N t+(k^{N-1}+\cdots+k^2+k+1)b \geq k^n+(k^{n-1}+\cdots+k^2+k+1)b$ となる最小のNである。
まず、N=nの時、t>1である限りは（これは入力の制約より保証される)条件を満たす。
式をガチャガチャ変形すると、
$k^N t \geq k^n+(k^{n-1}+k^{n-2}+\cdots+k^N)b$
$t\geq k^{n-N}+(k^{n-1-N}+k^{n-2-N}+\cdots+1)b$
であることがわかり、
N=n,n-1,n-2...と遷移させると
右辺は
1, k+b, k^2+(k+1)b+...となる事から、
これがtを超えない所まで繰り返し、超えたら対応するNの値を出せば良い

コード

   int k,b,n,t;
   cout << "test" << endl;
   cout << endl;
   cin >> k>>b>> n>> t;
   int ans = n;
   long long curnum = 1;
   while( true ){
    curnum*=k;
    curnum+=b;
    if( t < curnum ) break;
    ans--;
    if( ans == 0 ) break;
   }
   cout << ans << endl;
   return 0;

problem D Jumping on Walls

向かい合った二つの壁がある（高さn)。掴まれるところと掴まれない所が入力で指定される。
忍者は「１つのぼる」「１つ下る」「対面の壁のkだけ上の頂点に飛び移る」という行動が許される。
フィールドには徐々に水が注がれており、時刻tの時点で高さt-1以下にいると忍者は溺れてしまう。
以上の条件のもと、忍者が高さnの所まで登れるのかを判定せよ

考えたこと

何故かものすごい愚直な深さ優先探索とか書いて到底終わるわけがなかった。

nの上限が10000だから、2*10000の値を埋めていくような探索（？）で良い気がするのだけれど…
何故かうまくいかない。