perogram

dfsで閉路検出 D - Subway

Quiz

https://codeforces.com/contest/131/problem/D

AC code

https://codeforces.com/contest/131/submission/74636017

解法

  • 閉路が1つだけあることが決まっているので、dfsして再訪した点があれば、それは閉路内の点
  • dfsしながら親を記録しておけば、閉路発見時に親をたどって閉路の点が全てわかる
  • 閉路内の点は距離0
  • 閉路内の各点を始点として閉路以外の点方向にdfs2をして距離を求めればよい

この記事は何

  • dfsで閉路を見つけてそのパスを求めたい時の参照用

excerpted code

int n,x,y;
int f,s; // loop start & end
int ans[3005];
int pred[3005]; // parent
vector<int> v[3005];
bool used[3005];
bool closed[3005];

// 答え用
void dfs2(int x,int d,int p=-1){
  ans[x]=d;
  for(ll to : v[x]){
    if(to==p)continue;
    if(!closed[to]) dfs2(to, d+1, x);
  }
}

// 閉路検出用
void dfs(int x,int y){
  pred[x]=y;
  used[x]=1;
  for(ll to : v[x]){
    if (to==y) continue;
    if (used[to]==1) {
      // revisit
      s=x;
      f=to;
      debug(s,f);
      return;
    }
    dfs(to,x);
  }
}
int main(){
    cin>>n;
    rep(i,n){
      cin>>x>>y;
      x--;y--;
      v[x].push_back(y);
      v[y].push_back(x);
    }

    dfs(1,-1);
    swap(f,s);
    // 閉路を辿る
    while (s!=f) {
        closed[s]=true;
        s=pred[s];
    }
    closed[f]=true;
    
    rep(i,n){
      if (closed[i]==true) dfs2(i,0);
    }
    VI A;
    rep(i,n){
      A.push_back(ans[i]);
    }
    print_vector(A);
}

F - Knapsack for All Segments

Quiz

https://atcoder.jp/contests/abc159/tasks/abc159_f

解説

  • 私の解説ではないですが、良さそうな解説がTweetされていたのでたどり着ける人が増えるようにここに書いておく

感想

  • 機械的&数学的に解いている
  • l, rを全探索だと重いからlを消すというのは汎用性がある

prefix palindrome

const int M = (int)(2e6 + 239);
int pref[M], c;
string solve_palindrome(const string& s)
{
    string a = s;
    reverse(a.begin(), a.end());
    a = s + "#" + a;
    c = 0;
    for (int i = 1; i < (int)a.size(); i++)
    {
        while (c != 0 && a[c] != a[i])
            c = pref[c - 1];
        if (a[c] == a[i])
            c++;
        pref[i] = c;
    }
    return s.substr(0, c);
}
  • prefとはprefix functionと書いてあり、一致しなかったらcを減らしていくと理解した
  • manacharでやってもいいのかもしれないが、偶数長回文の時はダミー文字を入れる必要がある
    • 例:abba => a#b#b#a としてからmanachar

MP, KMP

  • snukeさんのblog記事を読むと、上記コードはMP, KMP法に近い?
  • ということで入力sに対してt = s + "#" + rev(s)を作ってKMPしてみたら、同様のprefix palindromeが得られた
string KMP(string s){
  s = s + "#" + rev(s);
  ll L = s.size();
  VI A(2*L, -1);
  int j = -1;
  for (int i = 0; i < L; i++) {
    while (j >= 0 && s[i] != s[j]) j = A[j];
    j++;
    A[i+1] = j;
  }
  ll ma = *max_element(ALL(A));
  return s.substr(0, ma);
}

動作確認コード

string rev(string s){
  reverse(ALL(s));
  return s;
}

// 自作
string KMP(string s){
  s = s + "#" + rev(s);
  ll L = s.size();
  VI A(2*L, -1);
  int j = -1;
  for (int i = 0; i < L; i++) {
    while (j >= 0 && s[i] != s[j]) j = A[j];
    j++;
    A[i+1] = j;
  }
  ll ma = *max_element(ALL(A));
  return s.substr(0, ma);
}

const int M = (int)(2e6 + 239);
int pref[M]; // prefix function
int c;
 
// editorial
string solve_palindrome(const string& s)
{
    string a = s;
    reverse(a.begin(), a.end());
    a = s + "#" + a;
    c = 0;
    for (int i = 1; i < (int)a.size(); i++)
    {
        while (c != 0 && a[c] != a[i])
            c = pref[c - 1];
        if (a[c] == a[i])
            c++;
        pref[i] = c;
    }
    return s.substr(0, c);
}

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

    vector<string> S;
    S.push_back("abcbae");
    S.push_back("abae");
    S.push_back("aaaaaa8888888888888888888888bbbbb");

    for(string s : S){
      auto a = KMP(s);
      auto b = solve_palindrome(s);
      debug(s,a,b);
      if(a==b){
        p("same");
      }else{
        p("not same");
      }  
    }
    return 0;
}

