naoya_t@hatenablog

いわゆるチラシノウラであります

SRM692 DIV1

参加してないけど

3年前に書いたこんな記事
naoyat.hatenablog.jp
のせいでagwたんから2-SAT教えてって無茶振りされて、とりあえずPractice Roomで問題を見てみました

Easy: HardProof (250points)

N個の言明(statement)から成る集合があって、
その中の言明xと言明yについて、含意(implication) x=>y を証明するのにコストが D[x*N+y] かかる。
この集合の各言明が、直接ないし間接的に互いを含意するように必要な証明を行いたい。
ただし、本問で求めたいのは証明の最小コストではなく、最も難しい言明と最も易しい言明の証明コストの差が最小になるケースにおける、そのコスト差の最小値。

これって別に2-SATってわけじゃなくて、有向グラフで、全ノードが繋がってて、どのノードから辿ってもそのノード自身に戻って来られれば良いんだよね。

そういうグラフになるために必要なエッジの繋ぎ方を全パターン調べるべき?(この時点で頭の中にあったのは最小全域木的なやつ)
最初に1つノードを決めて、1つずつ追加してコストを再計算する?
DP的に出来ない?
それは計算量的に無理じゃない?

一晩放置して翌朝、

あ、許容するコストの上限と下限が決まってれば、その範囲のエッジだけ繋いで、そのグラフが条件を満たしてるか調べればいいのでは?上限と下限は二重ループで回すとして。

条件を満たしてるか調べるってどうやって?

ここで、ああ、これって強連結じゃん、と気づいて(前に書いた強連結コードをコピペ)、
とりあえずテストサンプル全部通るしsubmitしてみる

→WA
あああ
N=1のとき死ぬ

D.size() == 1 のときに0を返しちゃえ

→TLE
あああ
N=50なケースで落ちてる
落ちたそのテストケースをローカルで試したら80秒ぐらいかかってるし

上限と下限の二重ループ、下限はループでいいとして、上限を二分探索にしたらどう?
ローカルで1秒切った
いけるぞ

→AC
この問題、みんなすんなり解けてるの?

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())

class HardProof {
	vector<vector<int> > d;
	vector<int> nums;
	int N2, N, nn;

	vector<vector<int> > arc;
	vector<vector<int> > arc_r;
	vector<int> cmp; // 属する強連結成分の、グラフ全体におけるトポロジカル順序

	vector<bool> visited;
	vector<int> vs; // post-order
	void dfs(int v) {
	  	visited[v] = true;
	  	tr(it, arc[v]) {
	    	if (!visited[*it]) dfs(*it);
	  	}
	  	vs.push_back(v); // 帰りがけにvを記録。グラフの末端に近いものから並ぶ
	}
	void rdfs(int v, int k) {
	  	visited[v] = true;
	  	cmp[v] = k;
	  	tr(it, arc_r[v]) {
	    	if (!visited[*it]) rdfs(*it, k);
	  	}
	}
	int scc() { // 強連結成分分解
		vs.clear();
  	  	visited.assign(N, false);
  	  	rep(i, N) {
    		if (!visited[i]) dfs(i);
  	  	}

  	  	visited.assign(N, false);
  	  	int k=0;
  	  	reverse(all(vs)); // グラフの末端から遠いものから始めたい
  	  	tr(it, vs) {
    		if (!visited[*it]) rdfs(*it, k++);
  	  	}
  	  	return k;
	}

	bool check(int lo, int hi) {
		arc.assign(N, vector<int>());
		arc_r.assign(N, vector<int>());
		cmp.assign(N, -1); // 追加

		rep(i, N) rep(j, N) {
			if (i == j) continue;
			if (lo <= d[i][j] && d[i][j] <= hi) {
				// add_edge(i, j);
				arc[i].push_back(j);
				arc_r[j].push_back(i);
			}
		}

		scc(); // 強連結成分分解

		map<int, int> st;
		tr(it, cmp) {
			st[*it]++;
		}
		tr(it, st) {
			if (it->second == cmp.size()) {
				return true;
			}
		}
		return false;
	}
	public:
	int minimumCost(vector<int> D) {
		N2 = D.size();
		if (N2 == 1) return 0;
		N = (int)sqrt(N2); // 1-50
		// Di = [0..150000]
		d.assign(N, vector<int>(N));
		rep(x,N) rep(y,N) {
			d[x][y] = D[x*N+y]; // cost to prove x => y
		}

		set<int> nums_;
		rep(x,N) rep(y,N) { if (x != y) nums_.insert(d[x][y]); }

		nums.assign(all(nums_));
		nn = nums.size();

		int ans = nums[nn-1] - nums[0];
		for (int i=0; i<nn; ++i) {
			if (check(nums[i], nums[i])) return 0;
			if (!check(nums[i], nums[nn-1])) continue;
			int lo = i, hi = nn-1;
			while (lo+2 <= hi) {
				// assert(check(nums[i], nums[lo]) == false)
				// assert(check(nums[i], nums[hi]) == true)
				int m = (lo + hi)/2;
				if (check(nums[i], nums[m])) {
					hi = m;
				} else {
					lo = m;
				}
			}
			ans = min(ans, nums[hi]-nums[i]);
		}

		return ans;
	}
};