始点に戻らなくていい巡回セールスマン bitDP N=17 (それって最短ハミルトン路) abc190_e

ライブラリ bitDP

ルーカスの定理 lucas リュカ 使った記録

制約

  • nCr mod m にて、
  • n, r <= 1018
  • m <= 1000程度
  • 理論的にはこれくらいはいけそう

発展

最小費用流 負のコスト うし フロー

負のコストは無いけれど、問題「M-分割」をkobae964さんのeditorialに従って解いた

f:id:peroon:20210818104141p:plain

負のコストがある場合の内部実装

有向グラフのオイラー路・オイラー閉路判定関数

ライブラリ 
#include <atcoder/dsu>
using namespace atcoder; // 忘れがち

// （有向グラフ版）
// オイラー路ライブラリ
// そもそも連結されているか (by BFS)
// 有向グラフなら始点に注意
// （どこを開始点にするかで全て訪れれるかが変わる）
// => UFで判定するように変更
bool is_connected(VV& G){
  ll N = G.size();
  dsu uf(N);
  rep(i,N){
    for(ll to : G[i]){
      uf.merge(i,to);
    }
  }
  if(uf.groups().size()==1)return true;
  return false;
}
// ※有向
// オイラー閉路が作れるか？
// 条件：すべての頂点について入次数＝出次数
bool is_eular_circuit(VV& G){
  ll N = G.size();
  VI in(N);
  VI out(N);
  rep(i,N){
    for(ll j : G[i]){
      // i to j
      out[i]++;
      in[j]++;
    }
  }
  rep(i,N){
    if(in[i]!=out[i])return false;
  }
  return true;
}
// ※有向
// オイラー路が作れるか？
// 条件：
// ある１点について、入次数＋１＝出次数
// ある１点について、入次数＝出次数＋１
// その他の点について、入次数＝出次数
bool is_eular_trail(VV& G){
  ll N = G.size();
  VI in(N);
  VI out(N);
  rep(i,N){
    for(ll j : G[i]){
      // i to j
      out[i]++;
      in[j]++;
    }
  }
  ll more_in=0;
  ll more_out=0;
  ll even=0;
  rep(i,N){
    if(in[i]==out[i]){
      even++;
    }
    // 1の差であることに注意(2以上の差があったら不可能)
    else if(in[i]==out[i]+1){
      more_in++;
    }
    else if(in[i]+1==out[i]){
      more_out++;
    }
    else{
      // 2以上の差
      return false;
    }
  }
  if(more_in==1 && more_out==1)return true;
  return false;
}

条件確認

Air Conditioners エアコン （左から見る＆右から見る）

1500
  • Quiz
  • AC
  • 解法
    • 左からの累積MIN, 右からの累積MINを取ればいい
  • 別解？
    • 下記画像左上のように、不要なエアコンがあれば除去してしまえば、現在位置の左右のエアコンのみ見ればいいな、と思ったのだがその除去ができなかった
  • 学び
    • 「左からの累積・右からの累積かー」で終わってしまってはいけない
    • まず状況をグラフで書いてみる
    • V字のグラフがたくさんできる
    • →しかし直線ではないので扱いづらい→Vの底で切って別々に考える→左から累積・右から累積したくなる

f:id:peroon:20210715013408p:plain