競プロ覚書

思考整理

最短ハミルトン(閉)路問題

・なにそれ
グラフ上の全ての頂点を 1 度ずつ通るパス(サイクル)の最小コストを求める問題
サイクルを求める問題は巡回セールスマン問題とも呼ばれる
NP完全(多項式時間で解けない)で有名


・全部調べたらどうなるのっと
頂点数をNとして、パスならO((N-1)!), サイクルならO(N!)かかる
N<=10くらいまでなら全部試しても高速。C++ならnext_permutaitonを使うと楽


atcoder.jpハミルトン閉路のうち、コストがKであるものを数え上げる。N<=8なので全探索できる


・もっといい方法ないの?
ある。いわゆるbitDP(集合を0と1で扱うDP)を使えば計算量をO(2^N * N^2)まで落とせる
N<=18くらいまでなら競プロの制限時間に間に合うようになる


・なんでbitDPを使うと高速化できるの?
要らない状態を捨ててるから。
結局全部の頂点を通るので通ってきた頂点の順番はどうでもいい。
各頂点を通った/通ってない判定と最後に通った(今いる)頂点だけ分かれば十分。


・お気持ち
dp[S][i]:=通過済みの頂点集合をS(iを含まない)、今いる頂点がiであるときの最小コスト
dp[最後に通る頂点以外の集合][最後に通る頂点]のうち、最小のものが最短ハミルトン路の長さになる。

漸化式
次に通る頂点をi, 直前に通った頂点をjとする
dp[S][i] = min(dp[S - j][j] + cost[j][i])
こんな感じのイメージ……
f:id:pm4:20210627155859p:plain


・例題
atcoder.jpそのまんま巡回セールスマン問題。


atcoder.jp並べる宝石をグラフ、宝石同士の最短距離をコストと考えると最短ハミルトン問題になる


・実装
f:id:pm4:20210627160044p:plain

メモ
・mask >> i AND 1
maskのi番目のビットが立っているかどうか
・mask XOR 1 << j
mask(頂点集合)から最後に通った頂点jのビットを差し引いた(0にした)もの
例: 10110 XOR (1 << 2) = 10010
・1 << k-1 XOR 1 << i
長さkで全部1のビット列からi番目だけを差し引いたもの
・引数
adj:隣接行列グラフ
is_cycle:パスを求めるならfalse, サイクルをならtrueにする
s:始点。-1なら全始点から開始する

競プロ典型90題 - 039 Tree Distance(★5)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_am
解説 kyopro_educational_90/039.jpg at main · E869120/kyopro_educational_90 · GitHub

【問題】
重みのない木が与えられる。
任意の2頂点の最短パス長の総和を求めよ。


【典型ポイント】
主客転倒
辺をカットして頂点を2グループ化

【方針】
辺に注目し、各辺をカットして頂点を2グループに分けた時の頂点数の積が、その辺の「答えへの貢献度
貢献度の和が答えになる。
辺をカットしたときのそれぞれの頂点数は、[子ノードと、その子孫のノード数]をAとすると、A * (N - A)となる。

【感想】
知らんかった。主客転倒って何

int main(){
    int N; cin >> N;
    vector<vector<int>> G(N);
    rep(i, N-1){
        int a, b; cin >> a >> b;
        G[--a].push_back(--b);
        G[b].push_back(a);
    }

    vector<ll> vc(N); //各頂点の、その頂点を含む子孫の数
    auto dfs1 = [&](auto&& self, int v, int p) -> ll{
        vc[v] = 1;
        for(auto e:G[v]){
            if(e==p)continue;
            vc[v] += self(self, e, v);
        }
        return vc[v];
    };
    dfs1(dfs1, 0, -1);

    auto dfs2 = [&](auto&& self, int v, int p) -> ll{
        ll res = 0;
        for(auto e:G[v]){
            if(e==p)continue;
            res += self(self, e, v) + vc[e] * (N - vc[e]);
        }
        return res;
    };
    cout << dfs2(dfs2, 0, -1) << ln;
}

典型90問 - 034 There are few types of elements(★4)

https://atcoder.jp/contests/typical90/tasks/typical90_ah
ベーシックなしゃくとり法

