夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

Codeforces#66 惨敗

プログラミング

いえ〜い！

いや、問題文の解読が…


とりあえず自分のコードね。

A

int c(int count, int max_k, int max_n, vector<int> log) {
	while (count < max_k) {
		if (log[0] >= 2) {
			count++;
			log[0] -= log[0]/2;
			max_n = max(max_n, count);
			continue;
		}
		if (log[1] >= 2) {
			count++;
			log[1] -= log[1]/2;
			max_n = max(max_n, count);
			continue;
		}
		if (log[2] >= 2) {
			count++;
			log[2] -= log[2]/2;
			max_n = max(max_n, count);
			continue;
		}
		break;
	}
	return max_n;
}
int main() {
	int x,y,z,k;
	cin >> x >> y >> z >> k;
	vector<int> log;
	log.push_back(x); log.push_back(y); log.push_back(z);
	int count = 1, max_n = 0;
	max_n = c(count, k, max_n, log);
	int ans = (int) pow(2, max_n); 
	cout << max_n << endl;
	return 0;
}

なんか敵をどれだけ分割できる数を求めるという謎問。

プレテスト４で終了。

B

int main() {
	int n; cin >> n;
	string s; int a;
	vector<string> ss; vector<int> aa;
	for (int i=0; i<n; i++) {
		cin >> s >> a;
		ss.push_back(s); 
		aa.push_back(a);
	}
	int m; cin >> m;
	int b;
	vector<int> bb;
	for (int i=0; i<n; i++) {
		cin >> b;
		bb.push_back(b);
	}
	string v; cin >> v;
	int my_score;
	
	for (int i=0; i<ss.size(); i++) {
		if (ss[i] == v) {
			my_score = aa[i];
		}
	}
	
	int min_r, max_r, temp;
	int min_s=100000000, max_s=0;
	if (n > m) {
		min_r = n;
		for (int i=0; i<m; i++) {
			temp = bb[i]+my_score;
			max_s = max(max_s, temp);
		}
		max_r = 0;
		for (int i=0; i<aa.size(); i++) {
			if (max_s < aa[i])
				max_r++;
		}
	} else if (n <= m) {
		for (int i=0; i<m; i++)
			min_s = min(min_s, bb[i]);
		min_s += my_score;
		for (int i=0; i<m; i++) {
			temp = bb[i]+my_score;
			max_s = max(max_s, temp);
		}
		min_r=n; max_r=0;
		for (int i=0; i<aa.size(); i++) {
			if (my_score == aa[i]) continue;
			if (min_s > aa.size()) n--;
		}
		for (int i=0; i<aa.size(); i++) {
			if (max_s < aa[i])
				max_r++;
		}
	}
	cout << max_r << " " << min_r << endl;
}

レースゲームの順位とかごちゃごちゃやる問題。

推測でなんとなく解いてみたけどプレテスト１で失敗。

D

int main() {
	int n, m, k; cin >> n >> m >> k;
	set<int> log; log.clear();
	int a, b, p=n;
	for (int i=0; i<m; i++) {
		cin >> a >> b;
		if (log.count(a) != 0 && log.count(b))
			continue;
		p--;
		log.insert(a); log.insert(b);
	}
	int ans;
	if (p-k-1 <= 0) {
		ans = 0;
	} else {
		ans = p-k-1;
	}
	cout << ans << endl;
	return 0;
}

なんか全部の都市をつなげようぜ！！！って問題。

頑張ったつもりでもプレテスト４で落ちる。


さてここからは拾ってきた正解コード

A

Pythonのコードだけど驚いた。

がんばって理解中。

x,y,z,k = map(int,raw_input().split())
x,y,z = sorted((x,y,z))
kx = min(x-1,k/3)
k -= kx
ky = min(y-1,k/2)
k -= ky
kz = min(z-1,k)
print (kx+1)*(ky+1)*(kz+1)

B

C++でバッドノウハウ満載のとっても読みにくいコード。

あとで解析予定。

