Code Formula 2014 本選

Submission #1390914

Source codeソースコード

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;

const int N = 24;
const int B = 1 << 23;

string s;

int fib[N];

void fib_init(void) {
  int x = 0;
  int y = 1;
  REP(i,0,N) {
    fib[i] = x;
    int r = x + y;
    x = y;
    y = r;
  }
}

int dp[N][B];

int mutual(int n, const string &s, const string &t) {
  // cerr << "call(mutual):" << n << " " << s << " " << t << endl;
  if (n <= 2) {
    return 0;
  }
  if (s.substr(0, t.length()) == t) {
    int sub = mutual(n - 1, t, s.substr(t.length()));
    if (sub >= 0) {
      return 2 * sub;
    }
  }
  if (s.substr(s.length() - t.length()) == t) {
    int sub = mutual(n - 1, t, s.substr(0, s.length() - t.length()));
    if (sub >= 0) {
      return 2 * sub + 1;
    }
  }
  return -1;
}

// if not found, return -1.
int rec(int k) {
  if(k == 1) {
    return s.substr(0, fib[k]) == "b" ? 0 : -1;
  }
  if(k == 2) {
    return s.substr(0, fib[k]) == "a" ? 0 : -1;
  }
  // [k-3] [k-2] [k-2] ?
  int f3 = fib[k-3];
  int f2 = fib[k-2];
  if(s.substr(f3,f2) == s.substr(f3 + f2, f2)) {
    int sub = mutual(k - 2, s.substr(f3, f2), s.substr(0, f3));
    if(sub >= 0) {
      return sub * 4 + 2;
    }
  }
  // [k-2] [k-3] [k-2] ?
  if(s.substr(0, f2) == s.substr(f3 + f2, f2)) {
    int sub = mutual(k - 2, s.substr(0, f2), s.substr(f2, f3));
    if(sub >= 0)
      return sub * 4;
  }
  // [k - 2] [k - 2] [k - 3] ?
  if(s.substr(0, f2) == s.substr(f2, f2)) {
    int sub = mutual(k - 2, s.substr(0, f2), s.substr(2 * f2, f3));
    if(sub >= 0)
      return sub * 4 + 1;
  }
  return -1;
}

void enumerate_few(void) {
  vector<vector<string> > dp(10);
  dp[0] = vector<string>(1, "b");
  dp[1] = vector<string>(1, "a");
  REP(i, 2, 6) {
    dp[i] = vector<string>(1 << (i - 1), "");
    REP(k, 0, 1 << (i - 1)) {
      if (k % 2 == 0) {
	dp[i][k] = dp[i - 1][k / 2] + dp[i - 2][k / 4];
      } else {
	dp[i][k] = dp[i - 2][k / 4] + dp[i - 1][k / 2];
      }
    }
    REP(k, 0, 1 << (i - 1)) {
      cerr << "dp[" << i << "][" << k << "]=" << dp[i][k] << endl;
    }
  }
  
}

int main(void){
  cin>>s;
  fib_init();
  //enumerate_few();
  if(s == "a") {
    cout << "2 0" << endl;
    return 0;
  }
  if(s == "b") {
    cout << "1 0" << endl;
    return 0;
  }
  if (s == "ab") {
    cout << "3 0" << endl;
    return 0;
  }
  if (s == "ba") {
    cout << "3 1" << endl;
    return 0;
  }
  int n = -1;
  REP(i,0,N) {
    if((int) s.length() == fib[i]) {
      n=i;
      break;
    }
  }
  cout << n << " " << rec(n) << endl;
}

Submission

Task問題 E - ab文字列
User nameユーザ名 こば@チーム戦の時は別垢を作れ!
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2721 Byte
File nameファイル名
Exec time実行時間 2 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 sample_01.txt,sample_02.txt,test_11_511.txt,test_13_2047.txt,test_15_8191.txt,test_16_16383.txt,test_18_65535.txt,test_1_0.txt,test_22_0.txt,test_22_1048575.txt,test_2_0.txt,test_3_0.txt,test_3_1.txt,test_4_3.txt,test_5_7.txt,test_6_15.txt,test_8_63.txt,sample_01.txt,sample_02.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
test_11_511.txt AC 1 ms 256 KB
test_13_2047.txt AC 1 ms 256 KB
test_15_8191.txt AC 1 ms 256 KB
test_16_16383.txt AC 1 ms 256 KB
test_18_65535.txt AC 1 ms 256 KB
test_1_0.txt AC 1 ms 256 KB
test_22_0.txt AC 2 ms 256 KB
test_22_1048575.txt AC 2 ms 256 KB
test_2_0.txt AC 1 ms 256 KB
test_3_0.txt AC 1 ms 256 KB
test_3_1.txt AC 1 ms 256 KB
test_4_3.txt AC 1 ms 256 KB
test_5_7.txt AC 1 ms 256 KB
test_6_15.txt AC 1 ms 256 KB
test_8_63.txt AC 1 ms 256 KB