TopCoder SRM620 DIV1 MEDIUM - CandidatesSelection

Source

TopCoder SRM620 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

$N$ 人のメイド $0,1,\ldots, N-1$ と $M$ 個の技能 $0,1,\ldots,M-1$ がある.
各メイド $i$ が各技能 $j$ に対するスキルレベル $S_{i,j}$ が与えられる.
スキルレベルは $\verb|A|$ から $\verb|Z|$ までの $26$ 段階で $\verb|A|$ の方が良い.
最初メイドは $0,1,\ldots,N-1$ と番号順に並んでいる.
何回でも技能を $1$ つ選び,その技能が高いメイドの方が前に来るように並び替えることができる.
指定した技能のスキルレベルが同じメイドは,順番を入れ替えないように並び替える.
与えられたメイドの順番 $P$ に並び替えることができるかどうかを判定する問題.

解法

Ad-hoc.最後にソートする技能から順番に考える.
最後にソートする技能を決めると,$P$ の最初の方がスキルレベルが高くなるようにソートされていなくてはいけない.
逆にそうであれば,スキルレベルが一致するいくつかの区間に分割できて,それぞれの区間を同時に並び替えれば良い.
最後から $2$ 番目にソートする技能は,今度は各区間の最初の方がスキルレベルが高くなるようにソートされていなくてはいけなく,そうであれば,それでソートすることで区間が細切れになっていく.
区間を細切れにすることで自由度が減ることはない(区間が細かくなったことでソートできない技能ができることはない)ので,ソートしても良い技能があるならどんどんソートして,区間を細切れにしていけば良い.
その結果,全ての区間のメイドが,番号の順番通りになっていれば,並び替え可能ということになる.

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class CandidatesSelection {
public:
string possible(vector <string> s, vector <int> result) {
  int i, j, k;
  int N, M;
  vector<vector<int> > r, nr;
  vector<int> tmp;

  N = s.size();
  M = s[0].size();
  r.push_back(result);

  for(;;){
    int fg = 0;

    k = 0;
    rep(i,r.size()){
      REP(j,1,r[i].size()) if(r[i][j-1] > r[i][j]) k++;
    }
    if(k==0) return "Possible";

    rep(k,M){
      int dame = 0, modify = 0;
      rep(i,r.size()){
        REP(j,1,r[i].size()) if(s[r[i][j-1]][k] > s[r[i][j]][k]) dame = 1;
        if(s[r[i][0]][k] != s[r[i][r[i].size()-1]][k]) modify = 1;
      }
      if(dame || !modify) continue;

      fg = 1;
      nr.clear();
      rep(i,r.size()){
        tmp.clear();
        tmp.push_back(r[i][0]);
        REP(j,1,r[i].size()+1){
          if(j==r[i].size() || s[r[i][j-1]][k] != s[r[i][j]][k]){
            nr.push_back(tmp);
            tmp.clear();
          }
          if(j<r[i].size()) tmp.push_back(r[i][j]);
        }
      }
      r = nr;
    }
    
    if(!fg) break;
  }
  
  return "Impossible";
}

}

Current time: 2017年11月18日11時36分21秒
Last modified: 2014年05月11日03時36分40秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM620 SRM_Div1_Medium
トップページに戻る

Logged in as: unknown user (not login)

ログイン: