はやし屋

競技プログラミングのメモ きたない

AOJ 1156: Twirling Robot

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156

やるだけです

#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdlib>
using namespace std;

#define fr first
#define sc second

typedef pair < int , int > Pi;
typedef pair <  Pi , Pi  > Pii;
typedef priority_queue < Pii , vector < Pii > , greater < Pii > > Que;

int w , h;

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

bool isover(int y , int x){
  return (y < 0 || x < 0 || x >= w || y >= h);
}

int st[111][111];
int c[111];

int solve(){
  Que que;
  que.push(Pii(Pi(0,0),Pi(0,0)));
  int vis[111][111][4] = {};
  while(!que.empty()){
    Pii pi = que.top();que.pop();
    int cost = pi.fr.fr, dir = pi.fr.sc;
    int    y = pi.sc.fr,   x = pi.sc.sc;
    if(y == h-1 && x == w-1)return cost;
    if(vis[y][x][dir]++)continue;
    for(int i = 0 ; i < 4 ; ++i){
      int ndir = (dir+i)%4 ;
      int ny    = y + dy[ndir] , nx = x + dx[ndir];
      if(!isover(ny,nx)){
	que.push(Pii(Pi(cost + (st[y][x] == i ? 0 : c[i] ), ndir),Pi(ny , nx)));
      }
    }
  }
  return -1;
}

int main(){
  while(cin >> w >> h && (w|h)){
    for(int i = 0 ; i < h ; ++i)
      for(int j = 0 ; j < w ; ++j)
	cin >> st[i][j];
    for(int i = 0 ; i < 4 ; ++i) cin >> c[i];
    
    cout << solve() << endl;
  }

}

AOJ 1150: Cliff Climbing

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1150&lang=jp

Dijkstraっぽい

移動できるマスのおおまかな条件は、
"十字方向に移動すると考えた時3歩以内で行けるところ"でかつ"足の内側"
なのでテーブル使わなくても適当にforを回すとできる。

三項演算子使ったりrep使ったりするときたないです

#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdlib>
using namespace std;

#define fr first
#define sc second
#define reps(i,j,n) for(int i = j ; i < n ; ++i)
#define rep(i,n) reps(i,0,n)

typedef pair < int , int > Pi;
typedef pair <  Pi , Pi  > Pii;
typedef priority_queue < Pii , vector < Pii > , greater < Pii > > Que;

int w , h;

char st[111][111];

bool isover(int y , int x){
  return (y < 0 || x < 0 || x >= w || y >= h);
}

int dijkstra(Que&que){
  int vis[2][111][111] = {};
  while(!que.empty()){
    Pii pi = que.top();que.pop();
    int cost = pi.fr.fr,turn = pi.fr.sc;
    int    y = pi.sc.fr,   x = pi.sc.sc;
    if(st[y][x] == 'T')return cost;
    if(vis[turn][y][x]++)continue;
    const int s[] = {1,-3} , t[] = {3,-1};
    int ny , nx;
    reps(i,s[turn],t[turn]+1)reps(j,-2,2+1)
      if(abs(i)+abs(j)<=3)if(!isover(ny=y+j,nx=x+i))if(st[ny][nx]!='X'){
	    int x = st[ny][nx];
	    que.push(Pii(Pi(cost+(x=='T'?0:x-'0'),turn^1),Pi(ny,nx)));	    
      }
  }
  return -1;
}

int main(){
  while(cin >> w >> h && (w|h)){
    Que que;
    rep(i,h)rep(j,w){
      cin >> st[i][j];
      if(st[i][j] == 'S')rep(turn,2)que.push(Pii(Pi(0,turn),Pi(i,j)));
    }
    cout << dijkstra(que) << endl;
  }
  return 0;
}

PCK 2013 本選 4,6

ウッ頭が...

巨樹の刻み手
再帰でやると無限にやる場合の場合わけとかめんどくさそう

dpる

#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

#define ALL(a) a.begin() , a.end()
#define chmin(a,b) a=min(a,b)

int main(){
  int d , n;
  while(cin >> d >> n && (d|n)){
    int a[111] , e[111] , r[111]; 
    for(int i = 0 ; i < n ; ++i){
      cin >> a[i] >> e[i] >> r[i];
    }
    vector < vector < int > > dp(111,vector < int >(111,1<<28));
    dp[d][0] = 0;
    for(int D = d ; D > 0 ; --D){
      for(int E = 0 ; E <= 100 ; ++E){
	if(dp[D][E] != 1<<28){
	  for(int i = 0 ; i < n ; ++i){
	    if(E >= r[i]){
	      chmin(dp[max(D-a[i],0)][min(100,E+e[i])],dp[D][E]+1);
	    }
	  }
	}
      }
    }
    int ret = *min_element(ALL(dp[0]));
    if(ret == 1 << 28)cout << "NA" << endl;
    else cout << ret << endl;
  }
  return 0;
}