結果

[s,a,b]: "abcbae" "abcba" "abcba"
same
[s,a,b]: "abae" "aba" "aba"
same
[s,a,b]: "aaaaaa8888888888888888888888bbbbb" "aaaaaa" "aaaaaa"
same

その他

  • 最近codeforcesのmanacharについてツイートしている人が多かったので、TLの人はmanacharを使った人が多そう
  • 他にもeditorialの方法や、KMPの方法もる
  • しかし使い方は分かったものの、内部理解はしていない。それはまだ早い

全方位木DPについてBlogを読むより先に見るべき動画


Educational DP Contest / DP まとめコンテスト (EDPC) : V - Subtree 解説動画

追記:ABCで出題された!F - Distributing Integers 2020/03/28

全方位木DP or rerooting

  • snukeさんやかつっぱさんの説明だと全方位木DPという印象。各辺の矢印をすべて求めるため
  • jupiroさんの説明だとrerootingという印象

2次元imos (二次元いもす) ~yukicoder No.60 魔法少女~

Quiz

https://yukicoder.me/problems/no/60

AC code

https://yukicoder.me/submissions/443826

クラス化してみた

struct Imos2D{
  VV A;
  ll H,W;
  Imos2D(ll h, ll w){
    H = h;
    W = w;
    A.resize(H, VI(W));
  }

  // [(y0,x0), (y1,x1)]
  void add(ll y0, ll x0, ll y1, ll x1, ll v){
    A[y0][x0] += v;
    A[y1+1][x1+1] += v;
    A[y0][x1+1] -= v;
    A[y1+1][x0] -= v;
  }
  void calc(){
    // horizontal imos
    rep(y,H){
      rep(x,W-1){
        A[y][x+1] += A[y][x];
      }
    }

    // vertical imos
    rep(x, W){
      rep(y, H-1){
        A[y+1][x] += A[y][x];
      }
    }
  }
  ll val(ll y, ll x){
    return A[y][x];
  }
};

f:id:peroon:20200314043440p:plain

No.41 貯金箱の溜息(EASY)~コインDP~

Quiz

https://yukicoder.me/problems/no/41

AC code

https://yukicoder.me/submissions/443691

DP表の定義

// i円玉まで使って
// j円以下を作る方法
ll dp[10][100100];
  • j円「以下」というところがポイント

DP表の図示

f:id:peroon:20200313224716p:plain

解法

  • M円を111111で割った値をM'として、M'円「以下」を新1~9円玉で支払う問題になる
  • M'円との差分は旧1円玉で支払う

コインDP

  • 検索しやすいように名前をつけておこう
  • コインDPと呼ぼう
  • 今回使った新1~9円玉は代わりに「3円玉、7円玉、10円玉、17円玉」などの設定になっても大丈夫

code 抜粋

// i円玉まで使って
// j円以下を作る方法
ll dp[10][100100];

void prepare(){

  rep(i,10){
    rep(j,100100){
      dp[i][j]=-1;
    }
  }

  dp[0][0] = 1;

  // 1円のみで作る
  rep(j, 100000){
    dp[1][j] = j+1;
  }
  
  // 0円の払い方は1通り
  rep(i,10){
    dp[i][0] = 1;
  }

  FOR(i, 2, 10){
    // i円玉を使う

    // j円払う
    // 上からお下がりのぶん
    FOR(j, 0, 100000){
      dp[i][j] = dp[i-1][j];
    }

    // 累積していくぶん
    FOR(j, 0, 100000){
      dp[i][j+i] += dp[i][j];
      dp[i][j+i] %= mod;
    }
  }
}

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

    // input
    ll Q;cin>>Q;

    prepare();

    while(Q--){
      ll m;cin>>m;
      m /= 111111;
      
      // ll ans = dp[9][m] - dp[9][m-1]; // m円ぴったり払うならこっちのはず
      // ans %= mod;
      // if(ans<0) ans += mod;
      ll ans = dp[9][m];
      p(ans);
    }

    return 0;
}

隣接積の和の最小値をOEISに聞いてみる練習

Quiz

https://yukicoder.me/problems/no/831

AC code

具体的な数列

[n, minA]: 1 {1}
[n, minA]: 2 {1, 2}
[n, minA]: 3 {1, 2, 3}
[n, minA]: 4 {1, 3, 2, 4}
[n, minA]: 5 {1, 4, 3, 2, 5}
[n, minA]: 6 {1, 5, 3, 4, 2, 6}
[n, minA]: 7 {1, 6, 3, 4, 5, 2, 7}
[n, minA]: 8 {1, 7, 3, 5, 4, 6, 2, 8}★
[n, minA]: 9 {1, 8, 3, 6, 5, 4, 7, 2, 9}★

N=9, N=8の場合の遷移を図示★

f:id:peroon:20200312013615p:plain