3-1 lower_bound
長さnの単調非減少な数列a0,,,an-1と数kが与えられます。ai>=kとなるような最小のiを求めなさい存在しない場合はnを出力しなさい
int main() {
int n, k;
int a[1000100];
cin >> n >> k;
for (int i = 0; i < n; ++i)cin >> a[i];
//解の存在範囲を初期化
int lb = -1, ub = n;
//解の存在範囲がiより大きい間繰り返す
while (ub - lb > 1) {
int mid = (lb + ub) / 2;
if (a[mid] >= k) {
ub = mid;
}
else {
lb = mid;
}
}
cout << ub << endl;
return 0;
}
これはSTLにlower_boundという関数として含まれています
sqrt関数
double mysqrt(double x) {
double l = 0, r = x;
for (int i = 0; i < 64; ++i) {
double m = (l + r) / 2.0;
if (m*m < x)l = m;
else r = m;
}
return l;
}
例題 joi本戦2008 B ピザ
int main() {
int d, n, m;
cin >> d >> n >> m;
vector<int>D, K;
ll res = 0;
D.push_back(0);
D.push_back(INF);
for (int i = 1; i < n; ++i) {
int x; cin >> x;
D.push_back(x);
}
for (int i = 0; i < m; ++i){
int x; cin >> x;
K.push_back(x);
}
sort(D.begin(), D.end());
sort(K.begin(), K.end());
for (int i = 0; i < m; ++i) {
int plus;
auto iter = lower_bound(D.begin(), D.end(), K[i]);
int key1 = iter - D.begin();
if (key1 == n) {
plus = min((d - K[i]), abs(K[i]-D[n-1]));
}
else {
plus = min(D[key1] - K[i], K[i] - D[key1 - 1]);
}
res += plus;
}
cout << res << endl;
return 0;
}
joi2008年 本戦c ダーツ
int main() {
int n, m; cin >> n >> m;
vector<int>p;
p.push_back(0);
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
p.push_back(a);
}
sort(p.begin(), p.end());
vector<int>v;
for (int i = 0; i < n + 1; ++i) {
for (int j = 0; j < n + 1; ++j) {
v.push_back(p[i] + p[j]);
}
}
v.push_back(0);
v.push_back(INF);
sort(v.begin(), v.end());
int res = 0;
for (int i = 0; i < v.size(); ++i) {
int x = m - v[i];
if (x < 0)continue;
auto iter = upper_bound(v.begin(), v.end(), x);
int key = iter - v.begin() - 1;
res = max(res, v[i] + v[key]);
}
cout << res << endl;
return 0;
}
abc 077 c snuke festival
int main() {
ll n; cin >> n;
vector<int>a(n), b(n), c(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
for (int i = 0; i < n; ++i) {
cin >> c[i];
}
a.push_back(INF);
c.push_back(INF);
sort(a.begin(), a.end());
sort(c.begin(), c.end());
ll res = 0;
for (int i = 0; i < n; ++i) {
auto iter1 = lower_bound(a.begin(), a.end(), b[i]);
auto iter2 = upper_bound(c.begin(), c.end(), b[i]);
ll key1 = iter1 - a.begin();
ll key2 = n - (iter2 - c.begin());
res += (key1 * key2);
}
cout << res << endl;
return 0;
}
ARC 037 億マス計算
そもそも小さいほうからk番目の値がxであるとはどういうことか？
→x-1以下の数字がk個未満かつx以下の数字がk個以上
→x以下の数字がk個以上ある最小のxを見つける
//答えをmidとすると積がmid以下の数がK個以上になる最小のmidが答えになるmid以下の
//数を数える方法はi行目の中で掛け算してmid以下の数はai*bj<=midつまりbj<=mid/aiとなる
//
int main() {
int n, k; cin >> n >> k;
vector<ll>a(n), b(n);
for (int i = 0; i < n; ++i)cin >> a[i];
for (int i = 0; i < n; ++i)cin >> b[i];
sort(b.begin(), b.end());
sort(a.begin(), a.end());
ll l = -1, r = a[n - 1] * b[n - 1];
while (r - l > 1) {
ll mid = (l + r) / 2;
ll cnt = 0;
for (int i = 0; i < n; ++i) {
//ai*bj<=mid bj<=mid/ai
auto it = upper_bound(b.begin(), b.end(), mid / a[i]);
//bの中で,k/ai以下である個数を足す
cnt += it - b.begin();
}
if (cnt < k) {
l = mid;
}
else {
r = mid;
}
}
cout << r << endl;
return 0;
}
二分探索例題 abc138 E
# include<iostream>
# include<vector>
# include<algorithm>
# include<string>
# include<map>
# include<math.h>
# include<queue>
# include<deque>
# include<stack>
# include<cstdio>
# include<utility>
# include<set>
# include<list>
# include<cmath>
# include<stdio.h>
# include<string.h>
# include<iomanip>
# include<cstdio>
# include<cstdlib>
# include<cstring>
using namespace std;
# define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
# define REP(i, n) FOR(i, 0, n - 1)
# define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
const ll inf = 1LL << 50;
int gcd(int x, int y) {
if (x < y)swap(x, y);
if (y == 0)return x;
return gcd(y, x%y);
}
void mul(ll a, ll b) {
a = a * b % INF;
}
///////////////////////////////////////
int main() {
string s, t;
cin >> s >> t;
vector<vector<int>>alpha;
alpha.resize(26);
for (int i = 0; i < s.size(); ++i) {
alpha[s[i] - 'a'].push_back(i);
}
ll ans = 0;
ll last = -1;
for (int i = 0; i < t.size(); ++i) {
if (alpha[t[i] - 'a'].size()<=0) {
cout << -1 << endl;
return 0;
}
auto itr = upper_bound(alpha[t[i] - 'a'].begin(), alpha[t[i] - 'a'].end(), last);
if (itr == alpha[t[i] - 'a'].end()) {
ans += s.size();
itr = alpha[t[i] - 'a'].begin();
}
last = *itr;
}
ans += last+1;
cout << ans << endl;
return 0;
}
cable master 解を仮定し可能か判定
長さがそれぞれLiであるようなN本の紐があります。これらの紐を切って同じ長さの紐をK本作るときの最長の長さを求めなさい。
条件C(x):=長さxの紐をK本切り出すことができる
とするとC(x)を満たすような最大のxを求める問題となる。区間の初期化は十分に大きな数INF(>MAXL)を用いて
lb=0 ub=INFとすればよい
長さLiの紐から切り出せる長さxの紐の最大数はfloor(Li/x)本であるので
C(x)=floor(Li/x)の総和がK以上となり判定することができる
int N, K;
double L[10010];
bool C(double x) {
int num = 0;
for (int i = 0; i < N; ++i) {
num += (int)(L[i] / x);
}
return num >= K;
}
int main() {
cin >> N >> K;
for (int i = 0; i < N; ++i)cin >> L[i];
double lb = 0, ub = INF;
for (int i = 0; i < 100; ++i) {
double mid = (lb + ub) / 2;
if (C(mid))lb = mid;
else ub = mid;
}
cout << fixed<<setprecision(3)<<floor(ub * 100) / 100 << endl;
return 0;
}
例題 abc 023D 射撃王
ll N;
ll h[100100], s[100100];
bool OK(ll x) {
vector<pair<ll, ll>>St;
for (ll i = 0; i < N; ++i) {
St.push_back(make_pair((x - h[i]) / s[i], i));
}
sort(St.begin(), St.end());
//xに到達するまで時間がかからない順に前から並べる
//早い奴から順に撃ち落としていく
for (ll i = 0; i < N; ++i) {
ll index = St[i].second;
if (h[index] + s[index] * i > x) {
return false;
}
}
return true;
}
int main() {
cin >> N;
for (int i = 0; i < N; ++i) {
cin >> h[i] >> s[i];
}
ll l = 0, r = 1e15;
while(r-l>1){
ll mid = (l + r) / 2;
if (OK(mid))r = mid;
else l = mid;
}
cout << r << endl;
return 0;
}
abc 062 d widespread
//整数Tに対しenough(T)をT回以内の爆発ですべての魔物を消すことは可能か？という問いの答え
//とする。求めたい答えはenough(T)=YesであるようなTの最小値です。enoughは単調性を持つため
//この最小値を二分探索で求めることができる
//定められたTの値に対してenough(T)を判定するには爆発を起こすことを以下のようにとらえなおす
//すべての魔物の体力をBずつ減らし魔物を一体選んでその体力をさらにA-B減らす
//するとT回の爆発を起こすことはすべての魔物の体力をB*T減らしその上でT回にわたって
//一体の魔物の体力をA-B減らすことと同等すべての魔物を消すには体力がB*Tより高い魔物
//iにそれぞれに対して追加ダメージを[(hi-B*T)/(A-B)]回与える必要がありこの回数の合計が
//T以下であればenough(T)=Yes,合計がTを超える場合はenough(T)=Noと判定できます
ll N, A, B;
ll h[100100];
bool ok(ll k) {
ll cnt = 0;
ll sa = A - B;
for (int i = 0; i < N; ++i) {
if (h[i] > B*k) {
cnt += (h[i] - B * k + (A - B) - 1)/ (A - B);
}
}
return (cnt <= k);
}
int main() {
cin >> N >> A >> B;
REP(i, N)cin >> h[i];
ll l = 0;
ll r = 1e9+10;
while (r - l > 1) {
int mid = (l + r) / 2;
if (ok(mid)) {
r = mid;
}
else {
l = mid;
}
}
cout << r << endl;
return 0;
}
ARC 050 B 花束
ll R, B;
ll x, y;
//k個の花束をつくることができるか？
//花束を作るためには赤い花と青い花が少なくとも1本ずつ必要なので
//とりあえず赤い花と青い花をk本ずつ減らす
//赤い花束を作るためにはさらに赤い花がx-1本必要なので赤い花束は（R-k)/(x-1)個作ることができる
//同様に青い花束は(B-k)/(y-1)個作ることができる
//よって（R-k)/(x-1)+(B-k)/(y-1)>=kか判定すればよい
//この条件を満たす最大のkを二分探索する
//基本的に二分探索する対象は求めたい値
bool OK(ll k) {
if (k > R)return false;
if (k > B)return false;
ll nr = R - k;
ll nb = B - k;
ll rc = nr / (x - 1);
ll bc = nb / (y - 1);
return rc + bc >= k;
}
int main() {
cin >> R >> B;
cin >> x >> y;
ll l = 0, r = 1e20;
while(r-l>1){
ll mid = (l + r) / 2;
if (OK(mid)) {
l = mid;
}
else {
r = mid;
}
}
cout << l << endl;
return 0;
}
abc 026 D 高橋君ボール1号
中間値の定理を基にした二分探索の考え方
double A, B, C;
//tがf(t)=100となりうるか
double ok(double t) {
return A * t + B * sin(C*t*M_PI);
}
int main() {
cin >> A >> B >> C;
double l = 0, r = 10000;
for (int i = 0; i < 10000; ++i) {
double mid = (l + r) / 2.0;
if (ok(mid) < 100) {
l = mid;
}
else {
r = mid;
}
}
cout << fixed<<setprecision(10)<< r << endl;
return 0;
}
式変形して二分探索に持ち込むのは典型。past Mなどもこの例
aoj 2220 the number of real roots of a cubic equation
ax^3+bx^2+c*x+d=0が与えられるのでその正の実数根の個数、負の実数根の個数をそれぞれ調べよ
入力は複数のテストケースからなり，1行目にはその個数が記される．
2行目以降はa b c dの形式で3次方程式の係数が記される．aは0ではなく，またそれぞれの数は-100から100までの整数値である．
方針１ カルダノの公式というのがある
ax^3+bx^2+cx+d=0の両辺をaで割ると
x^3+b/ax+c/ax+d/aとなるこれはx^3+Ax^2+Bx+C=0と表せる。X=x+A/3を新たな変数として
(平行移動を行うことで)X^3+pX+q=0と書き直せる
X=u+vとすると、(u+v)^3+p*(u+v)+q=0となり変形するとu^3+v^3+q+(3uv+p)(u+v)=0よって
u^3+v^3+q=0,3uv=-pである。...(※)
この式からvを消すとu^6+qu^3-p^3/27=0となる。
よってu^3=(-q+√q^2+4p^3/27)/2,(-q-√q^2+4*p^3/27)/2
これを利用する。以下、引用
# include <cstdio>
# include <cstdlib>
# include <cmath>
# include <iostream>
using namespace std;
const double PI = 2 * asin(1.0);
double cuberoot(double x){
double s , prev;
int positive;
if(x == 0) return 0;
if(x>0)positive = 1; else {positive = 0 ; x = -x;}
if(x>1) s = x ; else s = 1;
do{
prev = s ; s = (x/(s*s)+2*s)/3;
}while(s < prev);
if(positive) return prev; else return -prev;
}
int M , P;
void check(double s){
if(abs(s) < 1e-10) return ;
if(s > 0) P++;
else M++;
}
void cardano(double a, double b , double c , double d){
double p , q , t , a3 , b3 , x1 , x2 , x3;
b/=(3*a);
c/=a;
d/=a;
p = b * b - c / 3;
q = (b * (c-2*b*b)-d)/2;
a = q * q - p * p * p;
if(a == 0){
q = cuberoot(q); x1 = 2 * q - b ; x2 = -q - b;
//printf("x = %g, %g(重解)\n",x1,x2);
check(x1);
check(x2);
check(x2);
}else if( a > 0){
if(q>0) a3 = cuberoot(q+sqrt(a));
else a3 = cuberoot(q-sqrt(a));
b3 = p / a3;
x1 = a3 + b3 - b;
x2 = - 0.5 * (a3 + b3) - b;
x3 = fabs(a3-b3) * sqrt(3.0) / 2;
//printf("x = %g; %g +- %g i\n",x1,x2,x3);
check(x1);
}else{
a = sqrt(p) ; t = acos( q / (p * a) ); a *= 2;
x1 = a * cos(t/3)-b;
x2 = a * cos((t+2*PI)/3)-b;
x3 = a * cos((t+4*PI)/3)-b;
//printf("x = %g , %g , %g\n",x1,x2,x3);
check(x1);
check(x2);
check(x3);
}
}
int main(){
int n;
cin >> n;
for(int i = 0 ; i < n ; i++){
double a , b , c , d;
cin >> a >> b >> c >> d;
M = P = 0;
cardano(a,b,c,d);
cout << P << " " << M << endl;
}
}
解法2 二分探索で一つ解をみつけてからいろいろやる
ちょっとむずすぎるので後回し、、
aggressive cows 最小値の最大化
農夫ジョンはN個の牛舎を持つ小屋を作りました。各牛舎は直線上に並んでおりi番目の牛舎は位置Xiにあります。しかし彼のM頭の牛たちは小屋の位置が気に入らずとても攻撃的になってしまいました。ジョンは牛たちが互いに傷つけあうのを防ぐため他の牛とできるだけ離れるように牛舎に入れることにしました。最も近い2頭の牛の間の間隔を最大化しなさい。
C(d):=最も近い二頭の牛の間の間隔をd以上とすることができる
とするとC(d)を満たすような最大のdを求める問題となる。また、最も近い間隔がd以上というのは全ての間隔がd以上であると言い換えることができるので
C(d)=(任意の牛の間隔をd以上とすることができる)となる。
この判定は次のように貪欲法を用いて簡単に行うことができます。
・牛舎の位置xをソートする
・最初の牛をx0に入れる
・i番目の牛をxjに入れたらi+1番目の牛はxj+d<=xkとなるような最小のxkに入れる
int n, m;
vector<int>x;
bool C(int d) {
int last = 0;
for (int i = 1; i < m; ++i) {
int crt = last + 1;
while (crt < n&&x[crt] - x[last] < d) {
crt++;
}
if (crt == n)return false;
last = crt;
}
return true;
}
int main() {
cin >> n >> m;
x.resize(n);
for (int i = 0; i < n; ++i) {
cin >> x[i];
}
sort(x.begin(), x.end());
int l = 0, r = INF;
while (r - l > 1) {
int mid = (l + r) / 2;
if (C(mid)) {
l = mid;
}
else {
r = mid;
}
}
cout << l << endl;//rではないことに注意
return 0;
}
例題joi2013本戦C バウムクーヘン
int main() {
ll n;
cin >> n;
vector<ll>a(n * 2);//環状の数列を扱う時は二週確保はよくやる
ll total = 0;//バームクーヘン全体のサイズ
for (int i = 0; i < n; ++i) {
cin >> a[i];
a[i + n] = a[i];
total += a[i];
}
ll low = 0, high = 1LL << 60;
while (high - low > 1) {
//3ピースともmid以上にできるかを判定する
ll mid = low + (high - low) / 2;
//尺取り法により各切れ目からmid以上になる最小区間がどこまでかを求める
vector<int>Next(n, -1);
vector<ll>Size(n, -1);
int right = 0;
ll sum = 0;
for (int left = 0; left < n; ++left) {
while (right < n * 2 && sum < mid) {
sum += a[right];
++right;
}
if (sum >= mid) {
Next[left] = right;
Size[left] = sum;
}
if (right == left)++right;
else sum -= a[left];
}
bool ok = false;
for (int i = 0; i < n; ++i) {
int ni = Next[i];
if (ni == -1)continue;
if (Size[i] >= total)continue;
ni %= n;
int nni = Next[ni];
if (nni == -1)continue;
if (total - Size[i] - Size[ni] >= mid)ok = true;
}
if (!ok)high = mid;
else low = mid;
}
cout << low << endl;
return 0;
}
尺取り+二分探索
JOI2016本戦C JOIOI王国
うーんむずいから後回しで、、
平均最大化
重さと価値がそれぞれwi,viであるようなn個の品物があります。この中からちょうどk個選んだ時の単位重さ当たりの価値の最大値を求めなさい
各品物を単位重さ当たりの価値でソートして大きいほうから貪欲に選ぶという方法が思いつくが、この方法だと小数点以下の扱い的にうまくいかないので二分探索を使う。
C(x):=単位重さ当たりの価値がx以上になるように選ぶことができる。
とするとC(x)を満たすような最大のxを求める問題となる。
C(x)の判定方法を考える。ある品物の集合Sを選んだとするとその時の単位重さあたりの価値はΣvi/Σwi(i∈S）であるのでΣvi/Σwi>=xとなるSが存在するか調べればよいということになる。この不等式を変形するとΣ(vi-xwi)>=0(i∈S)となり、これならば(vi-xwi)の値でソートして貪欲に選ぶことができます。従ってC(x)=((vi-x*wi)の大きいほうからk個の和が0以上)となりこれは判定可能
int n, k;
int w[10100], v[10100];
double y[10100];//v-x*w
bool C(double x) {
for (int i = 0; i < n; ++i) {
y[i] = v[i] - x * w[i];
}
sort(y, y + n);
double sum = 0;
for (int i = 0; i < k; ++i) {
sum += y[n - i - 1];
}
return sum >= 0;
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; ++i)cin >> w[i] >> v[i];
double l = 0, r = INF;
for (int i = 0; i < 100; ++i) {
double mid = (l + r) / 2;
if (C(mid))l = mid;
else r = mid;
}
cout << r << endl;
return 0;
}
例題 ABC 034 D 食塩水
int n, k;
ll w[10100], p[10100];
long double y[10100];//v-x*w
bool C(double x) {//濃度xは作れるか？
for (int i = 0; i < n; ++i) {
y[i] = p[i] * w[i] - x * w[i];
}
sort(y, y + n);
double sum = 0;
for (int i = 0; i < k; ++i) {
sum += y[n - i - 1];
}
return sum >= 0;
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; ++i)cin >> w[i] >> p[i];
double l = 0, r = INF;
for (int i = 0; i < 100; ++i) {
double mid = (l + r) / 2;
if (C(mid))l = mid;
else r = mid;
}
cout << fixed<<setprecision(10)<< l << endl;
return 0;
}
他にもあるけど後回しで。
しゃくとり法
でた。
長さnの数列a0,,,an-1と整数Sが与えられます。連続する部分列でその総和がS以上となるもののうち最小の長さを求めなさい。解が存在しない場合は0を出力せよ
区間[s,t)の総和は
sum(i)=a0+a1+,,,+ai-1とすると
as+as+1+,,,,+at-1=sum(t)-sum(s)となる。
int main() {
int n, s;
int a[100100];
cin >> n >> s;
vector<int>sum(n + 1);
for (int i = 0; i < n; ++i)cin >> a[i];
sum[0] = 0;
for (int i = 0; i < n; ++i) {
sum[i + 1] = sum[i] + a[i];
}
if (sum[n] < s) {
cout << 0 << endl;
return 0;
}
int res = n;
for (int i = 0; sum[i] + s <= sum[n]; ++i) {
int t = lower_bound(sum.begin() + i, sum.end(), sum[i]+s) - sum.begin();
res = min(res, t - i);
}
cout << res << endl;
return 0;
}
二分探索で書くとこうなる
int main() {
int n, s;
int a[100100];
cin >> n >> s;
for (int i = 0; i < n; ++i)cin >> a[i];
int res = n + 1;
int right = 0, sum = 0;
for (int left = 0; left < n; ++left) {
while (right < n&&sum < s) {
sum += a[right];
++right;
}
if (sum < s)break;
res = min(res, right - left);
if (right == left)++right;
sum -= a[left];
}
if (res > n) {
res = 0;
}
cout << res << endl;
return 0;
}
尺取り法だとこう。
jessica`s leading problem
pページからなりiページ目にはちょうど1つの事柄aiについて書かれている。本の中には同じ事柄が何度も書かれているので彼女はこの本の中の連続するページですべての事柄をカバーしているような部分を読むことに決めました。読まなければいけない最小のページ数を答えよ
区間[s,t]における各事柄の出現数を二分探索木などを用いてカウントしておく。
int main() {
int p; cin >> p;
int a[1000100];
for (int i = 0; i < p; ++i)cin >> a[i];
set<int>all;
for (int i = 0; i < p; ++i) {
all.insert(a[i]);
}
int n = all.size();
int right = 0, num = 0;
map<int, int>count;
int res = p;
for (int left = 0; left < p; ++left) {
while (right < p&&num < n) {
if (count[a[right]] == 0) {
num++;
}
count[a[right]]++;
right++;
}
if (num < n)break;
res = min(res, right - left);
if (right == left)++right;
count[a[left]]--;
if (count[a[left]] == 0) {
num--;
}
}
cout << res << endl;
return 0;
}
例題 ARC 022 B 細長いお菓子
int main() {
int p; cin >> p;
int a[1000100];
for (int i = 0; i < p; ++i)cin >> a[i];
set<int>all;
for (int i = 0; i < p; ++i) {
all.insert(a[i]);
}
int n = all.size();
int right = 0;
map<int, int>count;
int res = 0;
for (int left = 0; left < p; ++left) {
while (right < p) {
if (count[a[right]] != 0) {
break;
}
count[a[right]]++;
right++;
}
res = max(res, right - left);
if (right == left)++right;
count[a[left]]--;
}
cout << res << endl;
return 0;
}
ABC017 D サプリメント
後回し。
face the right way
int N;
int dir[5010];//牛の方向(0:F,1:B)
int f[5010];//区間[i,i+K-1]を反転させたかどうか
//機械の使用回数を計算する
int calc(int k) {
memset(f, 0, sizeof(f));
int res = 0;
int sum = 0;//たとえばi番目の牛がどっち向いているか知りたいなら何個のi番目を含んでいる長さkの区間があるか調べればよい
//ので配列fの区間[i-K+1,i]を足し算する
//全牛について調べる
for (int i = 0; i + k <= N; ++i) {
//区間[i,i+k-1]に着目
if ((dir[i] + sum) % 2 != 0) {
res++;
f[i] = 1;
}
sum += f[i];
if (i - k + 1 >= 0) {
sum -= f[i - k + 1];
}
}
for (int i = N - k + 1; i < N; ++i) {
if ((dir[i] + sum) % 2 != 0) {
return -1;
}
if (i - k + 1 >= 0) {
sum -= f[i - k + 1];
}
}
return res;
}
int main() {
cin >> N;
for (int i = 0; i < N; ++i) {
char x; cin >> x;
if (x == 'B')dir[i] = 1;
else dir[i] = 0;
}
int K = 1;
int M = N;
for(int k = 1; k <= N; ++k) {
int m = calc(k);
if (m >= 0 && M > m) {
M = m;
K = k;
}
}
cout << K << " " << M << endl;
return 0;
}
2 回やったら元に戻る (逆元が自分自身)
操作の順序を入れ替えても結果は変わらない、がミソ
fliptile
M*Nのマス目がある。一つのマスをひっくり返すとその縦横に隣接するマスまでひっくり返す。最小手数で全てのマスを白色にしたい。その回数を出力せよ。（0が白1が黒)
まず一番上の行のひっくり返し方を決めてしまう。すると繰り返しにより全てのマスのひっくり返り方が決まっていく。最終的に残った(M,1)~(M,N)のマスが全部白色にならなかったらそのような手順は存在しなかったということになる。
const int DX[5] = { -1,0,0,0,1 };
const int DY[5] = { 0,-1,0,1,0 };
int M, N;
int tile[20][20];
int opt[20][20];//最適解保存用
int flip[20][20];//作業用
//x,yの色を調べる
int get(int x, int y) {
int c = tile[x][y];
for (int d = 0; d < 5; ++d) {
int x2 = x + DX[d];
int y2 = y + DY[d];
if (0 <= x2 && x2 < M && 0 <= y2 && y2 < N) {
c += flip[x2][y2];
}
}
return c % 2;
}
//1行目を決めた場合の最小操作回数を求める。
//解が存在しないならば-1
int calc() {
for (int i = 1; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (get(i - 1, j) != 0) {
//(i-1,j)が黒色ならこのマスをひっくり返すしかない
flip[i][j] = 1;
}
}
}
//最後の行が全部白かチェック
for (int j = 0; j < N; ++j) {
if (get(M - 1, j) != 0) {
//解なし
return -1;
}
}
//反転回数をカウント
int res = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
res += flip[i][j];
}
}
return res;
}
int main() {
cin >> M >> N;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
cin >>tile[i][j];
}
}
int res = -1;
//1行目を辞書順で全通り試す。
for (int i = 0; i < 1 << N; ++i) {
memset(flip, 0, sizeof(flip));
for (int j = 0; j < N; ++j) {
flip[0][N - i - j] = i >> j & 1;
}
int num = calc();
if (num >= 0 && (res<0 || res>num)) {
res = num;
memcpy(opt, flip, sizeof(flip));
}
}
if (res < 0) {
cout << "IMPOSSIBLE" << endl;
}
else {
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (j == N - 1) {
cout << opt[i][j] << endl;
}
else {
cout << opt[i][j] << " ";
}
}
}
}
return 0;
}
弾性衝突は後回しで
半分全列挙
要素数nのリストA,B,C,Dが与えられます。各リストから1つずつ取り出した時その和が0となるような組み合わせの個数を求めなさい。ただし１つのリストに同じ値が複数個含まれている場合それらは異なるものとして数える。
int n;
int a[4010], b[4010], c[4010], d[4010];
int CD[16000100];
int main() {
cin >> n;
for (int i = 0; i < n; ++i)cin >> a[i];
for (int i = 0; i < n; ++i)cin >> b[i];
for (int i = 0; i < n; ++i)cin >> c[i];
for (int i = 0; i < n; ++i)cin >> d[i];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
CD[i*n + j] = c[i] + d[j];
}
}
sort(CD, CD + n * n);
ll res = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int cd = -(a[i] + b[j]);
res += upper_bound(CD, CD + n * n, cd) - lower_bound(CD, CD + n * n, cd);
}
}
cout << res << endl;
return 0;
}
例題 AGC 026 C string coloring
int main() {
int N; cin >> N;
string S; cin >> S;
map<pair<string, string>, int>mp;
//前半部分の組み合わせを全列挙
for (int mask = 0; mask < (1 << N); ++mask) {
string R = "", B = "";
for (int i = 0; i < N; ++i) {
if (mask&(1 << i)) {
R.push_back(S[i]);
}
else {
B.push_back(S[i]);
}
}
mp[{R, B}]++;
}
//後半部分の組み合わせを全列挙
ll ans = 0;
for (int mask = 0; mask < (1 << N); ++mask) {
string R = "", B = "";
for (int i = 0; i < N; ++i) {
if (mask&(1 << i)) {
R.push_back(S[N + i]);
}
else {
B.push_back(S[N + i]);
}
}
reverse(R.begin(), R.end());
reverse(B.begin(), B.end());
ans += mp[{B, R}];
}
cout << ans << endl;
return 0;
}
巨大ナップサック
重さと価値がそれぞれwi,viであるようなn個の品物があります。これらの品物を重さの総和がWを超えないように選んだ時の価値の総和の最大値を求めよ。
半分に分けて考える。半分に分けた片方から重さと価値の和がそれぞれw1,v1であるような選び方が得られたとする。このときもう片方からは重さがw2<=W-w1の条件の下でv2が最大となるように選べばよいということになる。
全列挙により得られた重さと価値の総和(w2,v2)のペアの集合からmax{v2|w2<=W}を効率的に計算するような方法を考えてみたい。明らかに、w2[i]<=w2[j]かつv2[i]>=v2[j]であるようなjは取り除いてよいことがわかる。w2,v2で辞書順ソートすることで取り除ける。すると、残ったものはw2[i]v2[i]<v2[j]となるためmax{v2|w2<=W}の計算はw2[i]<=Wとなるような最大のiを求めることで行うことができる。
const ll INF=1e18
const int MAX_N = 41;
ll n;
ll w[MAX_N], v[MAX_N];
ll W;
int main() {
cin >> n;
for (int i = 0; i < n; ++i)cin >> w[i];
for (int i = 0; i < n; ++i)cin >> v[i];
pair<ll, ll>ps[1 << (MAX_N / 2)];
cin >> W;
//前半分を全列挙
int n2 = n / 2;
for (int i = 0; i < 1 << n2; ++i) {
ll sw = 0, sv = 0;
for (int j = 0; j < n2; ++j) {
if (i >> j & 1) {
sw += w[j];
sv += v[j];
}
}
ps[i]=make_pair(sw,sv);
}
//無駄な要素を取り除く
sort(ps, ps+(1<<n2));
int m = 1;
for (int i = 1; i < 1<<n2; ++i) {
if (ps[m-1].second < ps[i].second) {
ps[m++] = ps[i];
}
}
//後ろ半分を全列挙し解を求める
ll res = 0;
for (int i = 0; i < 1 << (n - n2); ++i) {
ll sw = 0, sv = 0;
for (int j = 0; j<n - n2; ++j) {
if (i >> j & 1) {
sw += w[n2 + j];
sv += v[n2 + j];
}
}
if (sw <= W) {
ll tv = (lower_bound(ps, ps+m, make_pair(W - sw, INF)) - 1)->second;
res = max(res, sv + tv);
}
}
cout << res << endl;
return 0;
}
make_pair(W-sw,INF)-1とするのはいい手法やな
abc 032 D ナップサック問題
int main() {
ll N, W; cin >> N >> W;
ll v[210];
ll w[210];
ll VB = 0;
ll WB = 0;
for (int i = 0; i < N; ++i) {
cin >> v[i] >> w[i];
VB = max(VB, v[i]);
WB = max(WB, w[i]);
}
if (N <= 30) {
int N2 = N / 2;
pair<ll, ll>key[1<<16];
for (int i = 0; i < (1 << N2); ++i) {
ll vsum = 0;
ll wsum = 0;
for (int j = 0; j < N2; ++j) {
if (i >> j & 1) {
vsum += v[j];
wsum += w[j];
}
}
key[i]=make_pair(wsum,vsum);
}
sort(key, key + (1<<N2));
int m = 1;
for (int i = 1; i < 1<<N2; ++i) {
if (key[m - 1].second < key[i].second) {
key[m] = key[i];
m++;
}
}
ll res = 0;
for (int i = 0; i < 1 << (N - N2); ++i) {
ll sw = 0, sv = 0;
for (int j = 0; j < N - N2; ++j) {
if (i >> j & 1) {
sw += w[N2 + j];
sv += v[N2 + j];
}
}
if (sw <= W) {
ll tv = (lower_bound(key, key+m, make_pair(W - sw, INF)) - 1)->second;
res = max(res, sv + tv);
}
}
cout << res << endl;
}
else if (WB <= 1000) {
ll dp[210][200100] = {};//dp[i][j]でi番目の荷物を運んだ時の重さの和がjとなるときの価値の最大値
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= W; ++j) {
if (j >= w[i]) {
dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
}
else {
dp[i + 1][j] = dp[i][j];
}
}
}
cout << dp[N][W] << endl;
}
else {
ll dp[210][200100];//dp[i][j]でi番目までの荷物を選んだ時の価値の和がjの時の重さの最小値
for (int j = 1; j < 200100; ++j) {
dp[0][j] = INF;
}
dp[0][0] = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < 200100; ++j) {
if (j >= v[i]) {
dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
}
else {
dp[i + 1][j] = dp[i][j];
}
}
}
ll ans = 0;
for (int i = 0; i < 200100; ++i) {
if (dp[N][i] <= W) {
ans = i;
}
}
cout << ans << endl;
}
return 0;
}
ARC 017 C 無駄なものが嫌いな人
# include<iostream>
# include<vector>
# include<algorithm>
# include<string>
# include<map>
# define _USE_MATH_DEFINES
# include<math.h>
# include<queue>
# include<deque>
# include<stack>
# include<cstdio>
# include<utility>
# include<set>
# include<list>
# include<cmath>
# include<stdio.h>
# include<string.h>
# include<iomanip>
# include<cstdio>
# include<cstdlib>
# include<cstring>
using namespace std;
# define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
# define REP(i, n) FOR(i, 0, n - 1)
# define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
if (x < y)swap(x, y);
if (y == 0)return x;
return gcd(y, x%y);
}
void mul(ll a, ll b) {
a = a * b % INF;
}
double mysqrt(double x) {
double l = 0, r = x;
for (int i = 0; i < 64; ++i) {
double m = (l + r) / 2.0;
if (m*m < x)l = m;
else r = m;
}
return l;
}
///////////////////////////////////////
int main() {
int n, x;
cin >> n >> x;
int w[33];
for (int i = 0; i < n; ++i)cin >> w[i];
int N = n / 2;
vector<ll>key;
for (int i = 0; i < 1 << N; ++i) {
ll sum = 0;
for (int j = 0; j < N; ++j) {
if (i >> j & 1) {
sum += w[j];
}
}
if (sum <= x) {
key.push_back(sum);
}
}
vector<ll>key2;
for (int i = 0; i < 1 << (n - N); ++i) {
ll sum = 0;
for (int j = 0; j < n - N; ++j) {
if (i >> j & 1) {
sum += w[N+j];
}
}
if (sum <= x) {
key2.push_back(sum);
}
}
sort(key2.begin(), key2.end());
ll ans = 0;
for (int i = 0; i < key.size(); ++i) {
ll tv = x - key[i];
ans += upper_bound(key2.begin(), key2.end(), tv) - lower_bound(key2.begin(), key2.end(), tv);
}
cout << ans << endl;
return 0;
}
座標圧縮
w+hの格子上にn本の垂直または水平な幅1の直線が引かれています。格子は線によって何個の領域に分断されているでしょうか
座圧とは？→各値の大小関係や位置関係を崩さずに新しい数値を割り当てること
簡単なものから
abc 036 座圧
int main() {
int n; cin >> n;
int a[100100];
vector<int>v;
for (int i = 0; i < n; ++i) {
cin >> a[i];
v.push_back(a[i]);
}
sort(v.begin(), v.end());
map<int, int>mp;
int b = 0;
mp[v[0]] = 0;
for (int i = 1; i < n; ++i) {
if (v[i] == v[i - 1])continue;
else {
b++;
mp[v[i]] = b;
}
}
vector<int>ans;
for (int i = 0; i < n; ++i) {
ans.push_back(mp[a[i]]);
}
for (int i = 0; i < n; ++i) {
cout << ans[i] << endl;
}
return 0;
}
abc 113 c ID
int p[100100], y[100100];
vector<pii>v[100100];
int main() {
int n, m; cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> p[i] >> y[i];
v[p[i]].push_back({ y[i],i });
}
for (int i = 0; i < 100100; ++i) {
sort(v[i].begin(), v[i].end());
}
vector<int>ans(m);
for (int i = 0; i < 100100; ++i) {
if (v[i].empty())continue;
for (int j = 0; j < v[i].size(); ++j) {
ans[v[i][j].second] = j + 1;
}
}
for (int i = 0; i < m; ++i) {
cout << setw(6) << setfill('0') << p[i]<< setw(6) << setfill('0') << ans[i] << endl;
}
return 0;
}
↑は久しぶりに自分で解いてみたやつ↓ちゃんとした座標圧縮の解法
座標圧縮のやり方
まず数の候補をすべて列挙したvectorをつくる
vector<int>vals;
for(int i=0;i<n;++i)vals.push_back(a[i])
次にvalsをソートする
sort(vals.begin(),vals.end());
このままでは値が重複している可能性があるので重複を除く
vals.erase(unique(vals.begin(),vals.end()),vals.end());
これで準備完了。整列済みの配列に対して各値がどこにあるかを二分探索して求める
for(int i=0;i<N;++i){
int id=lower_bound(vals.begin(),vals.end(),a[i])-vals.begin();
}
int main() {
int n, m; cin >> n >> m;
vector<int>p(m), y(m);
for (int i = 0; i < m; ++i)cin >> p[i] >> y[i], --p[i];
//vals[v]:=p[i]=vであるようなiについてのy[i]の値を集めたもの
vector<vector<int>>vals(n);
for (int i = 0; i < m; ++i) {
vals[p[i]].push_back(y[i]);
}
for (int v = 0; v < n; ++v) {
sort(vals[v].begin(), vals[v].end());
vals[v].erase(unique(vals[v].begin(), vals[v].end()), vals[v].end());
}
for (int i = 0; i < m; ++i) {
int v = p[i];
cout << setw(6) << setfill('0') << v + 1;
int id = lower_bound(vals[v].begin(), vals[v].end(), y[i]) - vals[v].begin();
cout << setw(6) << setfill('0') << id + 1 << endl;
}
return 0;
}
確かにこっちのが楽だな
int w, h, n;
int x1[510], x2[510], Y1[510], y2[510];
bool fld[1510][1510];
int compress(int *x1, int *x2, int w) {
vector<int>xs;
for (int i = 0; i < n; ++i) {
for (int d = -1; d <= 1; ++d) {
int tx1 = x1[i] + d, tx2 = x2[i] + d;
if (1 <= tx1 && tx1 <= w)xs.push_back(tx1);
if (1 <= tx2 && tx2 <= w)xs.push_back(tx2);
}
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
for (int i = 0; i < n; ++i) {
x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();
x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();
}
return xs.size();
}
int main() {
cin >> w >> h >> n;
for (int i = 0; i < n; ++i)cin >> x1[i];
for (int i = 0; i < n; ++i)cin >> x2[i];
for (int i = 0; i < n; ++i)cin >> Y1[i];
for (int i = 0; i < n; ++i)cin >> y2[i];
int W = compress(x1, x2, w);
int H = compress(Y1, y2, h);
memset(fld, 0, sizeof(fld));
//線のある部分を塗りつぶし
for (int i = 0; i < n; ++i) {
for (int y = Y1[i]; y <= y2[i]; ++y) {
for (int x = x1[i]; x <= x2[i]; ++x) {
fld[y][x] = true;
}
}
}
int ans = 0;
for (int y = 0; y < H; ++y) {
for (int x = 0; x < W; ++x) {
if (fld[y][x])continue;
ans++;
queue<pii>que;
que.push(make_pair(x, y));
while (!que.empty()) {
int sx = que.front().first, sy = que.front().second;
que.pop();
for (int i = 0; i < 4; ++i) {
int tx = sx + dx[i], ty = sy + dy[i];
if (tx < 0 || W <= tx || ty < 0 || H <= ty)continue;
if (fld[ty][tx])continue;
que.push(make_pair(tx, ty));
fld[ty][tx] = true;
}
}
}
}
cout << ans << endl;
return 0;
}
二次元座標圧縮
例題 joi2007 E
int w, h, n;
int x1[1010], x2[1010], Y1[1010], y2[1010];
bool fld[3010][3010];
int compress(int *x1, int *x2, int w) {
vector<int>xs;
for (int i = 0; i < n; ++i) {
for (int d = -1; d <= 1; ++d) {
int tx1 = x1[i] + d, tx2 = x2[i] + d;
if (0 <= tx1 && tx1 < w)xs.push_back(tx1);
if (0 < tx2 && tx2 <= w)xs.push_back(tx2);
}
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
for (int i = 0; i < n; ++i) {
x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();
x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();
}
return xs.size();
}
int main() {
cin >> w >> h;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> x1[i] >> Y1[i] >> x2[i] >> y2[i];
}
int W = compress(x1, x2, w);
int H = compress(Y1, y2, h);
memset(fld, 0, sizeof(fld));
//線のある部分を塗りつぶし
for (int i = 0; i < n; ++i) {
for (int y = Y1[i]; y <= y2[i]; ++y) {
for (int x = x1[i]; x <= x2[i]; ++x) {
fld[y][x] = true;
}
}
}
int ans = 0;
for (int y = 0; y < H; ++y) {
for (int x = 0; x < W; ++x) {
if (fld[y][x])continue;
ans++;
queue<pii>que;
que.push(make_pair(x, y));
while (!que.empty()) {
int sx = que.front().first, sy = que.front().second;
que.pop();
for (int i = 0; i < 4; ++i) {
int tx = sx + dx[i], ty = sy + dy[i];
if (tx < 0 || W <= tx || ty < 0 || H <= ty)continue;
if (fld[ty][tx])continue;
que.push(make_pair(tx, ty));
fld[ty][tx] = true;
}
}
}
}
cout << ans << endl;
return 0;
}
ほぼ蟻本と同じようにやって14/20だった。どこが違うんやろ？
セグ木
Range Minimun Query(RMQ)を実現するセグ木を説明していく
.S,Tが与えられた時にas,,atの最小値を求める
.i,xが与えられた時にaiの値をxに変更する
次のように再帰的に求める
.与えられた区間とその節点の区間がまったく交差していなければ最小値に影響しない値を返す。（例えばINT_MAX)
.与えられた区間が完全にその節点の区間を含むような節点であればその節点の持つ値を返す。
.そうでなければ2つの子ノードについて再帰的に計算しその２つの値の最小値を返す。
//数列a0,,,an-1があるとき
//s,tが与えられた時as,,,atの最小値を求める
//i,xが与えれられたときaiの値をxに変更する
//セグ木を作る
# define MAX_INF 2147483647
//セグメント木を持つグローバル配列
int n;
vector<int>value;
//Nは葉の数datはノードの値を持つ配列
//k番目の値をaに変更
void update(int k, int a) {
//i番目の葉の値をxに変える
k += n - 1;//i番目の葉のノード番号
value[k] = a;
while (k > 0) {
k = (k - 1) / 2;//ノードiのノードの便号に変える
value[k] = min(value[k * 2 +1], value[k * 2 + 2]);
}
}
//[a,b)の最小値を求める
//後ろのほうの引数は計算の簡単のための引数
//kは節点の番号、l,rはその節点が[l,r)に対応づいていることを表す
//従って外からはquery(a,b,0,0,n)として呼ぶ
int query(int a, int b, int k, int l, int r) {
//[a,b)と[l,r)が交差しなければINT_MAX
if (r <= a || b <= l)return MAX_INF;
//[a,b)が[l,r)を完全に含んでいればこの節点の値
if (a <= l && r <= b)return value[k];
else {
//そうでなければ二つの子の最小値
int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);//左の子に値を聞く
int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);//右の子に値を聞く
return min(vl, vr);
}
}
int main() {
int N, Q; cin >> N >> Q;
n = 1;
while (n < N)n *= 2;
value = vector<int>(2 * n - 1, MAX_INF);
for (int j = 0; j < Q; ++j) {
int c; cin >> c;
if (c == 0) {
//update(i,x)
int i, x; cin >> i >> x;
update(i, x);
}
else {
//find(s,t)
int s, t;
cin >> s >> t;
cout << query(s, t + 1, 0, 0, n) << endl;
}
}
return 0;
}
例題 crane
クレーンがありますクレーンはN個の線分が端点で接続されたものと考えます。i番目の線分の長さはLiです。はじめはすべての線分がまっすぐ接続され上を向いています。C個のクレーンを動かす命令が来ます。各命令iは２つの整数Si,Aiで与えられます。これは線分Siと線分Si+1の間の角度をAi度にするという意味です。なお、角度は線分Siから半時計周りに線分Si+1を見た際の角度で最初の角度は180°です。
C個の命令は順次実行していきます。各命令に対しそれが終わったときのクレーンの先端の座標を出力してください。座標はクレーンの支点を(0,0)とします。
セグ木を用いて解く。各ノードは連続する線分の集合に対応し次の情報を持たせる。
・対応する線分たちを最初の線分を垂直にして繋げた際の
３－４動的計画法を極める！
bit dp
巡回セールスマン問題
頂点数nの重み付き有向グラフが距離行列d(i,j)として与えられます。辺がない場合はINF。頂点0からスタートして全ての頂点をちょうど一度ずつめぐって帰ってくる閉路のうち重みの総和の最小値を求めなさい。
すでに訪れた頂点集合がS,スタート地点0はまだ訪れていないものとする。現在vにいる状態から残りのすべての頂点０に帰るようなパスの重みの総和の最小値をdp[S][v]と表す。vからはまだ訪れていない頂点uに移動することができるので次のような漸化式が成り立つ
dp[V][0]=0
dp[S][v]=min{dp[S∨{u}][u]+d(v,u)|u(uはSに含まれない)}
int n, m;
vector<pii>G[20];
int dp[1 << 15][20];
//すでに訪れた頂点がS,現在位置がv
int rec(int S, int v) {
if (dp[S][v] >= 0) {
return dp[S][v];
}
if (S == (1 << n) - 1 && v == 0) {
return dp[S][v] = 0;
}
int res = INF;
for(auto u:G[v]){
if (!(S&(1 << u.first))) {
res = min(res, rec(S | 1 << u.first, u.first) + u.second);
}
}
return dp[S][v] = res;
}
int main() {
cin >> n >> m;
memset(dp, -1, sizeof(dp));
for (int i = 0; i < m; ++i) {
int from, to, cost;
cin >> from >> to >> cost;
G[from].push_back({ to,cost });
}
cout << rec(0, 0) << endl;
return 0;
}
dpでは下のように書ける
int n, m;
vector<pii>G[150];
int d[20][20];
int dp[1 << 16][20];
int solve(int s) {
memset(dp, INF, sizeof(dp));
dp[0][s] = 0;
for (int i = 0; i < (1 << n); ++i) {
for (int j = 0; j < n; ++j) {
if (dp[i][j] == INF)continue;
for (int k = 0; k < G[j].size(); ++k) {
pii e = G[j][k];
if (i&(1 << e.first))continue;
dp[i | (1 << e.first)][e.first] = min(dp[i | (1 << e.first)][e.first], dp[i][j] + e.second);
}
}
}
return dp[(1 << n) - 1][s];
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int a, b, c; cin >> a >> b >> c;
G[a].push_back({ b,c });
}
int mi = INF;
for (int i = 0; i < n; ++i)mi = min(mi, solve(i));
if (mi == INF)cout << -1 << endl;
else cout << mi << endl;
return 0;
}
traveling by stagecoach
ドミノ敷き詰め
nmのマスがあり各マスは白または黒に塗られています。12のブロックを重なりが生じないように敷き詰め全ての白のマスを覆い、黒のマスを一切覆わないような方法の総数を求めMで割った余りを答えなさい