2023-01-09

ABC284 E - Count Simple Paths

try-catch DFS を布教したいだけ（twitter を眺めていたら見つけたのでパクっただけなんですが…）

問題

$N$ 頂点 $M$ 辺の単純無向グラフが与えられる。各頂点の次数は $10$ 以下である。頂点 $1$ からの単純パスの個数を $K$ とした時、 $min(10^{6}, K)$ を求めよ。

制約

$1 \le N \le 2 \times 10^{5}$
$0 \le M \le min(2 \times 10^{5}, \frac{N(N-1)}{2})$

解法

基本的には DFS で頂点 1 から順に辿ったパスの個数をカウントすればよい。
$K$ が $10^{6}$ を超える場合は当然 $10^{6}$ を出力すればいいが、このようにある時点で答えが確定する場合は try-catch 構文 を用いて例外処理として書くと便利である。

try-catch

基本的な構文は以下の通りである：

    try {
        // ここに実行する処理を記述
    } catch (<例外の型> e) { // 例外が投げられた場合（throw で例外を投げることができる）
        // 例外が投げられた場合の処理を記述
    }

try ブロック内で実行した内容で受け取れる例外が発生した場合、即座に catch ブロック内の処理が実行される。これを用いることで、再帰関数内で答えが確定した時に即座に答えを出力してプログラムを終了させることができる。具体的には、以下のように実装すればよい：

    auto dfs = [&](auto &&dfs, <dfs の引数>) -> void {
        if (<答えが確定した場合>) {
            // 答えを出力
            throw 0; // ここで例外を投げる
        }
        // dfs の処理を書く
    };
    try {
        dfs(dfs, <dfs の初期状態の引数>);
    } catch (int e) { // ここで例外を受け取る
        return 0;  // プログラムを終了する
    }

プログラムを即座に終了させるだけなら exit(0) などの手段があるが、例えばマルチテストケースの場合に exit(0) だと困ってしまう一方で、try-catch だと拡張が簡単である。

またこの手法を用いることで、次数が $10$ 以下という制約が無くとも簡単に問題を解くことができる。

ちなみに、自分は以下のようなマクロをテンプレートに定義している：

#define TRYDFS(dfs)   \
    try {             \
        dfs;          \
    } catch (int e) { \
        return 0;     \
    }

提出

atcoder.jp

#include <bitset>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 入力
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    // DFS 10^6 を超えた時点で例外処理として 10^6 を出力して終了
    int ans = 0;
    constexpr int MAX = 1000000;
    constexpr int N = 200000;
    bitset<N> reach(0);
    auto dfs = [&](auto &&dfs, int v) -> void {
        if (ans >=
            MAX) {  // 答えが確定した場合（ここでは、K が 10^6 を超えた場合）
            cout << MAX << "\n";  // ここで答えを出力
            throw 0;              // ここで例外を投げる
        }
        ans++;
        reach[v] = 1;
        for (int to : g[v]) {
            if (not reach[to]) {
                dfs(dfs, to);
            }
        }
        reach[v] = 0;
    };
    try {
        dfs(dfs, 0);
    } catch (int e) {  // ここで例外を受け取る
        return 0;      // プログラムを終了する
    }

    // 答えの出力
    cout << ans << "\n";
}

感想

try-catch DFS を用いて穏やかな生活へ

2022-10-20

ABC273 G - Row Column Sums 2

やっていること自体は公式解説と同じなのですが、状態の持ち方が割と素直かも？と思ったので

問題

atcoder.jp

$N$ 次正方行列であって、以下を共に満たすものの個数を $998244353$ で割った余りで求めよ。
・すべての $1 \le i \le N$ について、 $i$ 行目の総和が $R_i$ に一致
・すべての $1 \le i \le N$ について、 $i$ 列目の総和が $C_i$ に一致

制約

$1 \le N \le 5000$
$0 \le R_i, C_i \le 2$

解法

行の総和と列の総和が一致しない場合は明らかに条件を満たしえないので、以下は行の総和と列の総和が一致しているものとして考える。

