srm437

久しぶりのsrm、のはずだけど、今年からペースが落ちたので問題セット的には間は空いてない。
しかしまぁ緊張した。

div1:250 TheSwap

1 <= n <= 1000000, 1 <= k <= 10と妙に数字が小さいので一見して全探索の予感。
スワップを全通り試すと6C2 ^ 10になって当然終わらないけど、6桁の数字の並び替えはせいぜい6! = 720通りしかないので、(現在の数字の並び, 残りのswap回数)でメモってやれば6! * 10で楽勝じゃん。おおぅ。というわけで普通のメモ化再帰を書く。整数値のままswapするのが面倒で文字列で処理したので速度が不安だったけれど(n = 123456, k = 10)が一瞬で終わったのでそのまま提出。
ところがswapの処理でバグを発見したので久しぶりに再提出。ふー。。。
。。。と、落ち着きたい所だったのだけれど、再提出後にテストしてみるとなぜか修正前の結果が出てしまう。直ってない。実は今回新しい環境で参加していて、プラグインの設定を変更できておらずファイルが上書きされてしまっていたっぽい。うぇぇぇ。
というわけで、二度目の再提出でとんでもなく低い点数になってしまった。
ともあれ通って良かったです。

map<pair<int, int>, int> memo;

int rec(int n, int k) {
  pair<int, int> p(n, k);
  if (memo.count(p)) return memo[p];
  if (k == 0) return n;
  stringstream ss;
  ss << n;
  string s = ss.str();
  int ret = -1;
  for (int i = 0; i < s.size(); ++i) {
    for (int j = i + 1; j < s.size(); ++j) {
      if (i > 0 || s[j] != '0') {
        swap(s[i], s[j]);
        ret = max(ret, rec(atoi(s.c_str()), k - 1));
        swap(s[i], s[j]);
      }
    }
  }
  return memo[p] = ret;
}

class TheSwap {
public:
int findMax(int n, int k) {
  memo.clear();
  return rec(n, k);
}

passed system test 87.47

div1:500 TheInteger

greedyにやろうとして死亡。dpかメモ化再帰だったらしい。わからん。

opened

div1:1000 問題名すら覚えていない

編集距離っぽい文面だけ読んだ。

opened

というわけで、間を空けるとやっぱり良くないなというありがちな感想です。ただ今回の問題セットはなかなかgoodだったらしく、全failな赤・黄コーダーが頻発してたので（どうしてかは知らない、greedyに引っかかったんでしょうか）レーティングは予想より上昇。なぜか黄色が見えてきた！

1383 -> 1443