#define all(a) a.begin(),a.end()
#define forn(i,n) for(int i=0;i<(n);++i)
#define fornn(i,n) for(i=0;i<(n);++i)
#define lng long long
#define SQ(a) ((a)*(a))
#define forv(i,v) for(int i=0;i<(int)v.size();++i)
#define mp make_pair
#define pb push_back
#define ABS(a) ((a)<0?-(a):(a))
#define iinf 1000000000
#define left asdleft

map<string,int> pts;
vector<pair<int,string> > src;
vector<int> bs;

int main(){
#ifdef __ASD__
    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
 
    int n;
    cin>>n;
    forn(i,n){
        char tmp[30];
        int p;
        scanf("\n%s%d",tmp,&p);
        pts[tmp]=p;
        src.pb(mp(-p,tmp));
    }
    bs.resize(n);
    bs.assign(n,0);
    int m;
    cin>>m;
    forn(i,m)
        cin>>bs[i];
    sort(all(bs));
    string vasya;
    cin>>vasya;
    int vp=pts[vasya];

    sort(all(src));
    forv(i,src)
        src[i].first*=-1;

    multiset<int> bset;

    int res1=0,res2=0;

    forv(i,bs)
        bset.insert(-bs[i]);
    bset.erase(bset.lower_bound(-bs.back()));
    for(int i=n-1;i>=0;--i){
        if(src[i].second==vasya)
            continue;
        int np=vp+bs.back()-src[i].first;
        if(src[i].second<vasya)
            --np;
        multiset<int>::iterator it=bset.lower_bound(-np);
        if(it==bset.end())
            break;
        bset.erase(it);
        ++res1;
    }
    res1=n-res1;

    bset.clear();
    forv(i,bs)
        bset.insert(bs[i]);
    bset.erase(bset.lower_bound(bs[0]));
    forn(i,n){
        if(src[i].second==vasya)
            continue;
        int np=-(src[i].first-(vp+bs[0]));
        if(src[i].second>vasya)
            ++np;
        multiset<int>::iterator it=bset.lower_bound(np);
        if(it==bset.end())
            break;
        bset.erase(it);
        ++res2;
    }
    ++res2;

    cout<<res1<<' '<<res2;

    return 0;
}

C

自分ではやってないし、問題文理解できてないけど…

バッドノウハウないぶんなんだか見てて安心します(笑)

int dp[102][102][26];
bool got[102][102][26];
int bonus[26][26];
char name[102];

int getDP(int len,int k,char c){
    int max = -1000000000;
    if(len+1 < k)   return max;
    if(got[len][k][c-'a'])  return dp[len][k][c-'a'];
    if(c == name[len]){
        for(char p = 'a';p<='z';++p){
            if(max < getDP(len-1,k,p) + bonus[p-'a'][c-'a']){
                max = getDP(len-1,k,p) + bonus[p-'a'][c-'a'];
            }
        }
    }
    else if(k>0){
        for(char p = 'a';p<='z';++p){
            if(max < getDP(len-1,k-1,p) + bonus[p-'a'][c-'a']){
                max = getDP(len-1,k-1,p) + bonus[p-'a'][c-'a'];
            }
        }
    }
    dp[len][k][c-'a'] = max;
    got[len][k][c-'a'] = 1;
    return max;
}

int main(){
    memset(got,0,sizeof got);
    memset(dp,0,sizeof dp);
    memset(bonus,0,sizeof bonus);
    for(int i=0;i<26;++i){
        got[0][1][i] = 1;
    }
    scanf("%s",name);
        got[0][0][name[0]-'a'] = 1;
    int k,n;
    scanf("%d%d",&k,&n);
    for(int i=0;i<n;++i){
        char a[4],b[4];
        scanf("%s%s",a,b);
        scanf("%d",&bonus[a[0]-'a'][b[0]-'a']);
    }
    int max = -1000000000;
    int len = strlen(name);
    for(int i=0;i<=k;++i){
        for(int c=0;c<26;++c){
            if(max < getDP(len-1,i,c+'a')){
                max = getDP(len-1,i,c+'a');
//              printf("%d %d %c %d\n",len-1,i,c+'a',max);
            }
        }
    }
    printf("%d\n",max);
    return 0;
}

D

こんなコードになるらしいです。

