2020-02-22

D - 薄氷渡り

JOI

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

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

作者:渡部有隆
出版社/メーカー: マイナビ出版
発売日: 2015/01/30
メディア: Kindle版

2020-02-21

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

JOI

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

イメージ

f:id:peroon:20210924014114p:plain

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/

2020-02-20

C - タイル (Tile)

JOI

f:id:peroon:20200220021433p:plain

Quiz

https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_c

AC Code

https://atcoder.jp/contests/joi2011yo/submissions/10218261

Code (抜粋)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    // input
    ll N; 
    cin >> N;
 
    ll Q;cin>>Q;
    while(Q--){
      ll x,y;cin>>x>>y;
      x--;y--;
      
      if(x>N/2){
        x = N-1-x;
      }
      if(y>N/2){
        y = N-1-y;
      }
 
      if(x>y) swap(x,y);
 
      if(x%3==0){
        p(1);
      }else if(x%3==1){
        p(2);
      }else{
        p(3);
      }
    }   
    return 0;
}