2012年JOI本選をゆっくり解いてみた

とりあえず、１～３までは解けそうだったので解いてみました。
４の解法が気になります。
1.JJOOII
これは予選の日に解きました.テストケースがなかったので落ちてるだろうなぁ...とか思ってましたが, 100%でした.やった～

#include <stdio.h>
#include <string.h>

int main(void)
{
    int j, o, i;
    char c, now;
    int ans;
    
    c = now = 'K';
    j = o = i = 0;
    ans = 0;
    
    while (1){
        scanf("%c", &c);
        if (now == 'I' && c != 'I'){
            if (j >= o && o <= i){
                ans = ans > o ? ans : o;
            }
            j = o = i = 0;
        }
        
        if (c == '\n'){
            break;
        }
        
        if ((j == 0 || now == 'J') && c == 'J'){
            j++;
            now = 'J';
        }
        else if (now == 'J' && c == 'I'){
            j = o = i = 0;
            now = 'I';
        }
        
        if ((j != 0 || now == 'O') && c == 'O'){
            o++;
            now = 'O';
        }
        else if (now == 'O' && c == 'J'){
            o = i = 0;
            j = 1;
            now = 'J';
        }
        
        if ((o != 0 || now == 'I') && c == 'I'){
            i++;
            now = 'I';
        }
    }
    printf("%d\n", ans);
    
    return (0);
}

2.Card Game is Fun
最初はDPと思っていましたが、案外やるだけでしたね.シミュレーションしました.
これも1回で100%. いいかんじ！

#include <stdio.h>

int main(void)
{
    int res, temp;
    int a[5001], b[5001];
    int na, nb;
    int i, j, k;
    
    scanf("%d%d", &na, &nb);
    
    for (i = 0; i < na; i++){
        scanf("%d", &a[i]);
    }
    for (i = 0; i < nb; i++){
        scanf("%d", &b[i]);
    }
    
    res = 0;
    for (i = 0; i < nb; i++){
        k = i;
        temp = 0;
        for (j = 0; j < na; j++){
            if (a[j] == b[k]){
                k++;
                temp++;
                if (k == nb){
                    break;
                }
            }
        }
        res = temp > res ? temp : res;
    }
    
    printf("%d\n", res);
    
    return (0);
}

3.Night Market
こっちは本当にDPでした. 典型DPにちょっと条件がついただけであまり難しい気はしませんでした.
これも1回で100%.やった！

#include <stdio.h>
#include <string.h>

int max(int a, int b)
{
    return (a > b ? a : b);
}

int main(void)
{
    int n, t, s;
    int a[3001], b[3001];
    int dp[3001];
    int res;
    int i, j;
    
    scanf("%d%d%d", &n, &t, &s);
    
    memset(dp, 0, sizeof(dp));
    
    res = 0;
    
    for (i = 0; i < n; i++){
        scanf("%d%d", &a[i], &b[i]);
        
        for (j = t - b[i]; j >= 0; j--){
            if (!(j < s && s < j + b[i])){
                dp[j + b[i]] = max(dp[j + b[i]], dp[j] + a[i]);
                res = max(dp[j + b[i]], res);
            }
        }
    }
    
    printf("%d\n", res);
    
    return (0);
}

本選に出場できてれば、４と５の部分点を狙ってたかもしれないですが、どうだろう.
寮では落ち着いて書けますが、本選に出場していたとするとテンパって死んでいたと思います.
来年は難化しそうなので、発想力と実装力とメンタルを強くしようと思います.