$R_i$ の昇順に行を、 $C_i$ の昇順に列を並び替えたとしても求める値は変わらないので、そのように並び替えたものを考える。すると行列の内、 $R_i > 0, C_i > 0$ を満たすような右下の長方形領域だけを考えれば良いことが分かる。また、 $R_i = 1$ の行（以下 $1$ の行と定め、他についても同様に定める）についてどの列に $1$ を書き込むかが決まればその行はもう以後考える必要がなくなり、前の長方形領域よりも小さい長方形領域について考えれば十分になる。同様に $2$ の行についても書き込み方を定めていくことで、最終的な答えが求められる。以上のことを踏まえると再帰的な dp をしたくなり、以下のような状態を定めることができる。

$dp_{r1, r2, c1, c2}$ ： $1$ の行が $r1$ 行、 $2$ の行が $r2$ 行、 $1$ の列が $c1$ 列、 $2$ の列が $c2$ 列ある場合についての条件を満たす行列の書き込み方の個数

さて、あとはこの dp の遷移（詳細は下記実装を参照）を丁寧に一つずつ実装すれば正しい答えの求まるアルゴリズムになるが、問題は計算量である。一見状態数が $O(N^{4})$ で到底間に合わなさそうだが、よくよく考えてみると遷移先の状態において常に行の総和と列の総和の一致、すなわち $r1 + 2 \times r2 = c1 + 2 \times c2$ が成り立つので、 $r1$ と $r2$ が決まれば、 $c1$ は $c2$ が決まることで一意に定まることが分かる。また $1$ の行から処理していくことを考えると、 $r1 + r2$ は $O(N)$ であるので、実はとりうる状態数は $O(N^{2})$ で抑えられる。遷移も $O(1)$ なので実はこれを素直にメモ化再帰で実装するだけで AC できる。

なお、メモ化の際に素直に std::map<std::tuple<int, int, int, int>, mint> とかすると $log$ がついて TLE してしまうので、適切に状態を int 型で計算して、std::vector や std::unordered_map などでメモ化することで TL に間に合うようになる。詳細は実装例を参照。

atcoder.jp

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;

const mint inv2 = mint(1) / 2;
int R1, R2, C1, C2;
vector<int> memo; // メモ化再帰用の配列

int calcState(int r1, int r2, int c2) { // 状態を計算
  return (r1 + r2) * (C2 + 1) + c2;
}

mint dp(int r1, int r2, int c1, int c2) { // メモ化再帰
  if (r1 == 0 and r2 == 0 and c1 == 0 and c2 == 0) return 1;
  const int state = calcState(r1, r2, c2);
  if (memo[state] != -1) return memo[state];
  
  mint res = 0;
  if (r1 > 0) { // 1 の行から処理
    if (c1 > 0) res += dp(r1 - 1, r2, c1 - 1, c2) * c1; // 1 の列を 1 つ選んで 1 を書き込む
    if (c2 > 0) res += dp(r1 - 1, r2, c1 + 1, c2 - 1) * c2; // 2 の列を 1 つ選んで 1 を書き込む（1 の列に変化する）
  } else { // 2 の行の処理
    if (c1 > 1) res += dp(r1, r2 - 1, c1 - 2, c2) * c1 * (c1 - 1) * inv2; // 1 の列を 2 つ選んで 1 を書き込む
    if (c2 > 0) res += dp(r1, r2 - 1, c1, c2 - 1) * c2; // 2 の列を 1 つ選んで 2 を書き込む
    if (c1 > 0 and c2 > 0) res += dp(r1, r2 - 1, c1, c2 - 1) * c1 * c2; // 1 の列と 2 の列を 1 つずつ選んでそれぞれ 1 を書き込む
    if (c2 > 1) res += dp(r1, r2 - 1, c1 + 2, c2 - 2) * c2 * (c2 - 1) * inv2; // 2 の列を 2 つ選んで 1 を書き込む
  }
  return memo[state] = res.val();
}

