けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 0115 Starship UAZ Advance

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0115
三次元幾何

問題概要

三次元空間上で、線分 s と三角形領域 t が与えられる。
s と t とが交点をもつかどうか判定せよ。

解法

まず、sを延長した直線と、tを延長した平面との交点 p を求める (三次元幾何版の交点ライブラリが必要になる)

  • p が線分 s 上にある
  • p が三角形領域 t 上にある

をともに満たすかどうかを判定する。
2 については、面積計算を用いるのが簡単である。

コード

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

typedef double DD;
const DD EPS = 1e-10;

struct Point3D {
    DD x, y, z;
    Point3D(DD x = 0.0, DD y = 0.0, DD z = 0.0) : x(x), y(y), z(z) {}
};

Point3D operator + (const Point3D &p, const Point3D &q) {return Point3D(p.x + q.x, p.y + q.y, p.z + q.z);}
Point3D operator - (const Point3D &p, const Point3D &q) {return Point3D(p.x - q.x, p.y - q.y, p.z - q.z);}
Point3D operator * (const Point3D &p, DD a) {return Point3D(p.x * a, p.y * a, p.z * a);}
Point3D operator * (DD a, const Point3D &p) {return Point3D(a * p.x, a * p.y, a * p.z);}
Point3D operator / (const Point3D &p, DD a) {return Point3D(p.x / a, p.y / a), p.z / a;}
Point3D cross (const Point3D &p, const Point3D &q) {
    return Point3D(p.y * q.z - p.z * q.y, p.z * q.x - p.x * q.z, p.x * q.y - p.y * q.x);
}
DD dot(const Point3D &p, const Point3D &q) {return p.x * q.x + p.y * q.y + p.z * q.z;}
DD abs(const Point3D &p) {return sqrt(dot(p, p));}
DD area(const Point3D &a, const Point3D &b, const Point3D &c) { return abs(cross(b - a, c - a)) / 2; }

struct Line3D : vector<Point3D> {
    Line3D(const Point3D &a = Point3D(), const Point3D &b = Point3D()) {
	this->push_back(a);
	this->push_back(b);
    }
};

struct Plane : vector<Point3D> {
    Plane(const Point3D &a = Point3D(), const Point3D &b = Point3D(), const Point3D &c = Point3D()) {
        this->push_back(a);
        this->push_back(b);
        this->push_back(c);
    }
};

vector<Point3D> crosspointSPL(const Line3D &s, const Plane &pl) {
    vector<Point3D> res;
    Point3D ph = cross(pl[1] - pl[0], pl[2] - pl[0]);
    DD baseLength = dot(s[1] - s[0], ph);
    if (abs(baseLength) < EPS) return vector<Point3D>();
    DD crossLength = dot(pl[0] - s[0], ph);
    DD ratio = crossLength / baseLength;
    if (ratio < -EPS || ratio > 1.0 + EPS) return vector<Point3D>();
    res.push_back(s[0] + (s[1] - s[0]) * ratio);
    return res;
}

Point3D my, en, bar[3];
int main() {
    while (cin >> my.x >> my.y >> my.z >> en.x >> en.y >> en.z) {
        for (int i = 0; i < 3; ++i) {
            cin >> bar[i].x >> bar[i].y >> bar[i].z;
        }
        Line3D myen(my, en);
        Plane barier(bar[0], bar[1], bar[2]);
        vector<Point3D> cps = crosspointSPL(myen, barier);
        if (cps.empty()) cout << "HIT" << endl;
        else {
            Point3D cp = cps[0];
            if (area(cp, bar[1], bar[2]) + area(cp, bar[2], bar[0]) + area(cp, bar[0], bar[1]) - area(bar[0], bar[1], bar[2]) > EPS)
                cout << "HIT" << endl;
            else
                cout << "MISS" << endl;
        }
    }
}

Codeforces Round #360 (Div. 1) A. NP-Hard Problem (R1500)

