cafelier@SRM

SRM 531 Div2 250

AS | 14:16 |

今日からここは、とりあえずdiv2 250をターゲットにコードの自動生成の可能性を探る日記になりました。解答例はとりあえずどうでもよくて、解の機械生成ができそう＆＆問題文からの(アルゴリズム的思考完全不要で)直訳で作れそう、なspecを色々書いてみながら言語設計するのが目標。

問題

main(
    s : int<1..100>[1..50]
) {
   let ps = all_permutations(s)
   let pps = ps - {s}
   if #pps == 0
      {- vector<int>() -}
   else
      min(lex, pps)
}

解答例

vector<int> getUnsorted(vector<int> s) {
    sort(s.begin(), s.end());
    if( !next_permutation(s.begin(), s.end()) )
       return vector<int>();
    return s;
}

SRM 530 Div2 250

AS | 15:29 |

問題

main(
   T : int<0..10>[2..10],
   strict_sorted(T)
) {
   let pT = all_permutations(T)
   let spT = map(pT, move(T,_1))
   max(spT)
}

move(T, S) {
   sigma(zip(T, S, abs(_1 - _2))) / 2
}

解答例

int solve(vector <int> T)
{
   int maxMove = 0;

   vector<int> S = T;
   sort(S.begin(), S.end());
   do {
      int dif = 0;
      for(int i=0; i<S.size(); ++i)
         dif += abs(S[i]-T[i]);
      maxMove = max(maxMove, dif/2);
   } while( next_permutation(S.begin(), S.end()) );
 
   return maxMove;
}

微妙。sigma(zip(T, S, abs(_1 - _2))) / 2 が問題文の仕様に合っているというのは何一つ自明ではない。といって問題の仕様どうやって記述しきればいいのかな…。

reverse(S.begin(), S.end());
int dif = 0;
for(int i=0; i<S.size(); ++i)
    dif += abs(S[i]-T[i]);
return dif/2;

この解はとりあえず導けなくていいや。