読者です 読者をやめる 読者になる 読者になる

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

JOI本選

プログラミング

難化してました。

結果

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

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

1番

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

2番

DPだけど難しかったです。僕的に。
dp[s][t][k]:=Sをs番目、Tを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);
}

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

#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);
}

3番

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

4番

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

よっしゃー書くかとかいって書いたら結局後ろから確定させていく方法がわりと怪しくて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);
}

5番

バブルソートの交換回数自体は有名なのでそれ覚えてれば部分点は取りにいけたと思うんですが無理だった。というかBIT使うの忘れてた。
まだ手つけてない。解法的にはすげーってなった。ちなみに時間内に5番を完答できた人はこの世に存在しなかったらしい…

ARC #12

復習してたら「あれ?いまやってるやん」ってなって残り30分で参加。
A,Bがゆるふわだったのでとりあえず通してCで5目並べの判定めんどくせーとか思っているうちに終わった。230位。まぁしょうがない。

まとめ(小並感)

  1. 合宿いけるといいな
  2. ブランク回復無理やった
  3. 受験勉強余裕勢になりたい
  4. ブラック庶務をコントロールしたい
  5. どっかでプログラミングに集中してスキルを取り戻すというか向上させたい
  6. 数研勢強かった
広告を非表示にする