# 問題概要
無向グラフ (頂点数 n, 枝数 m) が与えられる。
このグラフの頂点集合を互いに disjoint な 2 つの集合 A, B に分割して、
A, B がともに vertex cover となっているようにせよ。
そのようなものが存在しなければ -1 をリターンせよ。


# 制約
2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000


# 解法
二部グラフとなっているかどうかを判定する。
なっていれば、それぞれの頂点集合を出力する。


# コード

```cpp
#include
#include
#include
#include
#include
#include
using namespace std;

const int MAX = 210000;
vector G[MAX];

int seen[MAX];
vector Left, Right;

bool cannot = false;
void dfs(int v, int color) { // 1: left, 2: right
seen[v] = color;
if (color == 1) Left.push_back(v);
if (color == 2) Right.push_back(v);
int next_color = 3 - color;
for (int i = 0; i < G[v].size(); ++i) {
int to = G[v][i];
if (seen[to]) {
if (seen[to] != next_color) {
cannot = true;
}
}
else {
dfs(to, next_color);
}
}
}

int main() {
int n, m;
while (cin >> n >> m) {
for (int i = 0; i < MAX; ++i) G[i].clear();
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
--a; --b;
G[a].push_back(b);
G[b].push_back(a);
}
for (int i = 0; i < MAX; ++i) seen[i] = 0;
Left.clear(); Right.clear();
cannot = false;
for (int v = 0; v < n; ++v) {
if (seen[v]) continue;
dfs(v, 1);
}

if (cannot) cout << -1 << endl;
else {
cout << Left.size()<< endl;
for (int i = 0; i < Left.size(); ++i) {
cout << Left[i] + 1;
if (i != (int)Left.size() - 1) cout << " ";
}
cout << endl;
cout << Right.size()<< endl;
for (int i = 0; i < Right.size(); ++i) {
cout << Right[i] + 1;
if (i != (int)Right.size() - 1) cout << " ";
}
cout << endl;
}
}
}
```

O(2^n)から計算量を減らす問題

この記事は、Competitive Programming Advent Calendar Div2013の22日目の記事として書きました。

今年は「ナイーブにやるとO(2^n)になりそうな問題の計算量を落とす系の問題」を集めました。例えば、区間スケジューリング問題は、ナイーブに全探索しようと思うとn個の区間に対してそれぞれ「選ぶ」or「選ばない」の2択を行うO(2^n)の解法になりますが、Greedyアルゴリズムによって効率的に解くことができます。

このような問題のうち、特に、多項式時間や擬多項式時間で効率よく解けるものを中心に集めました。難易度としてはSRM DIV2 Hard、SRM DIV1 Medium程度のものが多いです。なお、個々の問題や解法についての説明はとてもあっさりしたものになっております。

また、個人の趣味の記事ということでインフォーマルな書き方をしております。競技プログラミング界隈の人々に少しでも楽しんで頂けたら嬉しいです。


0. まえがき

ところで、ナイーブにやるとO(2^n)な問題というのは多岐に渡ります。最適化問題であれば

  min  f(x1, x2, …, xn)
  s.t.  xi = 0 or 1
     様々な制約条件

という形の問題はこの枠組みで捉えられますし、数え上げ問題であれば

  find  (x1, x2, …, xn)の組の個数
  s.t.  xi = 0 or 1
     様々な制約条件

の形になります。
この「様々な制約条件」の形によって、想定解法がDPだったり、連立一次方程式だったり、最小カットだったりします。

そこで逆に、ナイーブO(2^n)な問題に対する解法を色々と整理しておくと、そのような問題に挑みやすくなるのではないかと考えました。「こういう制約の形だから最小カットだなー」とか、あるいは反対に、「最小カットになるように制約を弄れないかなー」という感じです。僕に知っている範囲で、過去にコンテストで出題された問題たちを題材に種々の解法をまとめてみます。


1. DP
  
2. 連立1次方程式
  
3. 最小カット
  
4. 最大独立集合問題
  
5. Greedy
  
6. その他
  


1. DP

