トポロジカルソートの直観的理解

おさらい: トポロジカルソートとは

トポロジカルソートは、DAGをソートして右にあるノードから左へエッジが伸びないようにするソート。

アルゴリズムはこんな感じ

1. 入次数が 0 のノードをすべてキューへ積む
2. キューからノードを取り出す
3. 取り出したノードから出ている辺を削除
4. 削除した結果、入次数が0のノードが増えたらキューへ積む
5. 以下キューが空になるまでくり返す
6. もし、キューが空なのにまだ入次数が1以上のノードがあったらDAGではないと判断

トポロジカルソートの動作原理

ポイントは 入次数が0のノード だ。入次数が0のノードは、ソート済み配列の末尾へ加えてよい。なぜなら入次数0ということは、未追加のノードからの辺がないから。右から左へと伸びる辺がないように並べるのがトポロジカルソートなので、これで動く。

一応コードも載せておく

void topological_sort(int N, int M, vector<int> A, vector<int> B) {
  vector<int> input(N, 0);  // 各ノードの入次数
  vector<vector<int>> edge(N, vector<int>());
  rep(i, M) {
    edge[A[i]].push_back(B[i]);
    input[B[i]]++;
  }
  queue<int> q;  // 入次数0のノードを積んでいくキュー
  rep(i, N) {
    if (input[i] == 0) q.push(i);
  }
  vector<int> ans;
  while (!q.empty()) {
    int p = q.front();
    q.pop();
    ans.push_back(p);
    // p から出ている辺を削除する
    for (const auto& e : edge[p]) {
      --input[e];
      if (input[e] == 0) {
        q.push(e);
      }
    }
  }
  if ((int)ans.size() != N) {
    // DAG でないのでトポロジカルソートできない
    cout << "Not DAG!" << endl;
    return;
  }
  cout << "result:" << endl;
  for (const auto& e : ans) {
    cout << e << " ";
  }
}

EDPCを3周して掴んできた勘所

後半のT以降はまだ1回も解けてないのですが、Sまでは3周したのでメモです。

ひたすら「メモ化再帰」と思い込む

いきなりdpの配列を想像すると脳がパンクするので、まずはメモ化再帰を書いてみてください。メモ化再帰から始める利点としては以下が挙げられます。

• 求めたい値がわかる
• ループ方向がわかる

たとえばEDPCのFrog 2ですが、以下のようなdfsが考えられます(※ネタバレ注意)。

int dfs(int n) {
  // 今足場n+1にいる
  if (n == N-1) return 0; // ゴールにいるなら当然コストは0
  if (dp[n] != -1) return dp[n]; // メモがあれば使う
  int ans = INF;
  rep(i, K) {
    if (n+i+1 >= N)
      break;
    ans = min(ans, abs(h[n] - h[n+i+1]) + dfs(n+i+1));
  }
  return dp[n] = ans;
}

求めたい値はdp[0]？dp[N]？

このdfsは「足場n+1からNまでにかかるコスト」を求めています。そのため求める答えはdfs(0)です。さらに言えばこれはdp[0]の値でもあります。

dpを配列でいきなり書こうとすると「あれ？求める答えってdp[0]？dp[N]？それともdp[N-1]？」と混乱してしまいますが、「これはメモ化再帰なんだ」と思い込めばdp[0] = dfs(0)と分かるので混乱が起きにくいです。

逆に言えば、dfs(n) != dp[n]となるようなdpの設計は基本的には避けたほうが良いです。ひたすらdpは部分問題の解を表すように気をつける、これだけでも大分書きやすくなるはずです。

ループの方向がわかる

徐々にdpになれて来ても、forを逆順で回すか順に回すかわからなくなることがあります(これは添字の設計にも関わります)。しかし、一度dfsを頭のなかでイメージすれば、「どこが真っ先に計算されるか？」がわかります。上の例ではdfs(0)の計算 dfs(1)、dfs(2)…dfs(K)が計算されたあとにされます。そのため、上のdfsをforループで書く場合は添字が大きいほうから埋まっていくように書けば良いとわかります。

ちなみに、添字が小さいほうからループを回したいときはdfsの引数を「あとn個段差がある」としてやれば良いです。この場合は求める答えがdfs(N)となります。

小手先のテクがわかってないと解けないことがある

dpには累積和を使うことでO(N³)がO(N²)になるといった方法があります。しかし、これは知っていないとなかなか出てきません。結局EDPCを何度もやるなど、量をこなさなければこういった知見は身につきません。

