Into the Horizon

programming, photography, and daily log

Codeforces #94 Div2 Only (11/15)

提出コードを公開するようにすれば、少しはきれいなコードを書く癖がつくかなという思いで、恥ずかしいですが晒していきます。思考プロセスも然り。
とりあえず黄色くなるのが当分の目標。


A. Cookies
問題:クッキーの入った袋がいくつかある。袋を1つ抜いた時、残りのクッキーを2人で等分できる=偶数であるような袋の抜き方の総数を求める

  • やるだけ
  • 残りの袋を袋毎に分けた時、クッキーの個数が等分できるようにする問題だと思ってちょっとタイムロス

B. Students and Shoelaces

  • 問題の意味が…。なんで靴ひもで遊んでるの??流行ってんの??
  • てきとーに解釈して出したらpretest通った。ので無視してたらSystem落ちた。 orz

C. Statues
問題:8x8マスのボードの右上にA、左下にMがいる。Mは毎ターン周囲の8方向に移動orその場に留まるの9つの行動をとれる。ボードにはSも配置しており、Sは毎ターンMが行動した後に1つ下のマスに移動してくる。MはAまで辿り着ければ勝利、Sと同じマスになったら敗北である。Mが勝利できるか出力せよ。

  • 問題の意味を完全に勘違いして実装して1 Wrong
  • 把握。Mが取りうる全ての行動をシミュレートしても余裕で間に合うので、全探索。最近探索書いてなくて実装が遅い。反省
    • 探索遅いとか致命的でしょ…と思いつつ、最近必要とされる問題に出会ってないなあと。

D. String
問題:与えられた文字列の全ての部分文字列(重複も含む)を辞書順に並べて前から数えたときのk番目の文字を答えよ

  • え、やるだけじゃんww 簡単…と思ったのも束の間、普通に計算が間に合わないのか
  • 考えれば十分できそうだけれど、前半時間使いすぎた。ここでタイムアップ
  • 後からやってみたら、そこまで簡単でもなかった。ですよねー


以下ソースコード(一部)


A. Cookies

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#include <list>
#include <math.h>
#include <numeric>
#include <cstring>
using namespace std;

#define INF 99999999
#define rep(i,start,m) for(int i=(int)(start);i<(int)(m);i++)
#define showarray(array,m) for(int sa_i=0;sa_i<(int)(m);sa_i++) cout << array[sa_i] << " "; cout << endl;
#define showvector(array) for(int sa_i=0;sa_i<(int)(array.size());sa_i++) cout << array[sa_i] << " "; cout << endl;
stringstream ss;
#define cast(a,b) ss.clear(); ss<<a; ss>>b; ss.clear();
#define rev(s) (string((s).rbegin(), (s).rend()))
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;
#define clr(a) memset((a), 0 ,sizeof(a))

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


int n;
int dat[200];
int even,odd,all;
int main () {
	cin >> n;
	rep(i,0,n){
		cin >> dat[i];
		all += dat[i];
		if(dat[i]%2==0){
			even++;
		}else{
			odd++;
		}
	}
	if(all%2 == 0){
		cout << even << endl;
	}else{
		cout << odd << endl;
	}
}


C. Statues

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#include <list>
#include <math.h>
#include <numeric>
#include <cstring>
using namespace std;

#define INF 99999999
#define rep(i,start,m) for(int i=(int)(start);i<(int)(m);i++)
#define showarray(array,m) for(int sa_i=0;sa_i<(int)(m);sa_i++) cout << array[sa_i] << " "; cout << endl;
#define showvector(array) for(int sa_i=0;sa_i<(int)(array.size());sa_i++) cout << array[sa_i] << " "; cout << endl;
stringstream ss;
#define cast(a,b) ss.clear(); ss<<a; ss>>b; ss.clear();
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;
#define clr(a) memset((a), 0 ,sizeof(a))

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

vector<string> downSs(vector<string> board){
	bool empty = false;
	rep(i,0,8){
		rep(j,0,8){
			int y = 7-i;
			int x = j;
			if(board[y][x]=='S'){
				empty = true;
				if(y==7){
					board[y][x]='.';
				}else{
					if( board[y+1][x]=='M' ){
						board[0][0]='*';
						return board;
					}
					board[y+1][x]='S'; board[y][x]='.';
				}
			}
		}
	}
	if(not empty){
		board[0][0]='W';
		return board;
	}
	return board;
}

void showboard(vector<string> board){
	rep(i,0,8){
		cout << board[i] << endl;
	}
}


bool dfs(vector<string> board, int x, int y, int depth){
	//cout << x << " " << y << " " << depth << endl;
	//showboard(board);
	
	int tx,ty;
	rep(i,0,9){
		tx = x + dx[i]; ty = y+dy[i];
		if(tx>7 or ty>7 or tx<0 or ty<0) continue;
		if(board[ty][tx]=='S') continue;
		if(board[ty][tx]=='A'){
			//cout << "WIN" << endl;
			return true;
		}
		//debug(tx);debug(ty);
		vector<string> tmp = board;//大丈夫?
		tmp[y][x] = '.'; tmp[ty][tx] = 'M';
		tmp = downSs(tmp);
		if(tmp[0][0] == '*'){
			//cout << "LOSE" << endl;
			continue;
		}else if(tmp[0][0] == 'W'){
			//cout << "WIN" << endl;
			return true;
		}
		//debug(tx);debug(ty);
		if(dfs(tmp,tx,ty, depth+1)){ //勝ったなら
			return true;
		}
	}
	return false;
}




int main () {
	string tmp;
	vector<string> board;
	rep(i,0,8){
		cin >> tmp;
		board.push_back(tmp);
	}
	
	if(dfs(board,0,7,1)){
		cout << "WIN" << endl;
	}else{
		cout << "LOSE" << endl;
	}
	
	
}