A - JJOOII (JJOOII) ～文字列のランレングス（文字情報あり）～

Quiz

https://atcoder.jp/contests/joi2012ho/tasks/joi2012ho1

AC code

https://atcoder.jp/contests/joi2012ho/submissions/10256473

解法

• Oの連続数に注目する
• 例えばOOOがあったとき（連続したOが3個でその隣は違う文字）、レベル3しか作りえない
  • レベル4はもちろんだが、レベル2も作れない
• 文字ごとにランレングス圧縮し、Oに注目して左がJ, 右がIであり、かつJとIの長さがO以上あれば作れる

例題

OJJOOIIOJOI

ランレングス圧縮すると
O1 J2 O2 I2 O1 J1 O1 I1

Oに注目すると
J2 O2 I2の箇所でLV2が作れる
J1 O1 I1の箇所でLV1が作れる

それらのmaxを取って答えは2

code 抜粋

using P = pair<char, ll>;
// どの文字が長さいくつ
// のvectorで返す
vector<P> run_length(string& s){
  vector<P> ret;
  ll N = s.size();
  if(N==0) return ret;
  char cur=s[0];
  ll cnt=1;
  FOR(i, 1, N){
    if(s[i]==cur){
      cnt++;
    }else{
      ret.push_back(MP(cur, cnt));
      cur = s[i];
      cnt = 1;
    }
  }
  ret.push_back(MP(cur, cnt));  
  return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    string s;cin>>s;

    stringstream ss;
    ss << 'z';
    ss << s;
    ss << 'z';

    string t = ss.str();
    vector<P> V = run_length(t);

    ll ma = 0;
    ll N = V.size();
    FOR(i, 1, N-1){
      if(V[i].first=='O'){
        ll len = V[i].second;
        // 左右見る
        if(V[i-1].first=='J' && V[i-1].second >= len && V[i+1].first=='I' && V[i+1].second >= len){
          chmax(ma, len);
        }
      }
    }
    p(ma);
    return 0;
}

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

bfsのたたき台 (2次元グリッド)

• bfsってやるだけなんだけど、これまで汎用化していなかった
• たたき台としてここに書いておく

verified

• E - チーズ (Cheese)
  • ✅https://atcoder.jp/contests/joi2011yo/submissions/10254552
• D - Grid Repainting
  • ✅https://atcoder.jp/contests/abc088/submissions/11618621
• C - 幅優先探索
  • ✅https://atcoder.jp/contests/abc007/submissions/17739188
• G-グリッド金移動
  • 少し変更して金将の移動に
  • ✅https://atcoder.jp/contests/past202005-open/submissions/22450272

code

VS S; // map
const int H_MAX = 55; // 1050とかでも通る
ll d[H_MAX][H_MAX];
ll H,W; // ちゃんとセットすること！

int dx[4] = {-1, 0, 1,  0};
int dy[4] = { 0, 1, 0, -1};

bool in_range(ll i, ll j){
  if(0<=i && i<H && 0<=j && j<W){
    return true;
  }else{
    return false;
  }
}

// 問題設定に沿って書き換える
const char block = '#';
const char pass = '.';

// 引数は(Y, X), (Y, X)
// 0-indexed
// Yが先だからね！！
ll bfs(PII from, PII to){
  rep(i,H_MAX){
    rep(j,H_MAX){
      d[i][j]=-1; // 到達不能をinfにするか-1にするかは注意！
    }
  }
  queue<PII> que;
  d[from.first][from.second] = 0;
  que.push(from);
  while(!que.empty()){
    auto pa = que.front(); que.pop();
    rep(i, 4){
      ll ny = pa.first + dy[i];
      ll nx = pa.second + dx[i];
      if(in_range(ny,nx) && d[ny][nx]==-1 && S[ny][nx]!=block){
        // can go
        d[ny][nx] = d[pa.first][pa.second] + 1;
        que.push(MP(ny,nx));
      }
    }
  }
  return d[to.first][to.second];
}

aを見つけたらbに塗るbfs