int main() {
  // 入力　配列の要素をとりながら R1, R2, C1, C2 を count
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int r;
    cin >> r;
    if (r == 1) R1++;
    if (r == 2) R2++;
  }
  for (int i = 0; i < n; i++) {
    int c;
    cin >> c;
    if (c == 1) C1++;
    if (c == 2) C2++;
  }
  
  // 答えを出力　行の総和と列の総和が一致していない場合は 0 であることに注意
  if (R1 + 2 * R2 != C1 + 2 * C2) {
    cout << 0 << '\n';
  } else {
    memo = vector<int>((R1 + R2) * (C2 + 1) + C2 + 1, -1);
    cout << dp(R1, R2, C1, C2).val() << '\n';
  }
}

感想

ぱっと見で $O(N^{2})$ に収まるような状態の持ち方に見えなかったので、びっくりする。

2022-09-11

ABC268-G Random Student ID

問題

atcoder.jp

$N$ 人の新入生がいて、それぞれの名前が英小文字で与えられる。学籍番号は英小文字の順序に従って辞書順で並べたときの順番で 1-indexed に振られる。英小文字の順序をランダムに定義したとき、学籍番号の期待値は？

解法

例えば $abc$ という文字列を考えた時、英小文字の順序に依らず $ab$ よりは辞書順で後に振られることになる。また、 $abcd$ よりは前に振られる。これらの順序は「その文字列が他の文字列を接頭辞として含んでいるか、またその文字列が他の文字列の接頭辞として含まれているか」によって決められる。 $M$ 個の文字列の集合に対していずれのペアもこの関係を満たさない時は、集合の $1, \dots, M$ 番目になるかが等確率に決まる。

以上の性質を踏まえると、ある文字列集合 $S$ に含まれる文字列 $T \in S$ が $S$ 内で何番目になりうるかは、 $S$ 内で $T$ が $T$ 以外で接頭辞として含む文字列の個数を $X_T$ 、 $T$ 以外に $T$ を接頭辞として含む文字列の個数を $Y_T$ とすると、 $T$ より前に少なくとも $X_T$ 個、後ろに少なくとも $Y_T$ 個並ぶはずなので、

$X_T + 1, X_T + 2, \dots, N - Y_T$

のいずれかであり、これらの内から一つが等確率で与えられるので求める期待値は