【問題】
数列の区間のうち、含まれる値の種類がK種類以下である最長の連続部分列を求めよ。
【典型ポイント】
しゃくとり法
【方針】
見たまんま、しゃくとり法の典型問題
種類の数え方には連想配列を用いる。集合だと削除処理ができないため。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
constexpr long long INF = 1000000000 + 100;
constexpr long long LINF = 1000000000000000000 + 100;
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
#define rrep(i, n) for(int i=(n); i>=0; i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
    int N, K; cin >> N >> K;
    vector<ll> A(N);
    rep(i, N){
        cin >> A[i];
    }

    int right = 0, res = -1;
    map<int, int> mp; int cnt = 0;
    for(int left=0; left<N; left++){//[left, right)
        while(right<N){
            if(mp[A[right]]==0 and cnt == K)break;
            if(mp[A[right]] == 0)cnt++;
            mp[A[right]]++;
            right++;
        }
        chmax(res, right - left);

        if (left == right) right++;
        mp[A[left]]--;
        if(mp[A[left]] == 0)cnt--;
    }
    cout << res << ln;
}

競プロ典型90問 - 43 Maze Challenge with Lack of Sleep(★4)

問題https://atcoder.jp/contests/typical90/tasks/typical90_aq
解説 https://twitter.com/e869120/status/1394787605099601923/photo/1


【問題】
二次元迷路のスタートからゴールへの経路のうち、最も曲がる回数が少ない経路の回数を求めよ
【典型ポイント】
頂点拡張
0-1 BFS
【注意点】
頂点拡張するので、同じ頂点を複数回更新することがある。
遷移先のコストと現在の最小コストを比較し、更新可能ならキューに詰める。
この処理を適切に行わないと無限ループに陥ったり、更新すべき点が更新されなかったりするので注意
【方針】
通常の最短経路問題とは違い、曲がる回数の最小値を求める。
曲がる回数は移動ごとに+0 または +1 されるので、dequeを用いた0-1BFSで実装できる。

次のマスに移動するときに、曲がったかどうかの判定には「いまどの方向を向いているか(どの方向から来たか)」の情報が必要。
各マスごとに、移動する向きごとに4つに拡張することで対処する。拡張BFSとか、拡張ダイクストラとか言うらしい。

【感想】
同一頂点が複数分割される点は問題なかったが、遷移の条件を間違えまくって時間を溶かしてしまった

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
constexpr long long INF = 1000000000 + 100;
constexpr long long LINF = 1000000000000000000 + 100;
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
#define rrep(i, n) for(int i=(n); i>=0; i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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

using tup = tuple<int, int, int>;

int cost[1010][1010][4];
int main(){
    int H, W, sy, sx, gy, gx;
    cin >> H >> W >> sy >> sx >> gy >> gx; sy--, sx--, gy--, gx--;
    vector<string> g(H); rep(i, H)cin >> g[i];

    rep(i, H)rep(j, W)rep(k, 4)cost[i][j][k] = INF;

    //0-1 bfs
    deque<tup> que;
    rep(k, 4){
        que.push_back({sy, sx, k});
        cost[sy][sx][k] = 0;
    }
    while(!que.empty()){
        auto t = que.front(); que.pop_front();
        int y = get<0>(t), x = get<1>(t), d = get<2>(t);
        rep(k, 4){
            int ny = y+dy[k], nx = x+dx[k];
            if(ny<0 or nx<0 or ny>=H or nx>=W or g[ny][nx]=='#')continue;
            int nxc = cost[y][x][d] + (d == k ? 0 : 1);
            if(cost[ny][nx][k] > nxc){ //更新発生
                cost[ny][nx][k] = nxc;
                if(d==k)que.push_front({ny, nx, k});
                else que.push_back({ny, nx, k});
            }
        }
    }
    cout << *min_element(cost[gy][gx], cost[gy][gx]+4) << ln;
}

ABC007 D - 禁止された数字

atcoder.jp
桁DPの典型的な問題


【題意】
自然数区間[A, B]において、4または9を含む整数はいくつあるか?
【典型ポイント】
1~Nの数え上げは桁DP
区間
【方針】
dp[i][smaller][j]:=1~Nの整数のうち、前方i桁まで見て、4または9が含まれている(j==1)か含まれていない(j==0)場合の数
smaller:未満フラグ
・遷移について
[smaller | x<N[i]-'0']:=未満フラグがtrueなら無条件でtrue、falseかつ次の遷移先が最大値未満ならtrueに遷移、そうでなければfalseに遷移
[j or x==4 or x==9]:=既に4or9が現れている(j==1)または、今見ている値が4or9であればtrue、そうでなければfalseに遷移

[A,B]の数え上げは[1,B] - [1,A-1]でOK

