SRM 470 Div2 Practice - kyuridenamidaのブログ

[Easy]250 LinearTravellingSalesman

問題文

全ての点を通る１本の直線(軸に平行でなくても良い)が存在するような点の集合が与えられる。(例えば{(1,1),(2,2),(3,3)}とか)

(X1,Y1)-(X2-Y2)間を移動するときに、|X1-X2|+|Y1-Y2| (まあ要するにマンハッタン距離)の時間かかる。

適切な頂点を選びながら移動した時に、全ての点を回るのに何分掛かるか。(始点はどこでもいい)

解法

＞全ての点を通る１本の直線(軸に平行でなくても良い)が存在するような点の集合

これかなり重要、読み落とすと終わる。絵を描いてみたら分かると思いますが、

このような条件下においては、X座標が最大(or最小)の点は、 Y座標も最大(最小or最小)となる。
このような条件下においては、マンハッタン距離の性質で途中の経路は無視できる。

よって、XとY座標が共に一番小さい点と、X座標とY座標が共に一番大きい点を結んでやると良い。

まああそんな感じです。

#include <algorithm>
#include <vector>
using namespace std;
#define all(a) a.begin(),a.end() 

class LinearTravellingSalesman {
public:
	int findMinimumDistance(vector <int> x, vector <int> y) {
		
		return *max_element(all(x)) - *min_element(all(x)) + 
			   *max_element(all(y)) - *min_element(all(y));
	}
};

[Medium]500 DoorsGame

問題文

AさんとBさんの２人がゲームをしている。N+1コの部屋がある、鍵付ドアで区切られている。

最初Aは1番目の部屋にいて、BはN+1番目の部屋にいる。真ん中の部屋にたどり着けたほうが勝ち。

さっき言った部屋と部屋の間にあるNコのドアの色が入力として与えられる(A-Pの16色)。

お互いは交互に色を選んでその色と一致するドアを開けていく(複数ある場合は全部)。

ドア開けてく。負けるのが分かってる人はできるだけ時間稼ぎする悪あがきする。

お互いが最適にプレイした時、何ターン目で終わるかを出力しろ。Aが勝つ場合は正,Bが勝つ場合は負の符号をつけて出力しろ。引き分ける場合は0を出力しろ。

貪欲法もしくは空けた部屋の数を状態に持つBitDPだと思ったけれど、といていない。

[Hard]1000 ActivateGame

問題文

なんか長方形平面が与えられる。数字とアルファベットで敷き詰められてて、アルファベットは9より大きい数を表すときの代わりみたいな感じ。

最初(0,0)が有効になっている。

有効になっているものの中で四方向に隣接するセルを１つさらに有効にすることができる。

有効したときに、その隣接するセルに書かれた数同士の絶対値が得点になる。

全ての点有効にしたところで終了するけど、得点を最大化したい。最大何点になるかという問題。

解法

最大全域木する。最終的に全点を繋ぐようにしたいから、最小全域木のアルゴリズムを弄って最大全域木にする。直感的にも貪欲法って考え方でたどり着ける。

int g(char c){
	if(c >= 'a') return 10 + c - 'a';
	else if(c >= 'A') return 36 + c - 'A';
	return c - '0';
}
struct NODE{
	int x,y,cost;
	NODE(int a,int b,int c){x = a , y = b , cost = c;}
};
bool operator < (const NODE &a,const NODE &b){
	return a.cost < b.cost;
}
class ActivateGame {
public:
	int findMaxScore(vector <string> grid) {

		bool ok[50][50] = {0};
		int W = grid[0].size() , H = grid.size();

		int ans = 0;
		priority_queue<NODE> Q;
		Q.push(NODE(0,0,0));
		while(Q.size()){
			NODE q = Q.top(); Q.pop();
			if(ok[q.x][q.y])continue;
			else ok[q.x][q.y] = true , ans += q.cost;
			if(q.y)Q.push( NODE( q.x , q.y-1 , abs(g(grid[q.y][q.x]) - g(grid[q.y-1][q.x])) ) );
			if(q.x)Q.push( NODE( q.x-1 , q.y , abs(g(grid[q.y][q.x]) - g(grid[q.y][q.x-1])) ) );
			if(q.y < H-1)Q.push( NODE( q.x , q.y+1 , abs(g(grid[q.y][q.x]) - g(grid[q.y+1][q.x]))) );
			if(q.x < W-1)Q.push( NODE( q.x+1 , q.y , abs(g(grid[q.y][q.x]) - g(grid[q.y][q.x+1]))) );
		}
		return ans;
	}
};