$\frac{(X_T + 1) + (X_T + 2) + \dots + (N - Y_T)}{(N - Y_T) - (X_T + 1) + 1} = \frac{\frac{((N - Y_T) - (X_T + 1) + 1) ((X_T + 1) + (N - Y_T)}{2}} {(N - Y_T) - (X_T + 1) + 1} = \frac{X_T + 1 + N - Y_T}{2}$

$X_T, Y_T$ は文字列集合 $S$ を最初にソートしておき文字列 $T \in S$ を前から順に取り出していくことにして、接頭辞 $U$ が $T$ を調べるより前に出てきていれば $Y_U, X_T$ をそれぞれインクリメントすることで求められる。

atcoder.jp

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;

int main() {
  // 入力　S0 に元の順序を持っておくことにしてソートしておく
  int N; cin >> N;
  vector<string> S(N); for (int i = 0; i < N; i++) cin >> S[i];
  const auto S0 = S;
  sort(S.begin(), S.end());
  
  // 文字列 T について、T の接頭辞でありかつ S 内に含まれる文字列の個数 X[T] と、T を接頭辞として含みかつ S 内に含まれる文字列の個数 Y[T] の計算　ソートしておいた順番に計算
  map<string, int> X, Y;
  for (string T : S) {
    string U = "";
    for (char x : T) {
      U += x;
      if (Y.find(U) != Y.end()) {
        X[T]++;
        Y[U]++;
      }
    }
    Y[T] = 0;
  }
  
  // 答えを出力
  using mint = atcoder::modint998244353;
  const mint inv2 = mint(1) / 2;
  for (string T : S0) {
    mint ans = mint(X[T] + 1 + N - Y[T]) * inv2;
    cout << ans.val() << '\n';
  }
  
  return 0;
}

感想

trie 木について何も知らなかったし、今も分かっていないが、解けた。初めてコンテスト中に ABC-G を通せたので嬉しい。

2021-08-09

ABC213 F-H 個人的メモ

厳密性には欠ける可能性あり　数式はあまり使わないように（めんどくさいし、僕も分からなくなってしまうので）公式解説にかなり丸投げをしますし、そもそもあまり人に読ませることを想定していないので、ご了承・・・

F

問題文を読むと、いかにも ACL を使いそうな雰囲気
atcoder/string を見てみると、Suffix Array と LCP Array が何か使えそう。

Suffix Array：i 文字目から後ろの文字列（これを Suffix と呼ぶ）というのを考えたときに、辞書順になるような index の配列 LCP Array：文字列とその Suffix Array を考えたときに、隣り合っている文字列同士の先頭何文字が被っているかみたいなのを記録する配列

ここで一つ重要な性質として以下がある： 3つの文字列を辞書順で並べたときに $A, B, C$ の順だったとすると、 $LCP(A, C) = min(LCP(A, B), LCP(B, C))$

これは $B$ が $A$ の前何文字かをそのままに後ろをどう更新したか、あるいは $C$ が $B$ の前何文字かをそのままに後ろをどう更新したか、みたいなのを考えると直感的に納得がいく気がする。
これを一般化すると、任意の2つの Suffix の LCP というのは、Suffix Array で考えたときのその間の LCP の min であるということが分かる。
これを図にすると最大長方形っぽいやつに帰着できるので、stack でごにょごにょすると、できる（この辺りは、公式解説の動画の方を見ると分かる）（丸投げ！）

G

制約的に、見るからに bit DP
dp[S]: ちょうど連結成分の部分集合が S になっているようなのがあるグラフの通り数
とすれば、これは頂点集合が S であるようなグラフの全体から、頂点集合が S であってそれが連結成分にならないようなものを引けばいいので、解説に書いてあるような式が立つ（丸投げ）
求める値は部分集合に頂点 1 と頂点 i を含むような部分集合の dp に、補集合は何でもいいので、2^{補集合の辺の本数} をかけた値の総和（ちょうど、という風にしていることで上手く区別ができている）

H

どんな遷移も左から右に遷移している、というのがミソで、自分からの遷移が出る、ということは自分への遷移はもうない、ということになる。
こういう場合の時は分割統治というのが使えるらしい（公式解説の動画がかなり分かりやすいので、それを見た方が早い気がする・・・）
遷移式を見ると、添え字の和の部分が一定の積の和となっていて、これはいかにも FFT
畳み込みというと嫌な気持ちになるけど、積の和というとそうでもない気がする（僕だけ？）
あとは、これを実装する　実装は公式解説の動画を見ると完全理解ができる（嘘かも）

2021-03-21

ABC196 D - Hanjo

ざっと見て自分と同じ解法の人がいなかったので

問題

atcoder.jp

解法

制約が小さいのでbitDPみたいなのが考えられそう．2×1の畳の敷き方が決まれば全体の敷き方も一意に決まるので，以下は2×1の畳を敷いた状態を考える．
dp[bit][j]:2×1の畳をちょうどj枚敷いた時の”敷く順番を考慮した場合の”敷き方
とする．ここでbitは敷き詰められたマスの集合を表す．敷く順番を考慮するというのがミソで，この条件を敷いてやることで遷移が一意に決まる．具体的には以下の通りに書ける（自明な気もするが）．
dp[bit|(1<<i)|(1<<ni)][j+1]+=dp[bit][j]
ここでiとかniというのは畳を敷く時に埋められるマスを表す．あとはこの遷移をぶん回してdpテーブルの各値を求めたあとにsum(dp[bit][A])を求めて，A!で割ってやることで答えが求まる．

提出

atcoder.jp

#include<bits/stdc++.h>
using namespace std;

int main(){
  //input
  int h,w,a,b;
  scanf("%d%d%d%d\n",&h,&w,&a,&b);
  const int N=h*w;
  std::vector<std::vector<long long>> dp(1<<N,std::vector<long long> (a+1,0));
  //bitDP
  dp[0][0]=1;
  for(int bit=0;bit<1<<N;bit++){//occupy
    for(int j=0;j<a;j++){//2*1 count
      for(int i=0;i<N;i++){//start
        for(int dir=0;dir<2;dir++){//direction 0:↓ 1:→
          int newbit=bit;
          int ni=i;
          if(dir){
            if(i%w==w-1)continue;
            ni++;
          }else{
            if(i/w==h-1)continue;
            ni+=w;
          }
          if((bit>>i)&1)continue;
          newbit|=1<<i;
          if((bit>>ni)&1)continue;
          newbit|=1<<ni;

          dp[newbit][j+1]+=dp[bit][j];
        }
      }
    }
  }
  //sum&div
  long long ans=0;
  for(int bit=0;bit<1<<N;bit++){
    ans+=dp[bit][a];
  }
  for(int i=1;i<=a;i++)ans/=i;
  //output
  printf("%lld\n",ans);
  return 0;
}

2021-03-19

ABC194 F - Digits Paradise in Hexadecimal

問題

atcoder.jp

解法

いわゆる「桁DP」と呼ばれるやつまあ桁DPがよく分からなくてもとりあえず動的計画法っぽいことを認識できれば良し（種類数を管理しながら・・・とかを考えるとDPでやりたいお気持ちになってくる）
dp=(上からi桁目まで見た時にn未満になることが分かるような条件を満たす数の個数）
として考える．
今まで出てきた数字を全部管理しちゃうとかすると，
dp[n.size()][1<<16][k]
とかみたいなテーブルがまず思いつくが，当然壊れちゃうのでもう少し工夫する必要がある．

まずnより小さくなる数sにどういう性質があるかを考えてみると，以下のような性質が見つかる．
・nの桁数より少ない
・nと桁数は一致していて，頭の方は同じだがn[i]<s[i]となるような箇所より前にn[i]>s[i]となるような箇所が存在する

前者の条件については簡単で，後ろの方の桁から始めればよい．後者については，その小さくなるのが確定する桁iについて，0~n[i]-1までを考えてやればいい．ただし，その数字が今まで出てきたことがある場合とそうでない場合で種類数が変わってしまうため，その部分は今まで出てきた数字を管理して探索してやればいい．
今までの桁で小さくなるのが確定している数字については，どの数字を使ってもn未満になるが，今まで出てきた種類数をjとすれば，出てきていない種類数は16-jであり，どっちを使うかで種類数が変わるためその部分の遷移を記述すれば良い．
以上のことを考えると以下のようなdpテーブルができ，これは空間計算量O(k*n.size())となってなんとかなりそうなのが分かる
dp[i][j]:頭から見てi桁目まで見た時に，n未満となるのが確定していて，出てくる種類がちょうどj個となるような数字の個数
ただし問題文はn"以下"を求めるように言っているので，もしnそのものが条件を満たす場合はそれを答えに加える必要があることに注意する．

提出

atcoder.jp

#include<bits/stdc++.h>
#include <atcoder/modint>
using namespace atcoder;
using namespace std;
using mint=atcoder::modint1000000007;
signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  string n;cin>>n;
  int k;cin>>k;
  int sz=(int)n.size();

  std::vector<std::vector<mint>> dp(sz+1,std::vector<mint> (17,0));//dp[i][j]:上からi桁目まで見た時に数字がj種類出てきてかつnより小さくなるような数の個数.最終的に求める答えはdp[sz][k](+もしnそのものが条件を満たす場合は+1する)
  set<char>st;//今まで出てきた数字を管理する
  auto itoc=[&](int i)->char{//数字を文字に変更
    if(i<10)return (char)(i+'0');
    else return (char)(i-10+'A');
  };
  auto ctoi=[&](char c)->int{//文字を数字に変更
    if(isdigit(c))return c-'0';
    else return c-'A'+10;
  };

  for(int i=0;i<sz;i++){
    if(i)dp[i+1][1]+=15;//上から見た時にnより小さい桁から始まるとすると明らかに小さい

    //i-1桁目まで一致していて，i桁目で小さくなることが確定する場合を考える
    //n[i]より小さい数になれば明らかにその数はnより小さくなるが，その数字が今まで出てきたかどうかで種類数が変わるので，その部分は全探索
    int kind=(int)st.size();//これまでに出てきた数字の種類数
    for(int j=0;j<ctoi(n[i]);j++){
      if(kind==0 and j==0)continue;//先頭の桁が0になるのは上で数えるので飛ばす
      if(st.find(itoc(j))!=st.end()){//今まで出てきたやつ
        dp[i+1][kind]++;
      }else{//初めて出てくるやつ
        dp[i+1][kind+1]++;
      }
    }
    st.insert(n[i]);
    //今までで小さいのが確定している数字の遷移
    for(int j=0;j<=k;j++){
      dp[i+1][j]+=dp[i][j]*j;//今まで使った数字を使えばもちろん種類数は変わらない
      if(j+1<17)dp[i+1][j+1]+=dp[i][j]*(16-j);//今までに使ったことのない数字を使えば当然種類数は1だけ増える（配列外参照に注意）
    }
  }
  dp[sz][st.size()]++;//ｎぴったりの分の加算
  printf("%d\n",dp[sz][k]);
  return 0;
}

2021-03-03

ABC193 F- Zebraness

フローを理解するためのいい問題だった

atcoder.jp

解法

こういうある状況と２種類の操作が与えられるので，どっちかに振り分けて最適にする感じの奴はmaxflowにだいたい帰着できる（多分）

詳しくはこれに色々書いた

cprgrma2.hatenablog.com

この問題における状況はこんな感じに整理できる

操作P:マスを以下の盤面と対応するマスの色で塗る

操作Q:マスをこの盤面と対応するマスの色でない方の色で塗る

WBWBWBWBWBWBWBWB....

BWBWBWBWBWBWBWBW....

WBWBWBWBWBWBWBWB....

BWBWBWBWBWBWBWBW....

WBWBWBWBWBWBWBWB....

BWBWBWBWBWBWBWBW....

この2つの操作で割り当てるのを考えると，最小カット問題に帰着できそうである．

最小カットはコストを最小化する問題であるので，一見値を最大化したいこの問題にうまく適用できないように思うかもしれないが，元々それぞれ隣り合う頂点間に辺が張られていて，そこからカットする辺の本数をできるだけ少なくする問題だと思うと結局最小カットで解けるのが分かるだろう．よって最初にans=2*n*(n-1)としておいて，そこから後で最小カットを引いてやれば良い．

すると，各グリッドの隣り合う頂点間（u→v）のコストは以下のように定義できる．

・頂点uが操作Pで塗られた場合，頂点vが操作Pで塗られていたらコスト0，操作Qで塗られていたらコスト1だけかかる

・頂点uが操作Qで塗られた場合，頂点vが操作Pで塗られていたらコスト1，操作Qで塗られていたらコスト0だけかかる

要するに異なる操作によって塗られていればそれを消すコストとして1が，同じ操作によって塗られていればそれは消す必要がないのでコスト0というふうにすれば良い．

また，今は「塗る」というその頂点に何も色が定義されていない前提であったが，もちろん元々黒の頂点を白で塗ることはできない．よって，以下をさらに定義する．

・頂点uの元の色が操作Pで塗られた時と色が一致する場合，操作Pで塗ったときはコスト0が，一致しない場合はコストINFがかかる

・頂点uの元の色が操作Qで塗られたときと色が一致する場合，操作Pで塗ったときはコストINFが，操作Qで塗ったときはコスト0がかかる

要するに，一致していれば元々その色で塗られていたのだからコスト0，そうでなければそれは違法なので莫大なコストがかかる，とすればいい．

あとは上記の関係性に従って，上の記事のチートシートに従い，辺を張って流せばよい．

atcoder.jp

解いたやつについてざっくばらんに

競プロをやる

ABC284 E - Count Simple Paths

問題

制約

解法

try-catch

提出

感想

ABC273 G - Row Column Sums 2

問題

制約

解法

感想

ABC268-G Random Student ID

問題

解法

感想

ABC213 F-H 個人的メモ

F

G

H

ABC196 D - Hanjo

問題

解法

提出

ABC194 F - Digits Paradise in Hexadecimal

問題

解法

提出

ABC193 F- Zebraness

解法