O(2^n)から計算量を落とす競プロの問題と言えば、圧倒的にDPが多いように思います。とりわけSRM DIV2 Hardでは、「O(2^n)だなーと思ったら、前から順番に見ていくDP!」と意識するだけでも、2割くらい解ける気がします!

何故、O(2^n)な問題がDPで解けることが多いかを考えてみると、「現在の選択が遠い未来にまで直接的には影響を及ぼさない」という状況によって、自然に前から順番に見ていくDPがフィットするケースが多いです。

逆に、前から順番に見ていくDPに帰着しようと思うと、予めn個のモノをソートしておくパターンがあります。


ナップサック問題

ナイーブO(2^n)な問題をDPによって効率的に解く問題と言えば、ナップサック問題が頻繁に取り上げられます。

概要
n個の品物があり、それぞれ重さと価値がwi, viとなっている。
これらの品物から重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めよ。

制約
・1 ≦ n ≦ 50
・1 ≦ wi, vi ≦ 100
・1 ≦ W ≦ 10000

Examples
0) 
 n = 6
 (w,v) = {(2,3), (1,2), (3,6), (2,1), (1,3), (5,85)}
 W = 8

 Returns : 91 (2, 5番の品物を選んだときが最大です)

この問題は例えば

dp[i+1][j] := i番目までの品物から重さの総和がj以下となるように選んだときの価値の総和の最大値

としてDPを構成して解くことができます。計算時間は、O(nW)となります。詳しくは、診断人さんの記事を参照してもらえらばと思います。


重み付き区間スケジューリング問題

上のナップサック問題に対するDP解法は、O(2^n)より速いですが擬多項式時間になっております。一方、「前から順番に見ていくDP」によって本当に多項式時間にできる問題もあります。

概要
n個の区間[si, ti](i = 1, 2, …, n)があり、それぞれwiの価値を持っている。
これらから区間の重なりを生じないように区間を選んで、その価値の総和を最大化せよ。

制約
・1 ≦ n ≦ 100000
・1 ≦ si < ti ≦ 10^9
・1 ≦ wi ≦ 10^9

Examples
0) 
 n = 5
 s = {1, 2, 4, 6, 8}
 t = {3, 5, 7, 9, 10}
 w = {3, 10, 6, 20, 8}

 Returns : 30 (区間2, 4)

この問題は例えば

dp[i+1] := i番目までの区間についての価値の総和の最大値

としてDP遷移式を作ることができます。計算時間はO(n^2)になります。


類題

幾つか個人的に印象に残った問題を挙げたいと思います。

「前から順番に見ていくDP」の部分がメインとなっている問題を幾つか並べました。このタイプで問題を難しくしようと思うと、予め何らかの基準によってn個のモノをソートさせたり、DP遷移自体に別のDPが必要だったり、といったパターンが多く見られました。


2. 連立1次方程式

最近、連立1次方程式を想定解法とする問題がとても多いですね。連立1次方程式で解ける問題についてpepsin-amylaseさんの記事がとても詳しいです。ここでは、特に、ライツアウト系の問題を挙げます。この問題が連立1次方程式で解ける鍵は、「制約条件が1次方程式の形で書けること」にあると言えます。なお、解法の細かい部分はpepsin-amylaseさんの記事を参照して下さい。


ライツアウト問題

今回はAOJ1308 Awkward Lightsを紹介します。

概要
m×nのライツアウトの初期盤面が与えられる。
あるマスを押すと、「押したマス、及び、そのマスからマンハッタン距離がdであるマス」
の状態が反転する。
ライツアウトの初期盤面が与えられて、全てOFFにすることができるかどうか判定せよ。

制約
・1 ≦ m, n ≦ 25
・1 ≦ d ≦ m + n

Examples
0) 
 n = m = 5, d = 1
 1 1 1 0 1
 0 1 0 1 0
 1 0 1 0 1
 0 1 0 1 0
 1 0 1 0 1

 Returns : 0(FALSE)

1)
 n = m = 5, d = 2
 0 0 0 0 0
 0 0 0 0 0
 0 0 1 0 0
 0 0 0 0 0
 0 0 0 0 0

 Returns : 1(TRUE)

