読者です 読者をやめる 読者になる 読者になる

SRM 702 Div1

Easyしか解いてないがsystestで落ちた。

 結局貪欲に決めていくだけなんだが、行を固定するときに移動元・移動先を固定しないといけなくてそれができてなかった。
 具体的には下のコードのused3のところ。

class GridSortMax {
    public:
    bool used[51];
    bool used2[51];
    bool used3[51];
    string findMax(int n, int m, vector<int> grid) {
        vector<vector<int>> fld(n, vector<int>(m, 0));
        for(int i : in(n))
          for(int j : in(m))
            fld[i][j] = grid[i * m + j];
        memset(used, 0, sizeof(used));
        memset(used3, 0, sizeof(used3));
        vector<int> fixed(m, -1);
        string ans = "";
        for(int i : in(n)) {
            pair<string, int> res(string(m, '.'), -1);
            for(int j : in(n)) if(!used[j]) {
                string tmp(m, '0');
                for(int k : in(m))
                  if(i * m + 1 <= fld[j][k] && fld[j][k] <= i * m + m) {
                      int id = fld[j][k] - (i * m + 1);
                      if(fixed[id] != -1) {
                          if(fixed[id] == k) tmp[id] = '1';
                      }
                      else if(!used3[k]) {
                          tmp[id] = '1';
                      }
                  }
                res = max(res, make_pair(tmp, j));
            }
            ans += res.first;
            int j = res.second;
            if(res.first != string(m, '0')) used[j] = true;
            for(int k : in(m)) if(!used3[k])
              if(i * m + 1 <= fld[j][k] && fld[j][k] <= i * m + m) {
                  int id = fld[j][k] - (i * m + 1);
                  if(fixed[id] == -1 && !used3[k])
                    fixed[id] = k, used3[k] = true;
              }
            int cntfix = 0, memo = -1;
            memset(used2, 0, sizeof(used2));
            for(int id : in(m)) {
                if(fixed[id] == -1) cntfix++, memo = id;
                else used2[fixed[id]] = true;
            }
            if(cntfix == 1) {
                for(int k : in(m)) if(used2[k] == false) fixed[memo] = k;
            }
        }
        return ans;
    }
};

 コードが汚なすぎて笑う。
スマートに解いている人もいたが、コードを見ても何をしているのかよくわからなかった。
 レートは1210。ついにDiv1ギリギリに来てしまった……。