Croc Champ 2012 - Qualification Round

A.
前から数える。本番ではstring s[3000]としてRE

#include <iostream>
#include <string>
using namespace std;

string s[30000];

int main(){
    int n,ans = 0;
    cin>>n;
    for(int i = 0; i < n; i++)cin>>s[i];
    int f = 1;
    for(int i = 0,l = s[0].size(); i < l && f; i++){
        char c = s[0][i];
        for(int j = 1; j < n; j++){
            if(c!=s[j][i]){
                f = 0;
                break;
            }
            if(j==n-1)ans++;
        }
    }
    
    cout<<ans<<endl;
    
    return 0;
}

B.
r_nとして考えられる数字は高々10000通りなので、10000回回してから周期を調べる。

#include <iostream>
using namespace std;


int main(){
	int a,b,m,r,ans = 1;
	cin>>a>>b>>m>>r;
	
	for(int i = 0; i < 10000; i++)r = (a*r+b)%m;
	
	int initial = r;
	while(initial != (r = (a*r+b)%m))ans++;
	
	cout<<ans<<endl;
	
	return 0;
}

C.
実装するだけ。本番ではAと同じく1桁間違えてWA

#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;

int t[100000],res[100000],n,m;
pair<int,int> x[100000];

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0; i < n; i++){
        scanf("%d%d",t+i,&x[i].first);
        x[i].second = i;
    }
    
    int time = 0,pos = 0;
    for(int i = 0; i < n; i+=m){
        int b = i+m>n?n:i+m;
        time = max(time,t[b-1]);
        sort(x+i,x+b);
        
        int a1,a2;
        a1 = i,a2 = i;
        while(a2 < b && x[a1].first == x[a2].first)a2++;
        
        while(a1!=a2){
            time += x[a1].first - pos;
            for(int j = a1; j < a2; j++){
                res[x[j].second] = time;
            }
            pos = x[a1].first;
            time += 1+(a2-a1)/2;
            a1 = a2;
            while(a2 < b && x[a1].first == x[a2].first)a2++;
        }
        time += x[b-1].first;
        pos = 0;
    }
    
    printf("%d",res[0]);
    for(int i = 1; i < n; i++){
        printf(" %d",res[i]);
    }
    puts("");
    return 0;
}

D.
前計算するだけ。ζ(2) = (π^2)/6 ≒ 1.7なので、前計算も足し算も大体O(n)となります。

#include<iostream>
typedef long long ll;
using namespace std;

int d[10000001];

int main(){
	for(int i = 2; i*i <= 10000000; i++){
		for(int j = 1; j*i*i <= 10000000; j++){
			d[j*i*i] = j;
		}
	}
	ll ans = 0;
	int a,n;
	cin>>a>>n;
	for(int i = 0; i < n; i++){
		ans += d[a+i]?d[a+i]:a+i;
	}
	cout<<ans<<endl;
	return 0;
}

E.
読んだ