Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-08-04

SRM478

21:57 | SRM478 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM478 - naoya_t@topcoder SRM478 - naoya_t@topcoder のブックマークコメント

林檎回

黄色と青のみの部屋で

DIVlevel問題名競技中後でSystem Test通過率備考levenshtein
1 250 CarrotJumping o - passed (144.96) - _ 0
1 500 KiwiJuice 間に合わず - - - _ ?
1 1000 - 開いてない - - - _ ?

Easy(250): CarrotJumping

  • Ubuntuマシンから初参加
    • あれれテストが生成されないマクロが出ない
    • プラグインの設定間違ってるのかorz
    • ええい自力でテスト書くぞ...
    • 時間を随分ロスした
  • BigInt問題?
    • いやそんなはずがない。林檎回だもの。
  • 4x+3,8x+7,16x+15,32x+31,...
    • (2^a)(x+1)-1 where 2<=a<=300000
    • 先にDPでa=[2..300000]に何ステップで到達するか見といた
    • (2^a)(x+1)-1 = 1000000007*k
    • ∴ (2^a)(x+1) = 1 mod 1000000007
    • はいはいあとは書くだけ
  • passed; 144.96 (29'03)
    • こんなのに30分もかけてて恥ずかしい
using namespace std;
typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);var++)

ll M=1000000007LL;
#define BIG 9999999

class CarrotJumping {
 public:
  int theJump(int init) {
    ll x=init;
    if (x%M == 0) return 0;
    vector<int> st(300004, BIG);
    st[0]=0;
    rep(i,300000) {
      if(st[i]<BIG){
        st[i+2]=min(st[i+2],st[i]+1);
        st[i+3]=min(st[i+3],st[i]+1);
      }
    }
    ll z=x+1;
    int res=100001;
    for(int i=1;i<=300000;i++){
      z *= 2; z %= M;
      if(st[i]>100000) continue;
      if (z == 1) res=min(res,st[i]);
    }
    return (res <= 100000)? res : -1;
  }
};

// BEGIN CUT HERE
#include "cout.h"
main(){
  cout<<  CarrotJumping().theJump(125000000) << endl;
  cout<<  CarrotJumping().theJump(281250001) << endl;
  cout<<  CarrotJumping().theJump(18426114) << endl;
  cout<<  CarrotJumping().theJump(4530664) << endl;
  cout<<  CarrotJumping().theJump(705616876) << endl;
  cout<<  CarrotJumping().theJump(852808441) << endl;
}
// END CUT HERE

Medium(500): KiwiJuice

  • 残り45分強
  • 最後のケースが思い切りTLE

Hard(1000): 開いてない

Challenge Phase

  • 落とさず落とされず
  • 250×1,500×1。不活発

System Test

  • 500が2つ落ちてた

結果

144.96points

Room: 5/20

Div1: 283/694

1525→1557 黄色微増

http://gyazo.com/278b4fae482d48574c6ab3533ae3b497.png

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100804