この問題に限らずライツアウト系の問題は

・各マスに変数xiを割り当て、「押す」= 1、「押さない」= 0 とする
・制約条件は、xiについてのmod.2の連立1次方程式の形で書ける
・その方程式を掃き出し法を用いて解く

という解法で解けることが多いです。


類題

連立1次方程式で解く類題です。必ずしも「0 or 1」の形ではないですが、考え方が良く似た問題たちです。

3. 最小カット

次に最小カットです。最近、診断人さんが放送されたテーマです。O(2^n)な問題を最小カットに帰着できる問題は、制約条件がとても特殊な形をしています。

  min  f(x1) + f(x2) + … + f(xn)
  s.t.  xi = 0 or 1
     様々な制約条件

において、制約条件が全て

   xi ≦ xj(言い換えると、xi = 1 ⇒ xj = 1)

の形をしていれば最小カットによって解くことができます。

詳しく書いて行くと大変長くなってしまうため、具体的にどのように最小カットに帰着させるかは

CKomakiさんの記事
診断人さんの放送スライド

を参照して頂ければと思います。


コメント

上では、制約条件を「xi ≦ xj」と書きました。この制約式であれば、構成したグラフの枝に負の容量があっても各枝に一律に値を足してあげればよいです。

一方、もう少し制約の形を一般化して、

   xi = 1 であるにも関わらず xj = 0 となる場合には、値pのペナルティを与える

としても最小カットで解ける場合があります(xi ≦ xjの制約は、ペナルティ値pをINFにしたものと見ることができます)。この場合は、枝に負の容量がある場合の対処方法は職人技になります。


類題

診断人さんの生放送で紹介された問題と多数被っていますが、幾つか類題を挙げたいと思います。

4. 最大独立集合問題

グラフの最大独立集合問題もナイーブにやるとO(2^n)になる問題とみなせます。
一般にはNP-hardですが、特殊なグラフであれば多項式時間で解ける場合が多々あります。
この機会にそれらをまとめて整理してみたいと思います。

なお、最大独立集合問題が解けるグラフのクラスとして、パーフェクトグラフと呼ばれるクラスが知られています。
2分グラフ、区間グラフなどはパーフェクトグラフに含まれています。


フローに帰着するパターン

フロー絡みで出題されるパターンは、

  • 2分グラフ上の最大独立集合問題 -> 「頂点数 - 最大マッチング」が答え
  • 推移率を満たすDAG上の最大独立集合問題 -> Dilworthの定理により「DAG最小パス被覆」に等しい

が代表的です。
出題例として以下の問題があります。

その他

他にも、暗黙に最大独立集合問題とみなせる問題も多数出題されています。

  • 区間グラフ上の最大独立集合問題(つまり、区間スケジューリング問題)
  • 推移閉包を取った有向ツリー上の最大独立集合問題

5. Greedy系

Greedy系はむしろO(n!)から落とす問題が多い印象ですが、O(2^n)から落とす問題も色々あります。


区間スケジューリング問題

上に重み付き区間スケジューリング問題を挙げましたが、重みが無ければもっと効率よくGreedyに解くことができます。

n個の区間[si, ti](i = 1, 2, …, n)がある。
これらから区間の重なりを生じないように最大個数の区間を選べ。

制約
・1 ≦ n ≦ 100000
・1 ≦ si < ti ≦ 10^9

Examples
0) 
 n = 5
 s = {1, 2, 4, 6, 8}
 t = {3, 5, 7, 9, 10}

 Returns : 3 (区間1, 3, 5)
マトロイド

 そして、O(2^n)から計算量を落とすGreedy系問題と言えば、やはりマトロイドが大きな枠組みを与えています。詳しくは、去年の記事を参照して頂ければと思います。


その他

 SRM328 DIV1 Medium BlockEnemy辺りが結構面白いと感じたので紹介してみます。ツリー上でmultiway cutを求める問題です。

