2011年12月29日木曜日

SRM 528結果


Easy(250): 183.84
Medium(500): Challenge Succeeded
Hard(1000): Opened
Challenge: +100 - 25 = +75
Total: 258.84
Rating: 863 -> 902 (+39)

ついに緑に戻って来ました!

今回はとんでもないチャレンジ回。
Easyはバグ埋め込んじゃって探すのに時間が掛かって死にました。
Mediumにひっかけが多すぎてやばかった。
サンプル通れば後はTLEだけ気にすればいいと思ってた自分がいました。


250:
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <iostream>
#include <sstream>
using namespace std;
class MinCostPalindrome {
  public:
    int getMinimum(string s, int oCost, int xCost) {
      int cost = 0;
      for (int i = 0; i < s.size(); i++){
        char A = s[i];
        char B = s[s.size() - i - 1];

        if (A == B && A != '?') continue;

        if (A == '?'){
          if (B == 'o'){
            cost += oCost;
            s[i] = 'o';
          }else if (B == 'x'){
            cost += xCost;
            s[i] = 'x';
          }else{
            int m = min(oCost, xCost);
            cost += m;
            if (m == oCost) s[i] = 'o';
            else s[i] = 'x';
          }
        } else if ((A == 'o' && B == 'x') || (A == 'x' && B == 'o')) return -1;
      }
      return cost;
    }
};

500: (コード未修正)
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <iostream>
#include <sstream>
using namespace std;
class Cut {
  public:
    int getMaximum(vector <int> eelLengths, int maxCuts) {

      int res = 0;
      int cur = maxCuts;
      for (int i = 0; i < eelLengths.size(); i++){
        if (eelLengths[i] % 10 == 0){
          if (eelLengths[i] / 10 - 1 <= cur) {
            res += eelLengths[i] / 10;
            cur -= eelLengths[i] / 10 - 1;
          }
        }
      }

      for (int i = 0; i < eelLengths.size(); i++){
        if (eelLengths[i] % 10 == 0) continue;
        int m = eelLengths[i] / 10;
        if (m <= cur){
          cur -= m;
          res += m;
        }else if (cur > 0){
          res += cur;
          cur = 0;
        }
      }
      return res;
    }
};

このコードは多分{10, 30}, 1で落ちます。
(10の倍数の処理に問題がある)


今回の自分的にChallengeで気になったポイントは、

  1. 10の倍数は切る回数が少なくて済む場合があるから別ルーチン
  2. {30, 20}, 1のような場合に30を切ってしまうと結果は1で終わるが20を切ると結果が2になるので実はeelLengthsは昇順ソートが必要
の2つです。
自分は1で2人落としましたが2がわかっていればもっと落とせたような気がします。



以上、チャレンジ回の報告でした

0 件のコメント:

コメントを投稿