#define FOR(I,A,B) for(int I=(A);I<=(B);I++)
#define REP(I,N) for(int I=0;I<(N);I++)

// BEGIN CUT HERE
#include<string>
#include<list>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<utility>
#include<sstream>
#include<cstring>
#define ALL(X) (X).begin(),(X).end()
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef long long LL;
typedef vector<string> VS;

#define FORD(I,A,B) for(int I=(A);I>=(B);I--)
#define INF  ((int)1e9+7)
#define VAR(V,init) __typeof(init) V=(init)
#define FOREACH(I,C) for(VAR(I,(C).begin());I!=(C).end();I++)

//ll nwd(ll a,ll b) { return !b?a:nwd(b,a%b); }
inline int CEIL(int a,int b) { return a%b ? a/b+1 : a/b; }
template <class T> inline T sqr(const T&a) { return a*a; }

int n, m, k, t;
int w;

vector<vector<int> > G((int)1e6+7);

bool o[((int)1e6+7)];

int slots;

void dfs(int a)
{
        o[a] = 1;
        slots++;
        for(int i = 0; i < G[a].size(); i++)
        {
                int y = G[a][i];
                if (!o[y]) dfs(y);
        }
}

int main()
{
        w = 0;
        scanf ("%d %d %d", &n, &m, &k);
        
        for(int i = 0; i < m; i++)
        {
                int b1, b2;
                scanf("%d %d", &b1, &b2);
                b1--; b2--;
                G[b1].push_back(b2);
                G[b2].push_back(b1);
        }
        
        int lssp = 0;
        int tv = 0;
        int SL = 2;
        for(int i = 0; i < n; i++)
        {
                slots=0;
                if (!o[i]) 
                {
                        dfs(i);
                        lssp++;
                }
                
                if (G[i].size() == 0) tv++;
                
                if (slots>2) SL+=min(k-2, slots-2);
        }
        
        int tun =0; int dro = 0;
        if (lssp == tv || k==1)
        {
                //tun += lssp/2;
                dro += (n-1)/2;
        }else
        {
                //int kolka = lssp-tv;
                //tun += kolka - 1;
                //tun += min(SL, tv);
                tv -= min(tv, SL);
                if (tv>0)
                {
                        dro++;
                        tun += tv/2;
                        dro += (tv-1)/2;
                }
        }
        
        //printf("SL = %d, lssp = %d, tv = %d\n", SL, lssp, tv);
        
        w = dro;
        
        printf("%d", w);
        return 0;
}

よみにくすぐるｗｗｗ

E

もうノーコメント。。。

const int inf = 1000*1000*1000; 
#define CL(x,a) memset(x,a,sizeof(x)); 
#define ALL(v) (v).begin(),(v).end() 
#define PII pair<int,int> 
#define PDI pair<double,int> 
#define MP(a,b) make_pair(a,b) 
#define FOR(i,n) for(int i=0;i<n;i++) 
typedef long long LL; 
typedef vector<int> vi; 
typedef vector< vi > vvi; 
typedef vector< vector<PII > > vvpii; 

int n;
LL ar[100009],x;
set<LL> st;
bool isPrime(LL x)
{
        if (x % 2 == 0)
                return 0;
        for (LL i = 3; i*i <= x; i+=2)
        {
                if (x % i == 0)
                        return 0;
        }
        return 1;
}
int main() 
{ 
        scanf("%d%I64d",&n,&x);
        if (x == 2)
        {
                printf("0\n");
                return 0;
        }

        LL Min = inf;
        Min *= Min;
        for (int i=0;i<n;i++)
        {
                scanf("%I64d",&ar[i]);
                if (ar[i] == 1)
                {
                        printf("1\n");
                        return 0;
                }
                Min = min(ar[i],Min);
                st.insert(ar[i]);
        }
        if (Min > 2)
        {
                printf("-1");
                return 0;
        }
        int C = 1;
        for (int i=3;i<x;i+=2)
        {
                if (!isPrime(i))
                        continue;
                if (st.find(i) == st.end())
                {
                        printf("-1");
                        return 0;
                }
                C++; 
        }
        printf("%d",C);
        return 0; 
}

では。