【感想】
桁DPの書き方毎回忘れるのでテンプレ関数にしたい

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
constexpr long long INF = 1000000000 + 100;
constexpr long long LINF = 1000000000000000000 + 100;
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
#define rrep(i, n) for(int i=(n); i>=0; i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
    ll A; string B, C; cin >> A >> B;
    C = to_string(A-1);

    auto digit_dp = [&](string N) -> ll{
        const int n = N.size();
        ll dp[n+1][2][2]{};
        dp[0][0][0] = 1;
        for(int i=0; i<n; i++){
            for(int smaller=0; smaller<2; smaller++){
                for(int j=0; j<2; j++){
                    for(int x=0; x<=(smaller ? 9 : N[i]-'0'); x++){
                        dp[i+1][smaller | x<N[i]-'0'][j or x==4 or x==9] 
                        += dp[i][smaller][j];
                    }
                }
            }
        }
        return dp[n][0][1] + dp[n][1][1];
    };
    cout << digit_dp(B) - digit_dp(C) << ln;
}

ABC007 D - 禁止された数字

atcoder.jp
桁DPの典型的な問題

【題意】
自然数区間[A, B]において、4または9を含む整数はいくつあるか?
【典型ポイント】
1~Nの数え上げは桁DP
区間
【方針】
dp[i][smaller][j]:=1~Nの整数のうち、前方i桁まで見て、4または9が含まれている(j==1)か含まれていない(j==0)場合の数
smaller:未満フラグ
・遷移( dp[i+1][smaller | x

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
constexpr long long INF = 1000000000 + 100;
constexpr long long LINF = 1000000000000000000 + 100;
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
#define rrep(i, n) for(int i=(n); i>=0; i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
    ll A; string B, C; cin >> A >> B;
    C = to_string(A-1);

    auto digit_dp = [&](string N) -> ll{
        const int n = N.size();
        ll dp[n+1][2][2]{};
        dp[0][0][0] = 1;
        for(int i=0; i<n; i++){
            for(int smaller=0; smaller<2; smaller++){
                for(int j=0; j<2; j++){
                    for(int x=0; x<=(smaller ? 9 : N[i]-'0'); x++){
                        dp[i+1][smaller | x<N[i]-'0'][j or x==4 or x==9] += dp[i][smaller][j];
                    }
                }
            }
        }
        return dp[n][0][1] + dp[n][1][1];
    };
    cout << digit_dp(B) - digit_dp(C) << ln;
}

ABC195 - E Lucky 7 Battle

atcoder.jp
ゲーム系。
勝負が確定している後ろからDPする(バックトラックというらしい)
この方針は正しかったが、7の倍数判定を無駄に考えすぎて解けず。

【問題】
数列が与えられる。
文字列の手番に従って、高橋君と青木君は新しい数列の末尾にS[i]か0を加える。
最終的に出来た数列が7の倍数なら高橋君の勝ち。
お互い最適に動いたとき、高橋君はゲームに勝てるか?
【典型ポイント】
バックトラック
10の階乗のmodを前計算する
倍数系の問題は都度modを取りながら進められる
【方針】
以下のようなDPテーブルを作る
dp[i][mo]:= i手目まで進んだ時の、余りがmoである場合に高橋君が勝てるかどうか
メモ化でDPする方法が分からなかったので他の人のコードを真似した。書けるようになると楽かもしれない

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
constexpr long long INF = 1000000000 + 100;
constexpr long long LINF = 1000000000000000000 + 100;
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
#define rrep(i, n) for(int i=(n); i>=0; i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int p[201010]; //10の階乗 mod 7
bool memo[201010][7], seen[201010][7];
int main(){
    int N; string S, X; cin >> N >> S >>X;

    p[0] = 1; rept(i, 1, 201010)p[i]= (p[i-1] * 10) % 7;

    //メモ化再帰
    //func(i, mo):=i回目の操作が確定していて、確定している数字を7で割った余りがmoのとき、高橋君の勝ち状態であるか
    auto func = [&](auto&& self, int i, int mo) -> bool{
        if(i==N)return mo == 0;

        if(seen[i][mo])return memo[i][mo];
        seen[i][mo] = true;

        if(X[i] == 'T'){
            //add S[i]
            if(self(self, i+1, (mo + (S[i] - '0') * p[N-i-1]) % 7)) return memo[i][mo] = true;
            //add 0
            if(self(self, i+1, mo))return memo[i][mo] = true;

            return memo[i][mo] = false;
        }
        else{
            //add S[i]
            if(!self(self, i+1, (mo + (S[i] - '0') * p[N-i-1]) % 7)) return memo[i][mo] = false;
            //add 0
            if(!self(self, i+1, mo))return memo[i][mo] = false;

            return memo[i][mo] = true;
        }
    };
    cout << (func(func, 0, 0) ? "Takahashi" : "Aoki") << ln;
}