微生物発電
bitdpる
最初何もしなずidx+1する場合って無駄じゃねっと思ったが、
無駄じゃない場合があった(サンプル3)
forでやった方バグってしまった...

#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdlib>
using namespace std;

#define SQR(q) ((q)*(q))
#define add(a,b) (abs(a-(b)) * SQR(abs(a-(b))-30))

int n , w;
int bm[16] , bw[16];
int dp[1 << 16][16];

int solve(int idx, int bit){
  if(idx == n)return 0;
  if(~dp[bit][idx])return dp[bit][idx];
  int ret = solve(idx+1 , bit);
  for(int i = 0 ; i < w ; ++i){
    if(!((bit >> i)&1)){
      ret = max(ret,solve(idx+1 , bit | (1 << i))+add(bw[i],bm[idx]));
    }
  }
  return dp[bit][idx] = ret;
}

int main(){
  while(cin >> n >> w && (w|n)){
    for(int i = 0 ; i < n ; ++i)cin >> bm[i];
    for(int i = 0 ; i < w ; ++i)cin >> bw[i];
    memset(dp,-1,sizeof(dp));
    int ret = solve(0,0);
    cout << ret << endl;
  }
  return 0;
}

AOJ 0581: Gifts

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0581

逆にしてdpするのが良いと思って実装したが、既に訪れたとこどう管理するかわからなかったので、公式解説を見た。
http://www.ioi-jp.org/joi/2012/2013-yo/2013-yo-t6/review/2013-yo-t6-review.html
"許される寄り道の回数が最も大きい K = 3 の場合でも,前述の条件を満たす区画は最大でも 12 個しかない."
思いつかないですね...

forで書くとヤバそうだったのでメモ化再帰しました

#include<iostream>
#include<algorithm>
using namespace std;
  
#define rep(i,n) for(int i = 0 ; i < n ; ++i)
  
  
int dp[1<<12][54][54][4];
int h , w , k;
string st[54];
  
int dy[] = {0,-1,0,1};
int dx[] = {-1,0,1,0};
  
bool isover(int y , int x){
  return (y < 0 || x < 0 || x >= w || y >= h);
}
// ←↑こす0
  
// new , old
 
// 訪れたことがあるか
bool judge(int bit){
  int ny = 0 , nx = 0 ;
  for(int i = 0 ; i < 6 ; ++i , bit >>= 2){
    int dir = bit%4;
    ny += dy[dir] , nx += dx[dir];
    if(ny == 0 && nx == 0)return true;
  }
  return false;
}
  
int getMax(int y , int x , int sur , int bit){
  if(y == 0 && x == 0)return 0;
  
  if(dp[bit][y][x][sur] != -1 << 28)return dp[bit][y][x][sur];
  
  int vis = 0  , ret = -1 << 28;
  if(st[y][x] != '.' && !judge(bit))vis = st[y][x] - '0'; 
  
  for(int i = 0 ; i < 4 ; ++i){
    int nx = x + dx[i] , ny = y + dy[i];
    if(!isover(ny,nx)){
      if(st[ny][nx] != '#'){
	if(sur - (i>=2) >= 0){
	  ret = max(ret,getMax(ny,nx,sur-(i>=2),((1<<12)-1)&((bit<<2)+i)) + vis);
	}
      }
    }
  }
  
  return dp[bit][y][x][sur] = ret;
}
  
int main(){
  cin >> h >> w >> k;
  for(int i = 0 ; i < h ; ++i){
    cin >> st[i];
  }
  for(int i = 0 ; i < 1 << 12 ; ++i){
    for(int y = 0 ; y < 54 ; ++y){
      for(int x = 0 ; x < 54 ; ++x){
	for(int k = 0 ; k < 4 ; ++k){
	  dp[i][y][x][k] = -1 << 28;
	}
      }
    }
  }
  
    
  int ret = getMax(h-1,w-1,k,0);
  cout << ret << endl;
}

パソコン甲子園(PCK) 2013 (もうひとつの)本選 参加記

予選落ちの悲しみを引きずって参加
AC:1,2,3,5
0WA
で多分2,3位っぽい(?)。
本選行ってたら一桁ワンチャンあったかもしれない


1:相方が適当に書く

2:O(N*M*L)とかどんなアルゴリズム使うのと思ったらvectorで書いたソースが通ってしまった
よくよんだらこなした回数の合計が50000以下であってN*Mをvectorでやれば絶対減らせるじゃんってと解いたあと気づいて絶望した

3:多倍長掛け算とか実装せんくても桁取るの可能じゃねと思ってずっと考えてたが無理で多倍長書いた

5:相方が頑張ってビットシフトしてた