n頂点から成るツリー(無向グラフ、各枝は重み付き)と、頂点集合の部分集合Sが与えられる。
今、ツリーから幾つかの枝を取り除くことによって、
Sのどの2頂点を選んでもそれらが分断されている状態にしたい。
このような枝の取り除き方のうち、取り除いた枝の重みの総和が最小となるものを求めよ。

制約
・2 ≦ n ≦ 50

Examples
0) 
 n = 5
 tree = {"1 0 1", "1 2 2", "0 3 3", "4 0 4"}(枝(1, 0)の重みが1、枝(1, 2)の重みが2、…)
 S = {2, 3, 4}

 Returns : 4 (枝(1, 0)と枝(0, 3)を取り除く)

Sをより細かく分断できるような枝のうち、最小重みの枝をカットすることを繰り返すGreedyで解くことができます。


6. その他

最短路問題、最小カット問題

最短路問題や最小カット問題も、条件を満たす枝集合を求める問題なので、ナイーブにやるとO(2^|E|)になる問題と言えます。

マトロイド交差問題

共通の台集合を持つ2つのマトロイドがあったとき、両方のマトロイドで独立な最大サイズの集合を求める問題です。2分グラフの最大マッチング問題、有向全域木問題、カラフル全域木問題、全域木をパッキングする問題などがマトロイド交差問題の枠組みに入ります。

種々の指数時間アルゴリズム

本記事では、主に多項式時間や擬多項式時間に落とせる問題を扱いましたが、指数の底を小さくする問題も色々あります。wataさんのスライドがとても面白いです。


7. おわりに

ここまで読んで頂いてありがとうございます。僕は「多項式時間で効率良く解ける問題たちがどのような絡繰りで効率的に解けるのか?」を考えるのが好きで、このような記事を書くことにしました。とても雑多な内容になってしまいましたが、少しでも楽しんで頂けたら嬉しいです。それでは、皆様よいお年を!

2013年の虫食算の宣伝

 たまには競プロ以外のことも。
 僕は、虫食算作りが大好きです♪そんなわけで、毎年新年になる度に、その年をモチーフにした虫食算を作っています。今までに作って来た虫食算を少しだけ書きたいと思います。


7個の7による7


1234567890



2011年





2012年



2011年、2012年はかなり壮大な作品にしてしまったので、2013年はかなりコンパクトにしました。新年開けに公開します。それでは皆様、よいお年を!

Kruskal法をココロから納得する

 僕は、最小全域木を求めるKruskal法をココロから納得するのにとても長い時間が掛かってしまいました。本記事では、備忘録的な目的を兼ねて、少しKruskal法について書いてみたいと思います。

 僕は、Kruskal法は今年5月頃初めて知ったのですが、そのときはどうしてコレで最小全域木が求まるのか、不思議でなりませんでした。その後6月頃にアルゴリズムイントロダクションを読んで、ひとまず証明は理解したのですが、イマイチなかなかイメージが掴めませんでした。さらに7月にはマトロイドの触りを勉強し、マトロイドのGreedyアルゴリズムからKruskal法が自然に導かれることを学んだのですが、それでもまだKruskal法をココロから納得するには至れませんでした。
 それくらい、Kruskal法を納得するのにとても苦労しました。ようやく自分なりにKruskal法が納得できるようになったのは、マトロイドの交換公理についての学びを経て、最小全域木問題の最適性条件をハッキリと意識するようになってからでした。

 思うに、最小全域木問題に限らず、最適化問題を考えるときには、「最適性条件を意識すること」が大事ではないかと思います。一番身近なところでは、上に凸な関数f(x)の最大値を求めるときの最適性条件は、f^'(x) = 0で与えられます。他にもとても多くのGreedyな問題は、最適性条件を意識することによって自然に思い付けるのではないかと考えています。最小全域木問題についても、最適性条件をしっかり意識することによってやっとKruskal法が自然なものに思えるようになりました。
 なお、最小全域木を求める様々なアルゴリズムが、fura_2さんの最小全域木の特集にて、紹介されています。


