SRM 476

まったく上がる気がしないDIV2な人。

• 300 行列回転してどうのこうの。ゲームにあったような気がする。行列を9個並べて最短のものを調べたが、他の人のコードを見て、min(r,R-r)+min(c,C-c)で余裕だった。
• 500 一瞬ナップザックかと思ったが、普通に貪欲法でおｋ。ところでバッジャーって何？
• 1000 全探索にて死亡。当たり前か。動的計画法らしい。500で動的計画法を思いつきながら、なぜか1000ではそのまま特攻した。1ケースだけTLEしてた。

Result

300: Passed System Test
500: Passed System Test
1000: Failed System Test
1079(+44)

300コード

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#include<complex>
#include<cstdlib>

#define INFTY 1000000
using namespace std;

class MatrixShiftings {
public:
  int minimumShifts(vector <string> matrix, int value) {
    int ret = INFTY;
    vector<string> ex_mt;
    for(int i = 0; i < matrix.size(); ++i){
      ex_mt.push_back(matrix[i]);
      for(int j = 0; j < 2; ++j){
	ex_mt[i] += matrix[i];
      }
    }
    for(int i = 0; i < matrix.size(); ++i){
      ex_mt.push_back(ex_mt[i]);
    }
    for(int i = 0; i < matrix.size(); ++i){
      ex_mt.push_back(ex_mt[i]);
    }

    //
    for(int i = 0; i < ex_mt.size(); ++i){
      for(int j = 0; j < ex_mt[i].size(); ++j){
	cout << ex_mt[i][j];
      }
      cout << endl;
    }
    
    for(int i = matrix.size(); i < ex_mt.size() - matrix.size(); ++i){
      for(int j = matrix[0].size(); j < ex_mt[0].size() - matrix[0].size(); ++j){
	if( ex_mt[i][j] - '0' == value ){
	  for(int y = 0; y < ex_mt.size(); y += matrix.size()){
	    for(int x = 0; x < ex_mt[0].size(); x += matrix[0].size() ){
	      int dist = abs(y-i)+abs(x-j);
	      ret = min( ret, dist );
	    }
	  }
	}
      }
    }
    if(ret==INFTY)ret = -1;
    return ret;
  }
};

500コード

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#include<complex>

using namespace std;
#define N 54
class Badgers {
public:
  int w[N+1][N];
  int feedMost(vector <int> hunger, vector <int> greed, int totalFood) {
    int n = (int)hunger.size();
    int ret = 0;
    for(int i = 1; i < n+1; ++i){
      for(int j = 0; j < n; ++j){
	w[i][j] = hunger[j] + (i-1) * greed[j];
      }
    }
    
    /*
    for(int i = 1; i < n+1; ++i){
      for(int j = 0; j < n; ++j){
	cout << w[i][j] << ' ';
      }
      cout << endl;
    }
    */

    for(int i = 1; i < n+1; ++i){
      sort(w[i],w[i]+n);
      int s=0;
      for(int j = 0; j < i; ++j){
	s+=w[i][j];
	if(s>totalFood){
	  break;
	}
	ret = max(ret, j+1);
      }
    }
    return ret;
  }
};