JOI本選

難化してました。

結果

結果は170/500でした。
ボーダーがここらへんになりそうなので５割くらいの確率で合宿に行けるっぽいです。

とりあえず行けることを願おう。

１番

プラクティスの４番を改変するだけだからわりとやさしかったはずなのでは…
しかし５割しか満点とれてなかったらしい。

２番

DPだけど難しかったです。僕的に。
dp[s][t][k]:=Sをs番目、Tをｔ番目までつかい末尾がk('I'?1:0)のときの最大
ってところまではわかったんですが、漸化式が立てられず…
というか問題そのままに考えてたしね（）
メモ化再帰でやったらなんで53/54のケースがACするのかがよくわからないコードが出来上がってた。

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

int m, n;
char s[2013], t[2013];
int memo[2013][2013][2];

int dfs(int ps, int pt, int len, int flag) {
    if (len<memo[ps][pt][flag]) return memo[ps][pt][flag];
    int ret = 0;
    if (flag) ret=max(ret, len);
    if (ps<m&&s[ps]=="IO"[flag]) ret=max(ret, dfs(ps+1, pt, len+1, (flag+1)%2));
    if (pt<n&&t[pt]=="IO"[flag]) ret=max(ret, dfs(ps, pt+1, len+1, (flag+1)%2));
    return memo[ps][pt][flag] = ret;
}

int main() {
    scanf("%d%d",&m,&n);
    scanf("%s%s",s,t);
    
    // 70点解法(ただし不正解が一つ)
    int res = 0;
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            if (s[i]=='I') res = max(res, dfs(i+1, j, 1, 1));
            if (t[j]=='I') res = max(res, dfs(i, j+1, 1, 1));
        }    
    }
    printf("%d\n", res);
}

うん。本当の解法に比べるとわりと惜しいｗ
正解はこちら（書きなおしたやつ）

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

int m, n;
char s[2013], t[2013];
int dp[2013][2013][2];

int dfs(int i, int j, int k) {
    if (dp[i][j][k]!=-1) return dp[i][j][k];
    int res = 0;
    if (i < m && s[i]=="IO"[k]) res = max(res, dfs(i+1, j, !k) + 1);
    if (j < n && t[j]=="IO"[k]) res = max(res, dfs(i, j+1, !k) + 1);
    return dp[i][j][k] = res;
}

int main() {
    scanf("%d%d",&m,&n);
    scanf("%s%s",s,t);
    
    memset(dp, -1, sizeof(dp));
    
    int res = 0;
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            res = max(res, dfs(i, j, 0));
        }
    }
    printf("%d\n", (res==0||res%2==1)?res:res-1);
}

３番

dijkstraっぽいなーと思いつつ書かないいつものパターン。
というか帰って来て実装しようとしたらあり本確認しないと書けなかったから実際やっててもできてたかあやしい…
実装多いし書ききってない…

４番

めちゃくちゃ難しかったけど解説で貪欲のはじめのワンステップ聞いて一瞬で理解できるほど理屈は簡単だった。
ようするに文字の特性を考えて後ろからなら確定させられるってわかればよかったのね…

よっしゃー書くかとかいって書いたら結局後ろから確定させていく方法がわりと怪しくて80点になったorz

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int n;
char s[1000000];

bool C(int x) {
    bool used[1000000];
    memset(used, 0, sizeof(used));
    vector<int> J, O, I;
    for (int i=n-1; i>=0&&I.size()<x; i--) {
        if (s[i]=='I') {
            I.push_back(i);
            used[i] = true;
        }
    }
    if (I.size()<x) return false;
    int a = 0;
    for (int i=n-1; i>=0&&O.size()<x; i--) {
        if (s[i]=='O'&&I[a]>i) {
            O.push_back(i);
            used[i] = true;
            a++;
        }
    }
    if (O.size()<x) return false;
    int b = 0;
    for (int i=n-1; i>=0&&J.size()<x; i--) {
        if (s[i]=='I'&&!used[i]&&O[b]>i) {
            J.push_back(i);
            used[i] = true;
            b++;
        } else if (s[i]=='J'&&O[b]>i) {
            J.push_back(i);
            used[i] = true;
            b++;
        }
    }
    if (J.size()<x) return false;
    return true;
}
int main() {
    scanf("%d%s",&n,s);
    int lb=0, ub=n+1;
    while (ub-lb>1) {
        int mid = (ub + lb) / 2;
        if (C(mid)) lb = mid;
        else ub = mid;
    }
    printf("%d\n", lb);
}