4:2,3の深読み(?)でだいぶ時間を食ってしまい残り20分ぐらいだった気がする
JOIで普通に出てきそうでこういう系書いたことある気がする楽勝とか思ってたら
しんでしてしまった
終わってから見れば見るほど簡単に見える

6:後から見たら溶けても良かった気がするパッと見典型bitdp


反省点
・やはり本選行きたかった
・余分な時間が多すぎた
・TLE明確にして(懇願)
・解く速さが遅い
・ミスがほぼ練習不足が原因
・このブログが見にくい
・6完出来ても良かった気が
など

上位に入れたのは良かったがやり残したこと多すぎのクソザコで実力不足を感じた


でも図書カードもらえる(と思う)ので良かった


ソースとかは後輩ブログに載っています
http://ei1333.blogspot.jp/2013/11/pck2013.html

パソコン甲子園2013 予選8問目 (AOJ 0283: Study Session)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0283

二分探索の添え字がずっとバグってて触れてなかった
データ多いからstaticしないとだめです
結局ソースみてしまったのでじぶんでバグらず速く実装したい...

#include<vector>
#include<set>
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

typedef multiset < int > :: iterator Itr;

int main(){
  int n , q;scanf("%d%d",&n,&q);
  static vector < int > score(n) , sorted;

  for(int i = 0 ; i < n ; ++i){
    scanf("%d",&score[i]);
    sorted.push_back(score[i]);
  }

  sort(sorted.begin(),sorted.end());

  multiset < int > leader;
  Itr it;
  while(q--){
    char order[11] ;
    int num ;
    scanf("%s %d",order,&num);

    if(*order == 'A'){
      leader.insert(score[num-1]);
    } else if(*order == 'R'){
      it = leader.lower_bound(score[num-1]);
      leader.erase(it);
    } else {

      int lb = 0 , ub = 1 << 28;
      while(lb != ub){
	int mid = (lb+ub)/2;
	int prv = 0 , loss = 0;

	for(it = leader.begin() ; it != leader.end(); ++it){
	  int p = lower_bound(sorted.begin(),sorted.end(),*it - mid) - sorted.begin();
	  loss += max(p - 1 - prv + 1  , 0);
	  prv   = upper_bound(sorted.begin(),sorted.end(),*it) - sorted.begin();
	}

	loss += max(n - 1 - prv + 1 , 0);

	if(loss <= num) ub = mid ;
	else lb = mid + 1 ;
      }
      if(lb != 1 << 28)printf("%d\n",lb);
      else puts("NA");
    }
  }
  return 0;
}

AOJ1320: City Merger

bitdp
遷移ちがってんのかなあって思ったら、
データが完全に含まれている場合とか見落としていた

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int mx = 15*22;

int main(){

  int n ;
  while(cin >> n && n) {

    vector < string > data(n);

    for(int i = 0 ;i < n ; ++i){
      cin >> data[i];
    }
    
    // compress

    vector < string > s; 
    for(int i = 0 ; i < data.size() ; ++i){
      bool can = true;
      for(int j = 0 ; j < data.size() ; ++j){
	if(i == j)continue;
	if(~data[j].find(data[i])){
	  can = false;
	}
      }
      //      cout << " can = " << can << " data = " << data[i] << endl;
      if(can)s.push_back(data[i]);
    }

    n = int(s.size());

    int cost[mx][mx] = {};
    for(int i = 0 ; i < n ; ++i){    
      for(int j = 0 ; j < n ; ++j){  
	if(i == j)continue;
	for(int k = min(s[i].size() ,s[j].size())  ; k >= 0 ; --k){
	  string a = s[i].substr(s[i].size() - k);
	  string b = s[j].substr(0,k);
	  if(a == b){
	    cost[i][j] = k;
	    break;
	  }
	}
      }
    }
    
    
    static int dp[1 << 15][17] ;
    
    for(int i = 0 ; i < 1 << 15 ; ++i){
      for(int j = 0 ; j < 17 ; ++j){
	dp[i][j] = 1 << 28;
      }
    }
    
    for(int i = 0 ; i < n ; ++i){
      dp[1 << i][i] = int(s[i].size());
    }
    
    for(int S = 0 ; S < 1 << n ; ++S){
      for(int i = 0 ; i < n ; ++i){
	if(dp[S][i] != 1 << 28){
	  for(int j = 0 ; j < n ; ++j){
	    if(!((S >> j) & 1)){
	      dp[S | 1 << j][j] = 
		min(dp[S | 1 << j][j] , dp[S][i] + int(s[j].size()) - cost[i][j]);
	    }
	  }
	}
      }
    }
    
    cout << *min_element(dp[(1 << n) - 1], dp[(1 << n) - 1] + 17 ) << endl;
  }
}