忍者ブログ
29 March

[PR]

×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

27 April

SRM618 div2 easy,med

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13072
http://community.topcoder.com/stat?c=problem_statement&pm=13147

Easy

タップするとアルファベット順に進む携帯がある。
入力に対し何回タップすればいいか合計を返せ。

Med

1.全部大文字
2.同じ文字が連続しない
3.xyxyのような部分列が存在しない(x,y∈文字)
1~3を与えられた文字列が満たすかどうか返せ。

感想とか

Easy

文字コードで足してくだけ。

Med

スマートじゃなく雑に全探索しました。
http://ideone.com/MKkvRp
PR
27 March

SRM612 div2 500

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13041

smiles
個絵文字を入力したいとき、
・今入力されている絵文字を全部クリップボードへコピーする。
・クリップボードからペーストする。
の2種類の操作ができる。
操作する回数の最小値を求めよ。(絵文字は最初に1個入力されている)


感想

DFSが使えて嬉しかったので久々の更新w
(間違っているかもしれません。)


class EmoticonsDiv2 {

	public:
	int printSmiles(int smiles) {
		int ans;
		ans = dfs(1,2,smiles);
		return ans+2;
	}

	int dfs(int clip,int now,int goal){
		int ret = INF;

		if(now == goal)return 0;
		if(now > goal)return INF;
		for(int i=0;i<2;i++){
			if(i==1)ret = min(ret,dfs(clip,now+clip,goal)+1);
			if(i==0)ret = min(ret,dfs(now,now+now,goal)+2);
		}
		return ret;
	}
};

24 January

SRM605 div2 250,500

問題文

Easy

http://community.topcoder.com/stat?c=problem_statement&pm=12950
文字列Sのうちどこか1文字消すとき何通りの文字列ができるか。

Meidium

http://community.topcoder.com/stat?c=problem_statement&pm=12821

長方形の盤面が黒か白に塗られている。
1行分の色を反転する操作を何回かしたときにできる
最大の正方形の面積を求めよ。


感想

Easy

文字が変わった回数をカウントして、プラス1。

Medium

全探索で間に合うみたいだからごり押し。

Hard

解けません(´・ω・`)



#include<iostream>
#include<string>

using namespace std;

class AlienAndPassword{
public:
	int getNumber(string S){
		int cnt=0;
		for(int i=1;i<S.size();i++){
			if(S[i-1] != S[i]) cnt++;
		}
		return cnt+1;
	}
};


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

using namespace std;

class AlienAndGame{
public:
	int getNumber(vector<string> board){
		int MAX;
		int ans=1;
		MAX = min(board[0].size(),board.size());
		
		for(int length=1;length<=MAX;length++){
		
		for(int i=0;i<board.size()-length+1;i++){
			for(int j=0;j<board[0].size()-length+1;j++){
			
				int fuga=0;
				
				for(int k=0;k<length;k++){
					int hoge=0;
					for(int l=0;l<length-1;l++){
						if(board[i+k][j+l] == board[i+k][j+l+1])
							hoge++;
					}
					if(hoge+1==length)fuga++;
				}
				if(fuga==length)ans=length;
			}
		}}
		return ans*ans;
	}
};

19 January

SRM604 div2 500

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12952

ゴールである(x,y)座標が与えられる。
kターン目には上か右に3^k分進まなければならないとすると、(kは0から)
ゴールには辿り着けるか返せ。

感想

本番の時は2^kならXOR?とかで解けるのにとか思っていましたが、
3^kでも同じようなものだとChallengeの時に気づきました。


#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class PowerOfThreeEasy {

	public: string ableToGet(int x, int y) {
		while(1){
			if((x%3==0&&y%3==1)||(x%3==1&&y%3==0)){
				x/=3;
				y/=3;
			}
			else{
				if(x==0&&y==0)return "Possible";
				return "Impossible";
			}
		}
	}

};


12 January

SRM604 div2 easy

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12953

空でない文字列がいくつか渡される。
文字列を二分割してそれを入れ替えた時同じものに
なるものをカウントして返せ。

例:"tokyo","kyoto"
tokyo = to + kyo → kyo + to = kyoto
このようなのをカウント。

解法

Constraintsは文字列の数、文字列の長さがそれぞれ50である。
よって全探索でも50^3程度にしかならない。


反省

今回が本番初参戦だった。
開催が遅かったので30分寝過ごしてしまった。
練習の時、早く解くことを意識はしていたものの、時間制限を設けず
やっていたので本番で焦ってしまった。
初チャレンジもよく確認せず突っ込み-25点と
いろいろと惨敗だった。

なんだかんだやっぱり本番は楽しかったのでまた頑張りたい。



#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class FoxAndWord {

	public: int howManyPairs(vector<string> words) {
		int cnt=0;
		for(int i=0;i<words.size()-1;i++){
			for(int j=i+1;j<words.size();j++){

				if(words[i].size() == words[j].size()){
				for(int k=0;k<words[i].size();k++){
					if(words[i].substr(k+1) + words[i].substr(0,k+1) == words[j]){
						cnt++;
						break;
					}
				}}
			}
		}

		return cnt;
	}

};

        
  • 1
  • 2
  • 3