• 湖を見つけたら番号を付けながら塗る必要があったので書いた
• 再利用の機会があるかも（書くの面倒なので・・・）
• AC D. Lakes in Berland https://codeforces.com/contest/723/submission/102175410

    // search : 探す記号
    // paint : 塗り後の値
    auto fill_edge = [&](PII start, ll search, ll paint){
      if(G[start.first][start.second]!=search)return;
      
      queue<PII> que;
      que.push(start);
      G[start.first][start.second]=paint;

      while(!que.empty()){
        auto pa = que.front(); que.pop();
        ll y = pa.first;
        ll x = pa.second;
        rep(i,4){
          ll ny = y + dy[i];
          ll nx = x + dx[i];
          if(!in_range(ny,nx))continue;
          if(G[ny][nx]==search){
            que.push({ny,nx});
            G[ny][nx]=paint;
          }
        }
      }
    };

D - カード並べ

Quiz

https://atcoder.jp/contests/joi2010yo/tasks/joi2010yo_d

AC code

https://atcoder.jp/contests/joi2010yo/submissions/10252516

解法

• next_permutationで全ての並び方を考慮し、先頭k個を採用する
• 3200msかかるが、10秒制限なので大丈夫

code抜粋

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,K;cin>>N>>K;
    VI A(N);
    rep(i,N)cin>>A[i];

    VI I;
    rep(i, N) I.push_back(i);

    set<string> se;
    do{
      // 前のk枚
      stringstream ss;
      rep(i, K){
        ll idx = I[i];
        ss << A[idx];
      }
      se.insert(ss.str());
    }while(next_permutation(ALL(I)));

    ll ans = se.size();
    p(ans);

    return 0;
}

BICYCLE(バイスクル) RACER BACK(レーサーバック) GOLD EDGES(ゴールドエッジ) トランプ 赤/青 2デック

D - 薄氷渡り

Quiz

https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_d

AC code

https://atcoder.jp/contests/joi2009yo/submissions/10251707

解法

• dfsで経路を全探索
• dfs内でdfsをさらに呼ぶ時、呼ぶ前に状態を変更して、読んで戻ってきた後に状態を戻すテクがありますね。それを使いました

注意点

• 移動先の薄氷しか割れない
• 最初に孤立した薄氷からスタートした時は、飛び先がないので1枚も割れないので答えは0

code抜粋

ll ma;
ll F[100][100]; // fixed map
ll G[100][100];
ll W,H;

void reset_map(){
  rep(i, 100){
    rep(j, 100){
      G[i][j] = F[i][j];
    }
  }
}

int dx[4] = {-1, 0, 1,  0};
int dy[4] = { 0, 1, 0, -1};

bool in_range(ll i, ll j){
  if(0<=i && i<H && 0<=j && j<W){
    return true;
  }else{
    return false;
  }
}

void dfs(ll y, ll x, ll m){
  chmax(ma, m);
  rep(i, 4){
    ll ny = y + dy[i];
    ll nx = x + dx[i];
    if(in_range(ny, nx) && G[ny][nx]==1){
      G[ny][nx]=0;
      dfs(ny, nx, m+1);
      G[ny][nx]=1;      
    }
  }
}
    
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    cin>>W>>H;

    rep(i,H){
      rep(j,W){
        cin>>F[i][j];
      }
    }

    rep(i,H){
      rep(j,W){
        if(F[i][j]==1){
          reset_map();
          dfs(i, j, 0);
        }
      }
    }

    p(ma);

    return 0;
}

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

B - 共通部分文字列 (※LCSとは違う)

Quiz

• https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_b

ABRACADABRA
ECADADABRBCRDARA

の最大共通部分列文字列は ADABR

• 文字列は連続である必要
• LCSとは違う（LCSは飛び飛びOK）

AC✅

https://atcoder.jp/contests/joi2008ho/submissions/10236208

解法

• dp[i][j] : s[i], t[j]まで使ったときの最長共通部分文字列
• と定義してDP

イメージ

code 抜粋

ll dp[4005][4005];

int main(){

    // input
    string s,t;cin>>s>>t;
    ll L = s.size();
    ll M = t.size();
    
    ll ma = 0;
    rep(i, L){
      rep(j, M){
        if(s[i]==t[j]){
          if(i-1<0 || j-1<0){
            dp[i][j] = 1;
          }else{
            dp[i][j] = dp[i-1][j-1] + 1;
          }
          chmax(ma, dp[i][j]);
        }
      }
    }
    p(ma);

    return 0;
}

学び

• s[i]==t[j]の時だけを考えればうまくやってくれる
• これはLCSよりも楽となっていて、それは部分文字列が飛び飛びじゃないため
  • LCS資料 http://www.deqnotes.net/acmicpc/1458/