SRM 468 :: DIV2

とりあえず500ptと1000pt

Level Two - T2

T2
問題概要
独自の携帯電話があって、ボタンが9つある。
例えば、
{"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
1番　空文字
2番　a,b,cのうち任意の1文字
3番　d,e,fのうち任意の1文字
…
のように表現される。
次のような文字列　223　が与えられたとき、
独自の携帯電話では、
(abc)(abc)(def)
1文字目はa,b,cのうち任意の1文字
2文字目はa,b,cのうち任意の1文字
3文字目はd,e,fのうち任意の1文字
よって表現される文字列はaad,aae,aaf,abd,…のように3^3 = 27通りある。
さらに辞書のデータが与えられる。
表現できる文字列のうち辞書にある文字列しか表現できない決まりになっている。
表現できる文字列が辞書に複数あった場合は文字の昇順が優先される。
特殊なボタンとして　'#' , '*' の2文字があり、
'#'は文字列の昇順のうち次の文字列を指す
'*'は'#'が5つあることと同じである。
上記の独自携帯で、辞書データが {"aad","aae"}　なら、
223 -> aad
223# -> aae
となる。
ボタン番号と'#','*'からなる文字列が与えられたとき、表現される文字列を求める問題。
ボタン番号が0のときはスペースを出力する。

system test pass

class T9{
public:
  string message(vector<string> part, vector<string> dict, vector<string> keystr)
  {
    char moji[256];
    for(int i=0; i<part.size(); i++){
      for(int j=0; j<part[i].size(); j++){
        moji[part[i][j]] = i+1;
      }
    }
    
    map<string, string> mss;
    for(int i=0; i<dict.size(); i++){
      string num;
      for(int j=0; j<dict[i].size(); j++){
        num += char(moji[dict[i][j]]+'0');
      }
      //cout << dict[i] << "___" << num << endl;
      mss[dict[i]] = num;
    }
    string key;
    for(int i=0; i<keystr.size(); i++)key += keystr[i];
    
    string ans;
    string number;
    int flag = 0;
    for(int i=0; i<key.size(); i++){
      if( key[i]=='0' ){
        if( flag ){
          map<string,string>::iterator it;
          for(it=mss.begin(); it!=mss.end(); it++){
            if( it->second == number ){
              ans += it->first;
              break;
            }
          }
          flag = 0;
        }
        ans += ' ';
        number = "";
      }else if( '1'<=key[i] && key[i]<='9' ){
        number += key[i];
        flag = 1;
      }else{
        int cnt = 0;
        for(; key[i]=='#'||key[i]=='*'; i++){
          if( key[i]=='#' )cnt++;
          else if( key[i]=='*' )cnt+=5;
        }
        i--;
        map<string,string>::iterator it;
        int uguu = 0;
        for(it=mss.begin(); it!=mss.end(); it++){
          if( it->second == number ){
            uguu++;
            if( uguu <= cnt )continue;
            ans += it->first;
            break;
          }
        }
        number = "";
        flag = 0;
      }
    }
    if( flag ){
      map<string,string>::iterator it;
      for(it=mss.begin(); it!=mss.end(); it++){
        if( it->second == number ){
          ans += it->first;
          break;
        }
      }
    }
    return ans;
  }
};

Level Three - Gifts

Gifts
問題概要
長方形のマップと、最大移動量が与えられる。
'.' - 移動可能な場所
'#' - 壁
'K' - スタート
'Q' - ゴール
'G' - ギフト
各文字は上記のようになっている。
移動は上下左右の4方向である。
スタート地点からゴール地点まで、最大ステップ数内で'G'を最大で何個集められるか、という問題である。
ただし、'G'は拾う度に1ステップに(g+1)の移動量が必要になる。
'G'がある場所に移動しても、'G'を拾うかどうかを選択することができる。

TLEなすぱげってぃコード
Kの位置から各'G'までの最短歩数、
各'G'からその他の'G'までの最短歩数を記録してから、DFS+枝刈りのコード。

int G[32][32];
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
int inf = 50*50*50;
int W,H;
int ans;
int visit[32];
int uzee[(1<<17)][17];

class Gifts
{
public:
  void dfs(int gn, int now, int tcost, int gnum, int T, int uguu)
  {
    //printf("gn:%d , tcost:%d, gnum:%d, ans:%d\n",gn,tcost,gnum,ans);
    if( ans==gn-1 )return;
    if( tcost > T )return;
    if( now==gn ){
      if( ans < gnum )ans = gnum;
      return;
    }
    if( tcost+G[now][gn-1]*(gnum+1) > T )return;
    if( uzee[uguu][now] <= tcost+G[now][gn-1]*(gnum+1) )return;
    uzee[uguu][now] = tcost+G[now][gn-1]*(gnum+1);
    
    for(int i=0; i<gn; i++){
      if( G[now][i]==0 || visit[i] )continue;
      visit[i] = 1;
      dfs(gn, i+1, tcost+G[now][i]*(gnum+1), gnum+(i+1!=gn?1:0), T, uguu|(1<<i) );
      visit[i] = 0;
    }
    
    return;
  }
  int maxGifts(vector<string> city, int T)
  {
    W = city[0].size();
    H = city.size();
    int cnt = 1;
    int gx,gy;
    
    for(int i=0; i<H; i++)
      for(int j=0; j<W; j++)
        if( city[i][j]=='Q' )gx=j,gy=i;
        
    
    for(int i=0; i<H; i++){
      for(int j=0; j<W; j++){
        if( city[i][j]=='K' || city[i][j]=='G' ){
          queue<int> xq,yq;
          xq.push( j );
          yq.push( i );
          int memo[50][50];
          
          for(int a=0; a<H; a++)
            for(int b=0; b<W; b++)
              memo[a][b] = inf;    
          memo[i][j] = 0;
          
          while( !xq.empty() ){
            int nx = xq.front();
            int ny = yq.front();
            int nc = memo[ny][nx];
            for(int k=0; k<4; k++){
              int tx = dx[k] + nx;
              int ty = dy[k] + ny;
              if( tx<0 || ty<0 || tx>=W || ty>=H ||
                  city[ty][tx]=='#' || memo[ty][tx]<=nc+1 )
              {
                continue;
              }
              memo[ty][tx] = nc + 1;
              xq.push( tx );
              yq.push( ty );
            }
            xq.pop(); yq.pop();
          }
          
          int c = 0;
          for(int a=0; a<H; a++)
            for(int b=0; b<W; b++)
              if( city[a][b]=='G' ){
                G[(city[i][j]=='K'?0:cnt)][c++] = memo[a][b];
              }
          
          G[(city[i][j]=='K'?0:cnt)][c++] = memo[gy][gx]; //quine
          if( city[i][j]=='G' )
            cnt++;
        }
      }
    }
    /*
    for(int i=0; i<10; i++){
      for(int j=0; j<10; j++){
        printf("%d ",G[i][j]);
      }
      puts("");
    }
    printf("cnt: %d\n",cnt);
    */
    for(int k=0; k<17; k++)
      for(int i=0; i<(1<<17); i++)uzee[i][k] = inf;
    dfs(cnt, 0, 0, 0, T, 0);
    
    return ans;
  }
};