CODE THANKS FESTIVAL 2014 A日程に参加しました

来年は予選通らねば...

結果

6完+部分点で630点7位

コンテスト

A問題

開始から5秒ぐらい問題が閲覧できなかったけどあれは何だったんだろう

int A,B;
int main() {
    cin>>A>>B;
    cout<<A*4+2*B<<endl;
    return 0;
}
B問題

A→B→Cの順に固定だと思ってた
マイナスにしてソートするの便利

int N;
int A[3];
int main() {
    cin>>N;
    cin>>A[0]>>A[1]>>A[2];
    int sum =0;
    int ans =0;
    int count=0;
    rep(i,3) A[i]=-A[i];
    sort(A,A+3);
    rep(i,3) A[i]=-A[i];

    while(1) {
        sum+=A[count];
        ans++;
        count++;
        count%=3;
        if(sum >= N) break;
    }
    cout<<ans<<endl;
    return 0;
}
C問題
int N,M;
int P[102];
int S[102];
int main() {
    cin>>N>>M;
    rep(i,N) cin>>P[i];
    rep(i,M) cin>>S[i];
    int ans = 0;
    rep(i,M) ans+=P[S[i]-1];
    cout<<ans<<endl;
    return 0;
}
D問題

if書いてる途中でmax,min使えば出来そうなことに気付いたけどそのままifで提出した

int N,Q;
int a[100005];
int b[100005];
int s[100005];
int t[100005];
int main() {
    cin>>N>>Q;
    rep(i,Q) cin>>a[i]>>b[i]>>s[i]>>t[i];
    rep(i,Q) {
        int ans = 0;


        if(b[i]<=s[i]) ans=t[i]-s[i];
        else if(t[i]<=a[i]) ans=t[i]-s[i];
        else if(a[i]<=s[i]&&t[i]<=b[i]) ans=0;
        else {
            if(a[i]-s[i]>=0) ans=a[i]-s[i];
            if(t[i]-b[i]>=0) ans+=t[i]-b[i];
        }
        cout<<ans*100<<endl;

    }
    return 0;
}
F問題

Eと比べて問題文短いし簡単そうだったのでこっちから解いた 初めはUnionFindかな？とか考えていたけど、上がって下がるパターンも数えることになってダメだと途中で気付く 辺貼って舐めた

int N,M;
int a[55],b[55];
vector<int> G[55];
int dfs(int s,int t) {
    queue<P> que;
    que.push(P(s,0));
    bool flag[55] = {};

    while(que.size()) {
        P p = que.front();
        que.pop();
        int v = p.fr;
        if(flag[v]) continue;
        flag[v] = true;
        if(p.fr==t) return 1;
        rep(i,G[v].size()) {
            int e = G[v][i];
            que.push(P(e,p.sc+1));
        }

    }

    return 0;
}
int main() {
    cin>>N>>M;
    rep(i,M) {
        cin>>a[i]>>b[i];
        G[a[i]].pb(b[i]);
    }
    int ans = 0;
    rep(i,N+1) {
        if(i==0) continue;
        if(dfs(i,1)==1) ans++;
    }
    cout<<ans<<endl;
    return 0;
}
E問題

シミュレーションするだけではと思い込んでO(N2 RC)を投げてしまう
TLEする
累積和の部分をいもす法して投げたら通る
コンテスト後に1位の方が言っていたけど、ちゃんと計算量の見積もりしてからコード書かねば

int R,C,M;
int N;
int r[2][5050];
int c[2][5050];

int grid[55][55];


void init() {
    rep(i,55) rep(j,55) grid[i][j]=0;
}
void rote(int a) {
    grid[r[0][a]][c[0][a]]++;
    grid[r[0][a]][c[1][a]+1]--;
    grid[r[1][a]+1][c[0][a]]--;
    grid[r[1][a]+1][c[1][a]+1]++;
}
void imos() {
    rep(i,R+1) {
        rep(j,C+1) {
            if(j!=0) grid[i][j]+=grid[i][j-1];
        }
    }
    rep(i,R+1) {
        if(i==0) continue;
        rep(j,C+1) {
            grid[i][j]+=grid[i-1][j];
        }
    }
}
int count() {
    int res = 0;
    rep(i,R) rep(j,C) if(grid[i][j]%4==0) res++;
    return res;
}
int main() {
    cin>>R>>C>>M;
    cin>>N;
    rep(i,N) cin>>r[0][i]>>r[1][i]>>c[0][i]>>c[1][i];
    rep(i,N) r[0][i]--,r[1][i]--,c[0][i]--,c[1][i]--;

    init();
    rep(i,N) {
        rep(j,N) {
            if(i==j) continue;
            rote(j);
        }
        imos();
        int c = count();
        if(M==c) {
            cout<<i+1<<endl;
        }
        init();
    }
    return 0;
}
G問題

1つ前の席の状態を持ってDPかな？と思って書いたけど、サンプル段階でダメと気付く
よく考えて実装に移らないとダメ 部分点だけ取りにいった

H問題

この時点で4位で、この問題の部分点取れば5位以上にはなるかなとか思ってた
結果部分点すらバグった

感想

計算量の見積もりとか、よく考えてから実装に移るとか、色々出来てないことがわかった
あと、普段のコンテストでは上位陣の正解状況を見て次の問題を選ぶってことができるけど、今回はそうは出来なくて精神的につらいなあと感じました

最後に

スタッフの方々本当にありがとうございました！