AHC036 シュタイナー木は万能ではない

AHC018, AHC020にて、シュタイナー木は有効な手法であった。今回AHC036に参加した時も木が見えたし、行かなくて良い点もあったのでシュタイナー木を構築した。しかし、振り返ってビジュアライズしてみると、筋が悪かったことが分かる。

AHC036 visualizer sample 1にて、中央の点からPrim法による（ほぼ）最小シュタイナー木作成を行ったもの

  • 赤い頂点：訪れる点
  • 緑の頂点：訪れなくていい点
  • 頂点の横の数字：中央の頂点からの距離

観察

  • AHC036の解説を見た人は知っている通り、中央からLBの距離で町にタッチしてそのまま中央に戻るのが強い
  • しかし、シュタイナー木だと辺数は少ないものの、各町に訪れるための距離が遠いものがある
    • （中央からの距離が30の町がある...）
    • 一方、中央からのBFS木なら最遠でも距離は18等
  • 辺数は400ほどとかなり少ないが、Aに収めるためにそこまで削る必要はない
  • 中央から遠い点を作らないためには、中央からBFSして木を構築すればよかった
  • 「最小全域木よりシュタイナー木が高級」「シュタイナー木は効く」という過学習をしてしまった...🤖

No.2201 p@$$w0rd (★1.5) 別解

code

string base;
ll N;
ll cnt=0;

bool is_ok(string& s){
  bool exist_char=0;
  bool exist_num=0;
  bool exist_sign=0;
  for(char c : s){
    if('a'<=c && c<='z')exist_char=1;
    if(c=='1' or c=='0')exist_num=1;
    if(c=='@' or c=='$')exist_sign=1;
  }
  return exist_char * exist_num * exist_sign;
}

void dfs(string s){
  if(s.size()==N){
    if(is_ok(s)){
      cnt++;
    }
    return;
  }
  ll idx = s.size();
  char c = base[idx];
  
  s.push_back(c);
  dfs(s);
  s.pop_back();

  if(c=='l'){
    s.push_back('1');
    dfs(s);
    s.pop_back();
  }
  if(c=='o'){
    s.push_back('0');
    dfs(s);
    s.pop_back();
  }
  if(c=='a'){
    s.push_back('@');
    dfs(s);
    s.pop_back();
  }
  if(c=='s'){
    s.push_back('$');
    dfs(s);
    s.pop_back();
  }
}

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

    // input
    cin>>base;
    N=base.size();

    dfs("");
    p(cnt);
    
    return 0;
}

No.1423 Triangle of Multiples (★1.5) 別解

code

void solve(){
  ll a,b,c;cin>>a>>b>>c;

  // 各辺を1e18を超えない && 倍数の条件を満たす、最大の長さにする

  ll big = 1e18;
  ll x = (big/a)*a;
  ll y = (big/b)*b;
  ll z = (big/c)*c;
  cout << x << ' ' << y << ' ' << z << endl;
}

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

    ll T;cin>>T;
    while(T--){
      solve();
    }
    
    return 0;
}

Functional Graph構造体を作った。なもりグラフ

ライブラリ

説明

  • 問題 https://atcoder.jp/contests/abc357/tasks/abc357_e
  • Functional Graphの問題だと見抜けた後は、連結成分ごとに分けて考えて、それぞれ閉路部分がどこか求めるなど、よく求める形がありそうなので再利用を考えて構造体にした
  • FunctionalGraph構造体
    • 複数（もしくは1つ）の、連結成分ごとに分離された、なもりグラフを持つ
  • Namori構造体
    • なもりグラフ
    • 各頂点は連結
    • 下記画像のような形で、閉路とそれに刺さってくる頂点の形

使用例

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

    // input
    ll N;cin>>N;

    // iからA[i]への辺
    VI A(N);
    rep(i, N){
      cin >> A[i]; A[i]--;
    }

    ll ans=0;
    auto fg = FunctionalGraph(A);
    // 連結されたなもりグラフそれぞれについて
    for(auto namori : fg.namoris){
      for(ll id : namori.ids){
        // サイクルも深さも取れるよ
        ans += namori.cycle_ids.size() + namori.depth[id];
      }
    }
    p(ans);

    return 0;
}

verified

用語（閉路、ループ）

GPT

Cycle: 
　グラフ理論において、特に意味が明確で、同じ頂点を
　2度通らずに出発点に戻ってくる経路を指します。
Loop: 
　通常、自己ループを指し、1つの頂点から同じ頂点に戻るエッジを意味します。

したがって、一般的な「閉路」を指す場合は「cycle」が適切です。

abc355 D - Intersecting Intervals [left, right]でソートする解法

画像

  • 丸1がイメージ
  • 丸2のような入力でも通るようにしよう

code抜粋

using ll = long long;
using PII = pair<ll, ll>;

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

    // input
    ll N;
    cin>>N;
    
    vector<PII> V;
    rep(i,N){
      ll l,r;cin>>l>>r;
      V.push_back({l,r});
    }
    sort(ALL(V));

    debug(V);
    ll cnt=0;
    rep(i,N-1){
      ll l=V[i].first;
      ll r=V[i].second;

      // 1つ右は重なっているか？
      if(r < V[i+1].first)continue;

      // 重なっている場合
      ll ok=i+1;
      ll ng=N;
      while(ng-ok>1){
        ll center = (ok+ng)/2;
        if(V[center].first<=r){
          ok=center;
        }else{
          ng=center;
        }
      }
      cnt += ok-i;
    }

    p(cnt);
    return 0;
}