SRM628 div2

昨日SRM628がありました。627は寝過ごしするめだったので、結構久しぶりの参加でした。
結果はeasyのみの1完でした。medやり直したので保管しておきます。

easy

ビショップ(将棋の'角'みたいな動きするらしい)が、8*8の盤上の座標(r1,c1)から(r2,c2)に移動するための手数を求める、移動出来ない場所は-1を返す。

座標の差とか計算してごにょごにょと場合分けして解いた。
challengeの時に見たら、長くて難しそうなプログラム作ってる人もいた。

using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

class BishopMove {
public:
	int howManyMoves(int r1, int c1, int r2, int c2) {
		if(r1==r2&&c1==c2){
			return 0;			
		}
		else if(abs(r1-r2)==abs(c1-c2)){
			return 1;
		}else if((abs(r1-r2)+abs(c1-c2)) %2 !=0){
			return -1;
		}
		else return 2;
		
	}
};

med

「'(',')','{','}','[',']','X'」といった、3種類の開き・閉じ括弧と'X'で構成された50文字以下の文字列が与えられる。また、'X'の数は5個以内である。'X'はワイルドカードで、任意の括弧に置き換えることができる。
以上の条件を満たした括弧を消去していき、入力された文字列全て消せるならば"possible"を、ダメなら"impossible"を返す。
(ex: "{()}[]"->"possible"　　"{(X}"->"possible"　　"[(]]"->"impossible")

深さ優先を使って'X'を6種類全ての括弧に変化させてシュミレーションする。変換候補は6種類なのでO(6^n)となる。nは5以下なので余裕で間に合う。

using namespace std;
typedef long long ll;

class BracketExpressions {
public:
	string del(string s){
		string ret="";
		for(int i=0;i<s.size()-1;i++){
			if( (s[i]=='(' && s[i+1]==')') 
			||  (s[i]=='[' && s[i+1]==']') 
			||  (s[i]=='{' && s[i+1]=='}')){
				s[i]='a';
				s[i+1]='a';
			}
		}
		for(int i=0;i<s.size();i++) if(s[i]!='a') ret+=s[i];

		return ret;
	}

	string Do(string s){
			string bef;
		do{
			bef=s;
			s=del(s);
		}while(s.size() && !(bef==s));
		return s;		
	}

	bool flag=false;
	void dfs(int n,string now,string s){
		if(now.size()==s.size()){
			if(Do(now).size()==0)flag=true;
			return ;
		}
		if(s[n]=='X'){
			dfs(n+1,now+'{',s);
			dfs(n+1,now+'[',s);
			dfs(n+1,now+'(',s);
			dfs(n+1,now+'}',s);
			dfs(n+1,now+']',s);
			dfs(n+1,now+')',s);
		}
		else{
			dfs(n+1,now+s[n],s);
		}
		return ;
	}

	string ifPossible(string expression) {
		string s=expression;
		dfs(0,"",s);
		
		if(flag)return "possible";
		else return "impossible";
	}
};

まとめ

• medでアルゴリズムを要求されることは少ないと思っていたので、「greedyなんだろうなぁ」と決めつけてしまっていた。前もdpとか出てたし、そんなことはなかった。
• 今回翻訳サイトに頼らず解いてみたら、medの「'X'は5以内」の制約などにしっかり気付けた。誤読多いからこれからは自力でやる
• dfs書いたら一発でACしたのが嬉しかった、dfs力の高まりを感じる・・・
• 本番ではmed解けなかったのにYazaten->Yazatenになってしまった。これからはちゃんと解いてレート上がるように頑張りたい。