SRM 478

開始5分前で参加決め込んだDIV2な人の挑戦…

• 250 実装問題。キウイジュースを注いだりするそうです。
• 500 10億7でたー。で、ちょっとよくわかりませんでしたが、今回は解けました。ふたつの移動が可換だということに気づいたところから、面倒なプロセスを踏んで回答。
• 1000 2^25でいけるだろ、と思ったのですが、答えが合わない…思考停止。時間切れ。前回同様、動的計画法でやるそうです。正直分かってても構築できん！

もうちょっと頑張れば全完できたかもしれん。悔しい。

Result

250: Passed System Test
500: Passed System Test
1000: Compiled

250

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#include<complex>

using namespace std;

class KiwiJuiceEasy {
public:
  vector <int> thePouring(vector <int> capacities, vector <int> bottles, vector <int> fromId, vector <int> toId) {
    for(int m = 0; m < fromId.size(); ++m){
      int fr = bottles[ fromId[m] ];
      int to = bottles[ toId[m] ];
      int tocap = capacities[ toId[m] ];
      
      if( fr + to > tocap  ){
	bottles[ toId[m] ] = tocap;
	bottles[ fromId[m] ] = fr - (tocap - to);
      }else{
	bottles[ toId[m] ] += fr;
	bottles[ fromId[m] ] = 0;
      }
    }
    return bottles;
  }
};

500

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#include<complex>

#define MAX 300000
#define CARROT 1000000007
using namespace std;

class CarrotJumping {
public:
  long long int table[MAX+1];
  long long int f[MAX+1];
  void Make(){
    int tmp = 4;
    for(int n=2;n<=MAX;++n){
      table[n] = tmp % CARROT;
      tmp *= 2;
      tmp %= CARROT;
    }

    f[0]=1000;f[1]=1000;
    f[2]=1;f[3]=1;
    for(int n=4;n<=MAX;++n){
      f[n] = min( f[n-2]+1, f[n-3]+1 );
    }
  }
  
  int theJump(int init) {
    Make();
    long long int answer = MAX;
    vector< long long int > cands;
    for(int n = 2; n <= MAX; ++n){
      if( ( ((table[n]*init)%CARROT) + ((table[n]-1)%CARROT) ) % CARROT == 0 ){
	cands.push_back( n );
      }
    }
    for(int i = 0; i < cands.size(); ++i){
      answer = min( answer, f[ cands[i] ] );
    }
    if(answer > 100000 ) answer = -1;
    return (int)answer;
  }
};

解法メモ：
A(x) = 4x+3.
B(x) = 8x+7.
と置くと、A(B(A(B(B(A(x))))) など、このふたつからなる任意の移動 T(x) = 2ⁿx + 2ⁿ-1, n = 2a + 3b であり、 a,b はそれぞれ T(x) を再現する際に A(x), B(x) を使用する回数となる。そこで、T(x) % 1000000007 == 0 となる n を列挙すれば、a+bが最小となるような n が答えとなる。