また、bitDPは比較的有名でも、それを使ってグループ分けができることなどは一度考察したことがないとなかなか発想として出てこないです。

結論

こんな記事を読んだところで結局はEDPCやらないと勘所を掴めないよ

ARC007 C 節約生活

問題設定がけっこうややこしいので本文を読んでください

C - 節約生活

解説

まず、答えがN以下であることは明らかだ。なぜならoが1個は含まれるので、oをN個並べてやればそれ以降条件を満たすからだ。

これをさらによく考えてみる。まず、Sの後ろにもうひとつSをくっつけたS'を考える。すると、S'の後半N個がすべてoになれば条件を満たすことがわかる。

あとはS'を作ってテレビのつけかたを全通り試してやればよい。Nが10とかなり小さいので多少強引でも解ける。

提出

1269 B. Modulo Equality

Problem - 1269B - Codeforces

問題概要

長さNの数列A,Bを与えられる。Aの各要素にXを足し、Mで割った数列をCとする。Cを並べ替えるとBと一致するとき、Aに足すべき最小のXを求めよ。

入力

1. 1 ≦ n ≦ 2000
2. 1 ≦ m ≦ 10⁹
3. 0 ≦ a_i < m
4. 0 ≦ b_i < m

解答

まずソートする。次にAの各要素にMを足した数列をAの後ろにくっつけてやる。これで考察はほとんど終わりである。

たとえば

• n=4
• m=3
• A = [0, 0, 2, 1]
• B = [2, 0, 1, 1]

このとき、先程いったことをすると以下のようになる

A' = [0, 0, 1, 2, 3, 3, 4, 5]

B = [0, 1, 1, 2]

あとはA'から切り出した長さNの部分列とソート済みのBを比較して、各要素の差が等しいならばそれが答え候補となる。今回でいえば、「2, 3, 3, 4」という部分列とBは各要素の差が等しい。あとは部分列からXを逆算すれば良い。

今回のキモはソートできること、Mで割る操作を別のことに変換することだ。

1278 B. A and B

Problem - 1278B - Codeforces

問題概要

A,Bの2数が与えられる。これらに対し、以下の操作を行う。

1. 片方を選ぶ
2. n回目の操作だとしたら、選んだ数へnを足す

A,Bを等しくするには最小で何回の操作が必要か答えよ。入力はT個与えられる。

制約

1. 1 ≦ A,B ≦ 10⁹
2. 1 ≦ t ≦ 100

解答

この問題は以下のように言い換えられる。

1. AとBの差の絶対値をdiffとする
2. 1からnのうちいくつかをマイナスにする
3. それらの総和をdiffにする

たとえば差の絶対値が5のときは次のようにすれば良い。

1 + 2 + 3 + 4 + 5 = 15
1 + 2 + 3 + 4 - 5 = 5

この観察から以下が言える。

1. 最低でも1からnまでの総和はdiff以上でなければならない
2. あるmをマイナスにすると、総和は2m減る

ここまで分かればおおよその方針ができる。まず、diff以上となるnを探す。もし、1からnの総和とdiffの偶奇が等しければnが答え。等しくなければ偶奇が等しくなるまでnを増やす。

証明

まず、1から(n-1)の総和をS'、1からnまでの総和をSとする。また、S' < diff ≦ Sとする。

S' + n = Sより、S' < diff ≦ S' + nである。

さらに、 0 < diff - S' ≦ nである。

ここでdiff - S' = 2kとする。0 < 2k ≦ nよりkは1からnに含まれている。よってkのみマイナスとすれば総和がdiffと一致する。

もしdiff - S'が奇数ならば、どのようにしても総和とdiffは一致しない。これを解消できる最小のnが答えなのは明らか。

降順ソートされたコンテナでlower_bound

わかればそれはそうか、となるのですが頭に入ってないとこの発想が出てこなそうなので書いておきます。

やり方はメチャクチャ簡単です。

lower_bound(v.rbegin(), v.rend(), value);

これだけです。ポイントは逆イテレータを渡していることです。たったそれだけで降順ソートしたコンテナをあたかも昇順ソートされているように扱えるわけです。使える場面が多いのでぜひ覚えておきたいテクニックですね。

Vimでライブラリをスニペットとして登録する

