SRM628Div2

Easy

問題

r1, c1.r2,c2が与えられる。斜め移動のみ(チェスのビショップの動き)で(r1,c1)から(r2,c2)まで移動したい。最小の移動回数を求めよ(不可能な場合は-1)。

解法

予め、与えられた2つの座標が同じ座標の場合は0を返しておく。

dr =|r2 - r1|, dc = |c2 - c1|とおいた時、

dr = dcの時は1回で移動できる。そうでない時は、dr - dcが偶数ならば2回で移動できるが、奇数ならば移動できない(-1)。

コード

#include<algorithm>

using namespace std;

class BishopMove

{

public:

int howManyMoves(int r1, int c1, int r2, int c2)

{

if(r1 == r2 && c1 == c2)

return 0;

int r = abs(r2 - r1), c = abs(c2 - c1);

if((r - c) % 2)

return -1;

return r == c ? 1 : 2;

}

};

Mid

問題

括弧の対応が正しいかを判定せよ。ただし、Xは任意の括弧に置き換え可能であり、文字列中に5つまで登場する可能性がある。

括弧の対応が正しいとは、閉じ括弧より前に開き括弧があり、括弧の内側の文字列に関しても、括弧の対応が正しい事を言う。

解法

Xは5つ以下なので、全探索をする。

コード

システムテストで落ちた。

#include <algorithm>

#include <string>

using namespace std;

char d[] = {'{', '(', '[', '}', ')', ']'};

class BracketExpressions

{

string s;

bool check()

{

int a = 0, b = 0, c = 0;

for(int i = 0; i < s.length(); i++)

{

switch(s[i])

{

case '{': a++; break;

case '}': a--; break;

case '(': b++; break;

case ')': b--; break;

case '[': c++; break;

case ']': c--; break;

}

if(a < 0 || b < 0 || c < 0)

return false;

}

return !a && !b && !c;

}

bool dfs(int n)

{

if(n == s.length())

return check();

bool a = false;

if(s[n] == 'X')

{

for(int i = 0;i < 6; i++)

{

s[n] = d[i];

a |= dfs(n + 1);

}

s[n] = 'X';

}

else

a |= dfs(n + 1);

return a;

}

public:

string ifPossible(string expression)

{

s = expression;

return dfs(0) ? "possible" : "impossible";

}

};

Hard

問題

ちゃんと読んでない。

解法

多分DP

コード

書いてない