なんで僕の体はこんなにもボロボロなんだろう

oxx -25 202.27pts 312nd
1104->1109(+5)
チャレンジなんてしてなければ、チャレンジなんてしてなければ…orz

Codechef

とりあえずこれ話そう

DOUBLE

なんかどっかで文字列を二つに割ったら両方が同じ文字列になるようなものを最大の長さで回文中からとりだしたくて、N文字の任意の回文からはその最大の長さどれくらいになるんよって話。
まぁ全て同じアルファベットの回文が作りたい文字列の最大の長さのものを作れるものになるのは自明ですから、適当にやるだけです。

#include <cstdio>
int main() {
    int t; scanf("%d",&t);
    for (int i=0; i<t; i++) {
        int n; scanf("%d",&n);
        if (n&1) printf("%d\n",n-1);
        else printf("%d\n",n);
    }
}

PLAYFIT

ゴール数を二つ選んだ時にその差を云々する的な。
LISのDPをちょっと弄るとできます

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf LLONG_MAX/2
ll g[100000];
ll dp[100001];
int main() {
    int t; scanf("%d",&t);
    for (int ix=0; ix<t; ix++) {
        int n; scanf("%d",&n);
        for (int i=0; i<n; i++) scanf("%lld",&g[i]);
        fill(dp, dp+n, inf);
        ll res=0;
        for (int i=0; i<n; i++) {
            ll &a=*lower_bound(dp,dp+n,g[i]);
            ll &b=*(lower_bound(dp,dp+n,g[i])+1);
            if (b==inf) res=max(res,g[i]-dp[0]);
            a=g[i];
        }
        if (res>0) printf("%lld\n",res);
        else puts("UNFIT");
    }
}

PANSTACK

これもまぁDP
掲示板見ないと問題文が完全に読解できなかった

#include <cstdio>
#include <cstring>
#include <algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll dp[1000][1005];
int main() {
    int t; scanf("%d",&t);
    memset(dp, 0, sizeof(dp));
    dp[0][1]=1;
    for (int i=1; i<1000; i++) {
        for (int j=1; j<=1000; j++) {
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*j)%mod;
        }
    }
    for (int ix=0; ix<t; ix++) {
        int n; scanf("%d",&n);
        ll res=0;
        for (int i=1; i<=1000; i++) res=(res+dp[n-1][i])%mod;
        printf("%lld\n",res);
    }
}

PKU 1118

初等幾何できてない
猛省
ちょっとカンニングしてたかも

#include <cstdio>
#include <algorithm>
using namespace std;
int x[700], y[700];
int main() {
    int n;
    while (scanf("%d",&n)) {
        if (!n) break;
        for (int i=0; i<n; i++) scanf("%d%d",&x[i],&y[i]);
        int res=0, cnt;
        for (int i=0; i<n; i++) {
            for (int j=i+1; j<n; j++) {
                cnt=2;
                for (int k=j+1; k<n; k++) {
                    if (k==i||k==j) continue;
                    cnt+=((y[j]-y[i])*(x[k]-x[i])==(y[k]-y[i])*(x[j]-x[i]));
                }
                res=max(res,cnt);
            }
        }
        printf("%d\n",res);
    }
}

SRM 540

Medむずすぎw

RandomColoringDiv2

やるだけ

class RandomColoringDiv2 {
public:
   int getCount( int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2 ) {
        int cnt=0;
        for (int r=0; r<maxR; r++) {
            for (int g=0; g<maxG; g++) {
                for (int b=0; b<maxB; b++) {
                    if (abs(startR-r)>d2) continue;
                    if (abs(startG-g)>d2) continue;
                    if (abs(startB-b)>d2) continue;
                    if (abs(startR-r)<d1&&abs(startG-g)<d1&&abs(startB-b)<d1) continue;
                    cnt++;
                }
            }
        }
        return cnt;
   }
};

ImporantSequence

Div.1でも半分、Div.2はやばい感じにチャレンジやらシステムテストやらでみんな落としまくってたもの。
やばい、無理(~_~;)

FractionInDifferentBases

もうちょっとで出来た気がする。。。
循環小数のWikiにのってるんだけど基数Xで有限小数になるには分母Qを素因数分解したときの素因数がXの約数のみで構成されればよくて、それを利用する。
ちょっとここを理解間違えて素因数分解まではしたのに最後の数えるところを上手くできなかったコードがこれ。

class FractionInDifferentBases {
public:
    int isp[1000001];
    vector<ll> p, p2;
    void init() {
        memset(isp, 0, sizeof(isp));
        isp[0]=isp[1]=1;
        for (int i=2; i<1000001; i++) {
            if (!isp[i]) {
                p.push_back(i);
                for (int j=i*2; j<1000001; j+=i) isp[j]=1;
            }
        }
    }
   long long getNumberOfGoodBases( long long P, long long Q, long long A, long long B ) {
        init();
        int sz=p.size();
        ll r=1;
        for (int i=0; i<sz; i++) {
            ll c=0;
            while (Q%p[i]==0) {
                Q/=p[i]; c++;
            }
            if (c>0) {
                r*=p[i];
                p2.push_back(p[i]);
            }
        }
        ll cnt=0;
        sz=p2.size();
        if (r>B) return 0;
        if (r==1) return 0;
        for (ll i=(A/r+1)*r; i<=B; i+=r) {
            bool flag=true;
            ll x=i/r;
            for (int i=0; i<sz; i++) if (x%p2[i]==0) {
                flag=false;
                break;
            }
            if (flag) cnt++;
        }
        return max(0LL,B-A+1-cnt);
   }
};

そしてプラクティスでごにょごにょ・・・
こうすると通ります

class FractionInDifferentBases {
public:
    ll gcd(ll a, ll b) { return b?gcd(b,a%b):a; }
   long long getNumberOfGoodBases( long long P, long long Q, long long A, long long B ) {
        vector<int> isp(1000001,1);
        vector<ll> p;
        isp[0]=isp[1]=0;
        for (ll i=2; i<1000001; i++) {
            if (isp[i]) {
                p.push_back(i);
                for (ll j=i*2; j<1000001; j+=i) isp[j]=0;
            }
        }
        int sz=p.size();
        ll r=1, g=gcd(P,Q);
        Q/=g;
        for (int i=0; i<sz; i++) {
            if (Q%p[i]==0) {
                while (Q%p[i]==0) Q/=p[i];
                r*=p[i];
            }
        }
        r*=Q;
        return (B-A+1)-(B/r-(A-1)/r);
   }
};