全域木の構造

 まずは、そもそも全域木の持っている構造について考えます。まずは全域木の基本的な構造です。
 グラフGの全域木Tがあったとき、Tに含まれない辺eを選ぶと、T + {e}は閉路を1つ含みます。コレをTとeに関する基本閉路と呼び、C(T,e)と書きます。



 また、Tに含まれる辺fを選ぶと、T - {f}は2つの全域木に分かれます(下図の黄色頂点と橙頂点)。このとき、グラフG全体のカットが1つ定まります。コレをTとfに関する基本カットと呼び、C*(T,f)と書きます。



 そして、この基本閉路と基本カットを用いると、以下のようなキレイな構造が見えて来ます。

 無向グラフGが与えられる。T, SをGの2つの全域木とする。
 このとき、任意の e \in T-Sに対し、ある f \in S-Tが存在して、
 T - {e} \cup {f}と、S \cup {e} - {f}とが共に全域木となる。

 コレは次のようなことです。最初は、SとTはともに全域木です。このとき、Sは自分が持っていながTが持っている辺eを欲しがったとします。このとき、逆にSは持っているけどTは持っていない辺fが上手い具合にあって、SとTとでeとfとを交換することができます。交換しても、新Sと新Tはともに全域木となります。



                                                                                                                                              • -



 証明は基本閉路と基本カットの構造をイシキすれば簡単です。

  1. T君はSにeをねだられたので、まずTにとってのeによる基本カットC*(T,e)を考えます。
  2. 反対にSはeが加わることで生じる基本閉路C(S,e)を考えます。
  3. これらは2つ以上の交辺を持ちますが、そのうちe以外の交辺をfとします。
  4. SとTとで、eとfを交換することで、上手いこと必ずSとTは新しい全域木になります。
最小全域木問題の最適性条件

 さて、最小全域木問題の最適性条件について考えます。
 ここまでに見た全域木の交換の構造を考えると、以下のとても嬉しい性質を示すことができます。この性質を見ると、もはやKruskal法は自然です。何故なら、Kruskal法による出力結果は、アルゴリズムの性質上必ず2の条件を満たすからです。

 無向連結グラフGが与えられ、各辺eの重みをw(e)とする。またSをGの全域木とする。このとき、以下は同値である。

  1. TはGの最小全域木である
  2. Tに含まれない任意の辺eについて、基本閉路C(T,e)の任意の辺をfとすると、w(e) >= w(f)

(証明)
 1→2は自明です。何故なら、Tに含まれないある辺eについて、あるf \in C(T,e)が存在してw(e) < w(f)であると仮定すると、Tはfを捨ててeを取り入れることによって、より重みの小さな全域木となって矛盾するからです。
 2→1は以下のようにします。
 まず、「Tに含まれない任意の辺eについて、基本閉路C(T,e)の任意の辺をfとすると、w(e) >= w(f)」を満たす全域木Tを取り、さらに任意の全域木をSとします。このとき、w(T) <= w(S)となることを|S-T|についての帰納法によって示します。まず、|S-T| = 0については、そもそもS = Tとなるので明らかです。
 |S-T| <= n-1については正しいと仮定して、|S-T| = nについても正しいことを示します。
 Sに含まれるがTには含まれない任意の辺eについて、基本閉路C(T,e)と基本カットC*(S,e)を考え、これらのe以外の交辺をfとする。このとき、C(T,e)についての条件より、w(e) >= w(f)が成立する。よって、SとTとでeとfを交換することにより、Sは新しくS^'になるとすると、w(S^') = w(S) - w(e) + w(f) <= w(S)となる。一方、|S^'-T| = n-1となるので、帰納法の仮定より、w(T) <= w(S^')となるので、結局、w(T) <= w(S)が導かれます。//
 

結び

 僕はKruskal法を知ってから長い間、どうしてこんな上手いこと行ってしまうのか不思議な気持ちが残り続けていました。最小全域木問題の最適性条件をハッキリと意識することによってようやく納得することができたので、そのことについて書いてみました。ここまで読んで頂いた方には感謝の気持ちで一杯です。