Codeforces #106 (Div. 2)

Codeforces

練習として全問解いてみました

A問題

大きい順に使っていく貪欲法

k=gets.to_i
a=gets.split.map(&:to_i)
a=a.sort.reverse
t=0
ans=0
a.each{|s|
  break if t>=k
  t+=s
  ans+=1
}
ans=-1 if t<k && ans==12
p ans

B問題

変換してみて確認する．
基数が35より大きくなることがあるので注意

BASE="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
def getv(s)
  return BASE.index(s);
end
def convert(s,b)
  res=0
  0.upto(s.length-1){|i|
    return -1 if getv(s[i])>=b
    res*=b
    res+=getv(s[i])
  }
  return res
end
def check(a,b,r)
  return false if convert(a,r)==-1 || convert(b,r)==-1
  a=convert(a,r)
  b=convert(b,r)
  return false if a<0||a>=24||b<0||b>=60
  return true
end
a,b=gets.split[0].split(":")
ans=[]
for r in 2..100
  ans.push(r) if check(a,b,r)
end

if ans.length==0 then
  puts 0
elsif check(a,b,101) then
  puts -1
else
  ans.each{|i|
    puts i
  }
end

C問題

差が大きくなりすぎないように貪欲に使っていく
わたしは交互に取るという方法で解いた．

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <numeric>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;

typedef long long int lli;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)

int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1}; //左 上 右 下

typedef pair<int,int> P;
const int INF=0x20000000;
const double EPS=1e-8;
int n;
P a[111111];
int maxa;
int sum=0;
int dp[111111];
int main(){
	cin>>n;
	REP(i,n){
		cin>>a[i].first;
		a[i].second=i;
	}
	sort(a,a+n);
	//maxa=*max_element(a,a+n);
	int x=n/2;
	int y=n-x;
	//sum=accumulate(a,a+n,0);
	cout<<y<<endl;
	for(int i=0;i<n;i+=2){
		cout<<a[i].second+1<<" ";
	}
	cout<<endl;
	cout<<x<<endl;
	for(int i=1;i<n;i+=2){
		cout<<a[i].second+1<<" ";
	}
	cout<<endl;

}

D問題

区間DP

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#define REP(i,x)for(int i=0;i<(int)x;i++)
string in;

typedef long long lli;
const lli MOD=1000000007;
lli dp[701][701][3][3];
lli rec(lli s,lli e,lli left,lli right){
	lli ans=0;
	if(dp[s][e][left][right]>=0)
		return dp[s][e][left][right];
	if(s==e)return 1;
	//左側と右側と決める
	lli depth=0;
	lli exit=0;
	for(lli i=s;i<e;i++){
		if(in[i]=='('){
			depth++;
		}else{
			depth--;
		}
		if(depth==0){
			exit=i+1;
			break;
		}
	}
	//左に色を塗る
	for(lli i=1;i<3;i++){
		if(i==left)continue;
		ans=(ans+rec(exit,e,0,right)*rec(s+1,exit-1,i,0))%MOD;
	}
	//右に色を塗る
	for(lli i=1;i<3;i++){
		if(exit==e&&right==i)continue;
		ans=(ans+rec(exit,e,i,right)*rec(s+1,exit-1,0,i))%MOD;
	}
	return dp[s][e][left][right]=ans;
}
int main() {
	memset(dp,-1,sizeof(dp));
	cin>>in;
	cout<<rec(0,in.size(),0,0)<<endl;
	return 0;
}

E問題

KMP法

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define REP(i,x)for(int i=0;i<(int)x;i++)

string s,in;
int n,m;
vector<int> matching(){
	vector<int> ans(in.size(),99999999);
	vector<int> fail(in.size()); //KMPテーブル
	fail[0]=0;
	int st=0;
	for(int j=1;j<(int)in.size();j++){
		while(st>0&&in[j-1]!=in[st-1]){
			st=fail[st-1];
		}
		st++;
		if(in[j]!=in[st-1])fail[j]=st;
		else fail[j]=fail[st-1];
	}
	int i=0;
	for(int k=0;k<n;k++){
		while(i>=0&&s[k]!=in[i]){
			i=fail[i]-1;
		}
		if(i>=0)ans[i]=min(ans[i],k-i);
		if(i==(int)in.size()-1)break;
		i++;
	}
	return ans;
}
int solve(){
	if(in.size()==1)return false;
	vector<int> t1=matching();

	reverse(s.begin(),s.end());
	reverse(in.begin(),in.end());
	vector<int> t2=matching();
	REP(i,t2.size()){
		if(t2[i]<99999999)t2[i]=s.size()-t2[i]-1-i;
		//cout<<t2[i]<<endl;
	}
	reverse(s.begin(),s.end());
	for(int i=1;i<(int)in.size();i++){
		int j=in.size()-i;
		if(j-1>=0&&t1[i-1]<99999999&&t2[j-1]<99999999){
			if(t1[i-1]+i<=t2[j-1]){
				return true;
			}
		}
	}
	return false;
}
int main() {
	cin>>s;
	n=s.size();
	int ans=0;
	cin>>m;
	REP(i,m){
		cin>>in;
		ans+=solve();
	}
	cout<<ans<<endl;
	return 0;
}