忍者ブログ
01 May

[PR]

×

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

09 January

SRM603 div2 easy

問題文


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

文字列"s"が与えられる。
・文字列の長さが奇数の時、その"s"の真ん中の文字を"t"の末尾に加え、"s"からは消す。
・文字列の長さが偶数の時、その"s"の真ん中の2つの文字の内小さい方を
"t"の末尾に加え、"s"からは消す。

この操作を"s"がなくなるまでやった時の"t"を返せ。


解法


指示された通りにコードを書いていけば大丈夫。
eraseとか使ってる時に、
コンパイルが1回で通るとビビるのを治したいw



#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#include<climits>
#include<string>

using namespace std;

class MiddleCode{
public:
	string encode(string s){
		string t;
		while(!s.empty()){
			if(s.size()%2 == 0){
				//even number
				if(s[s.size()/2-1]<s[s.size()/2]){
					t.push_back(s[s.size()/2-1]);
					s.erase(s.size()/2-1,1);
				}else{
					t.push_back(s[s.size()/2]);
					s.erase(s.size()/2,1);
				}
			}
			else{
				//odd number
				t.push_back(s[s.size()/2]);
				s.erase(s.size()/2,1);
			}
		}
		return t;
	}
};

PR
03 January

競技プログラミングまとめ

競技プログラミングコンテストまとめ

1.TopCoder

http://community.topcoder.com/tc
有名所。
詳しくはWikiとか見て下さい。
http://vipprog.net/wiki/TopCoder.html


2.CodeForces

http://codeforces.com/
あんまりやってないから、
これからやっていきたいと思う。


3.AtCoder

http://atcoder.jp/
英語のコンテストが多い中、日本の日本語のサイト。
初心者向けにもやってくれるので嬉しい。


4.Project Euler

http://projecteuler.net/
2,3問しか解いてないけど一応紹介。

答えだけ提出する感じ。
他のに比べて参加しやすいかも。
02 January

POH! Vol.1

paizaオンラインハッカソン Vol.1

問題文

https://paiza.jp/poh/ec-campaign



解法

全商品に対して、キャンペーン設定金額の内で最大になる対応を二分探索で探し、
その組み合わせの中でさらに最大値をとる。
最大ケースだとTLEになるかなと思ったけど、
大丈夫だったらしい。



#include<iostream>
#include<vector>
#include<functional>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstdlib>

using namespace std;

int binary_s(vector<int> v,int target);

int main(void){
    int N,D;
    vector<int> item;    //商品の値段
    vector<int> goal;    //キャンペーン設定金額
    scanf("%d%d\n",&N,&D);
    for(int i=0;i<N;i++){
        int a;
        scanf("%d\n",&a);
        item.push_back(a);
    }
    for(int i=0;i<D;i++){
        int a;
        scanf("%d\n",&a);
        goal.push_back(a);
    }
    //ここまで読み込み

    sort(item.begin(),item.end());//商品の値段順ソート
    
    for(int i=0;i<D;i++){    //キャンペーン設定金額ループ
        int ans = 0;
        
        if(item[0]+item[1]>goal[i])cout << 0 << endl;    //最低の商品2つの合計の値段が設定金額を超えていたら0
        else{
        //item[]:商品金額 goal[i]:キャンペーン設定金額 ans:最小値格納用

            for(int j=0;j<N;j++){
                if(item[j]>=goal[i])continue;
                int a = binary_s(item,goal[i]-item[j]);
                if(item[a] + item[j] == goal[i] && a!=j){
                    ans=item[a] + item[j];
                    break;
                }
                if(a==j)a-=1;
                if(item[a] + item[j]>goal[i])continue;
                ans = std::max(ans,item[j] + item[a]);            
            }
            cout << ans << endl;
        }
    }
    
    return 0;
}



int binary_s(vector<int> v,int target){
    int Mid=v.size()/2,Max=v.size()-1,Min=0;
    int PreMid = 0;
    while(Mid!=PreMid){
        PreMid = Mid;
        if(v[Mid] == target)return Mid;
        else if(v[Mid]>target){
            Max=Mid;
            Mid=(Max+Min)/2;
        }else{
            Min=Mid;
            Mid=(Max+Min)/2;
        }
    }
    
    if(target<v[Mid])return Mid-1;
    else return Mid;
}

31 December

SRM602 div2 easy

問題文


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

typocoderというコンテストではレーティングシステムがあって、
1200以上がbrownで、1200未満はcielと呼ばれる。
最初のレートが500の時、rating[]のようにレートが変化するとしたら、
何回brownとcielの間を移動したか返せ。


解法

普通に条件分けしてシミュレートしていったらできた。


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

using namespace std;

class TypoCoderDiv2{
public:
	int count(vector  rating){
		bool c=true;
		int cnt=0;
		for(int i=0;i<rating.size();i++){
			if(i==0){
			if(rating[i] >= 1200){c=true;cnt++;}
			else c=false;
			}
			else{
			if(c){
				if(rating[i]<1200){c=false;cnt++;}
			}
			else if(c==false){
			if(rating[i]>=1200){c=true;cnt++;}
			}
			}
		}
		return cnt;
	}
};
23 December

SRM601 div2 easy

問題文

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

bags[]の要素はそれぞれマンダリンオレンジの個数を表している。
このうちK個のbagsを友達に配る。
できるだけ公平に配るときに、一番多い人と一番少ない人の差を求めよ。

解法

ソートしてK番先の要素との差出して、最小をとる。


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

using namespace std;

class WinterAndMandarins{
public:
	int getNumber(vector <int> bags, int K){
	
		sort(bags.begin(),bags.end());
		int ret=INT_MAX;
		
		for(int i=0;i<=bags.size()-K;i++){
			ret = std::min(ret,bags[i+K-1]-bags[i]);
		}
		return ret;
	}
};