僕は今まで競プロ用のライブラリをファイルとして保存しておいて、それをコピペするスタイルを取っていました。しかし、いささか面倒になってきたのでスニペット化してみました。

実現したいこと

たとえばmint.cppというファイルがあるとします。

template<int MOD>struct MInt {
// 実装
};
using mint = MInt<1000000007>;

これをlibmintでスニペットとして呼び出せるようにします。

スニペット設定を生成

以下のようなディレクトリ構造を想定しています。

./create.sh
./library
  - mint.cpp
./snippets

このとき、以下のcreate.shを実行するだけでNeosnippet用の設定ファイルが生成されます。

#!/bin/bash
absolute_pwd=$(cd $(dirname $0); pwd) # create.shがあるディレクトリの絶対パス
snip_dir=$absolute_pwd/snippets

mkdir -p $snip_dir # snippetファイルが生成されていくディレクトリ
for path in $(ls ./library/*.cpp); do
    filename=$(basename $path .cpp)

    echo "snippet lib${filename}" > $snip_dir/${filename}.snip
    cat $path | sed -e 's/^/ /g' >> $snip_dir/${filename}.snip
done

# 使いやすい場所へシンボリックリンクを張る
[ -e "$XDG_CONFIG_HOME/nvim/snippets/library" ] || ln -sf $absolute_pwd/snippets $XDG_CONFIG_HOME/nvim/snippets/library

あとは$ bash create.shを実行するだけでスニペットファイルが生成されます。

備考

最後のシンボリックリンクは必要に応じて使ってください。たとえばneosnippetが読み込むディレクトリ以下にあるcpp.snip(~/.config/nvim/snippets/cpp.snipなど)に以下のように書いていた場合はシンボリックリンクを張っておくと便利です。

include ./library/*.snip

C++でpriority_queueを実装する

(競プロ以外の場面で)優先度付きキューを自力で実装する必要に迫られたので、自力で実装してみました。二分ヒープをベースに実装してあります。

※いくつかのメソッドは実装していません

実装

#include <vector>
#include <functional>

template <class T,
         class Container = std::vector<T>,
         class Compare = std::less<typename Container::value_type>>
         class priority_queue
{
  Container v;
  int size = 0;
  public:
  void push(T val) {
    int index = size;
    v.push_back(val);
    ++size;

    for (int parent = (index-1) / 2;
        parent >= 0 && Compare()(v[parent], v[index]);
        index = parent, parent = (index-1)/2) {
      T tmp = v[index];
      v[index] = v[parent];
      v[parent] = tmp;
    }
  }
  void pop() {
    v[0] = v[size-1];
    v.pop_back();
    --size;

    for (int index = 0, l = 1, r = 2;
        l < size && (Compare()(v[index], v[l]) || Compare()(v[index], v[r]));
        l = index * 2 + 1, r = index * 2 + 2) {
      int target = l;
      if (Compare()(v[index], v[r])) target = r;
      if (Compare()(v[index], v[l]) && Compare()(v[index], v[r]))
        if (Compare()(v[r], v[l])) target = l;
        else target = r;

      T tmp = v[index];
      v[index] = v[target];
      v[target] = tmp;
      index = target;
    }
  }
  T top() { return v.front(); }
  bool empty() { return size == 0; }
};

標準入力がちょっとだけ楽になるテンプレート

書きやすさ・使いやすさ・応用性の高さから便利だよという紹介です。

#define in(v) v; cin >> v;

int main() {
  int in(N);
  // int in(M);
  // int in(H); int in(W);

  rep(i, N) {
    int in(a);
    // cin >> A[i];
  }

  return 0;
}

解説

このin()マクロを使うと、変数の定義と入力を受け取る部分が分離しません。

メリット: 変数名を変更するとき変える箇所が少ない

int N, M, K; cin >> N >> M >> K;

このようなテンプレートを使っているとき、N、MをそれぞれHとWに変えたくなったら4箇所も変えなければなりません。

int H, W, K; cin >> H >> W >> K;

しかし、in()マクロなら2箇所で済みます。

int in(N); int in(M); int in(K);
// これを直すと
int in(H); int in(W); int in(K);

また、変数を増やすときもint in(N);をコピペして変数名を直すだけなので、非常に楽です。

グローバル変数へ移しやすい

他にも、たとえば変数をグローバルへ移したくなったとき、このマクロならばintをはずすだけで済みます。

int N;
int main() {
  // int in(N);
  in(N);
}