naoya_t@topcoder

SRM478

21:57 |

林檎回

黄色と青のみの部屋で

DIV	level	問題名	競技中	後で	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 黄色微増