SRM 708 : Div1 easy BalancedStrings - 土下座しながら探索中

問題概要：
1以上100以下の整数Nが与えられる。
以下の条件を満たすサイズNの文字列の集合Sを１つ見つけよ。
条件を満たすようなものは必ず存在する。

条件 1. 集合Sの要素である文字列の長さは１以上100以下である。
条件 2. 集合Sの要素である文字列は英小文字aからzから構成される。
条件 3. 集合Sの安定度と不安定度は等しい。

集合Sの安定度と不安定度は以下のように定義される。

安定度. Sに属する全ての文字列 s の連続する同じ英小文字を１つにまとめた文字列s'の長さ-1の総和
例 : S = { "aabcccdd", "a", "abccdde" } の安定度は 3 + 0 + 4 = 7

不安定度. Sに属する異なる二つの要素 s, t について、共通に現れる英小文字のペアの数の総和
　例 : S = { "aabcccdd", "a", "abccdde" } の不安定度は 16
"aabcccdd" と "a" から 2
"aabcccdd" と "abccdde" から 2 + 1 + 6 + 4 = 13
"a" と "abccdde" から 1
よって 16

解法：

不安定度を決定した後に安定度をそれに合わせる方針をとる。
以下、うまく説明をまとめることができなかったのでコンテスト中の自分がどのように考えていったのかについて書きます。
~~~ コンテスト中
どうしようか。
まず次のようなサイズNの文字列の集合 { "a", "a", ..., "a" }を用意して、この安定度を増加させていく方針で考えてみようかな。
この段階で不安定度は N * ( N - 1 ) / 2 だから、N が最大のとき、つまり100 なら不安定度は 4950。
さて、後は要素の文字列を変更して安定度を調整しよう。
aを使うと不安定度が変わるから、まだ集合の中にない文字列を二つ選んで追加しよう。
{ "abcbc", "adedede", ..., "ayzyzyz" } みたいな感じでね。
文字列の長さは最大100だから、この方法を使えば一つの文字列で安定度を最大99まで上げることができるな。
一度使った英小文字は別の文字列では使えない (使うと不安定度が上がる) から、最大 25 / 2 = 12 の文字のペアを使えて、 12 * 99 = 1188までは自由に安定度を増加させれるな。
あれ、不安定度は4950だよな。
（安定度が足り）ないじゃん。
不安定度を減らさなきゃ。
じゃあ { "a", ..., "a", "b", ..., "b" } としようかな。
するとN = 100のときの不安定度は ( 50 * 49 / 2 ) * 2 = 2450。
残りの英小文字で作れる安定度の最大は 24 / 2 = 12 ペア * 99 = 1188。
まだ足りない。
...
{ "a", ..., "a", "b", ..., "b", "c", ..., "c", "d", ..., "d", "e", ..., "e" }はどうだろう。
N = 100 のとき不安定度は ( 20 * 19 / 2 ) * 5 = 950。
残りの英小文字で作れる安定度の最大は 21 / 2 = 10 ペア * 99 = 990。
これなら不安定度と安定度を同じにできる！

コード：

#include<bits/stdc++.h>

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

using namespace std;

class BalancedStrings {
public:

  int calcS(vector<string> vec) {
    int S = 0;
    rep(i,(int)vec.size()) {
      map<char,int> cnt;
      rep(j,(int)vec[i].size()) ++cnt[vec[i][j]];
      REP(j,i+1,(int)vec.size()) {
	rep(k,(int)vec[j].size()) {
	  S += cnt[vec[j][k]];
	}
      }
    }
    return S;
  }

  vector <string> findAny(int N) {
    vector<string> ret;
    rep(i,N) ret.push_back(string(1,(char)(('a'+i%5))));
    int sim = calcS(ret);
    rep(i,N) if( sim ) {
      char p = (char)('f'+i*2), q = (char)('g'+i*2);
      while( (int)ret[i].size() < 100 && sim ) {
	int len = ret[i].size();
	if( len & 1 ) {
	  ret[i] += string(1,p);
	  --sim;
	} else {
	  ret[i] += string(1,q);
	  --sim;
	}
      }
    }
    return ret;
  }
};