ルクの競プロ部屋

学生の競プロ生活を見たい人はどぞ

競プロ精選 100 問 by C++<全探索：順列全探索>

精選100問

はじめに...

全探索編最後の章です！
順列全探索の3問やりました！
精選100問はこちら！

15　AtCoder Beginner Contest 145 C - Average Length

問題はこちらです！
問題文↓

N個の街の座標が与えられる
街をすべて巡るのにはN!通りの方ほうがあることは自明
すべての街のめぐり方を取ったときの距離の平均を求めてください
距離の式はsqrt((x_i-x_j)^2+(y_i-y_j)^2)とします

例えば、N=3のとき
(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)の6通りをすべて書き出すことが出来たら良い！
C++でこういうときはnext_permutationを使う！
2≦n≦8だから8!で間に合うのでこんな感じになりました！

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> M(n);
    rep(i, n) cin >> M[i].first >> M[i].second;
    double ans = 0;
    int x = 0;
    sort(all(M));// 忘れずにソートする.
    // 順列全探索！！！.
    do
    {
        double c = 0;
        for (int i = 0; i < M.size() - 1; i++)
        {
            c += sqrtl((M[i].first - M[i + 1].first) * (M[i].first - M[i + 1].first) + (M[i].second - M[i + 1].second) * (M[i].second - M[i + 1].second));
        }
        ++x;
        ans += c;
    } while (next_permutation(all(M)));
    cout << setprecision(11) << ans / x << endl;
    return 0;
}

こういうのはスニペット登録しとく！

16　AtCoder Beginner Contest 150 C - Count Order

問題はこちらです！
問題文↓

1からNまでのリストを辞書順に全列挙してほしい
そこで、2つのリストを与えるので、辞書順で何番目と何番目になるかを教えてください
ただし、解答方法は2つのリストの番号の差の絶対値にしてください

順列全探索をするだけ！

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

template <typename T>
bool vectorEqual(vector<T> const &v1, vector<T> const &v2)
{
    return (v1.size() == v2.size() && equal(v1.cbegin(), v1.cend(), v2.cbegin()));
}

int main()
{
    int n;
    cin >> n;
    vector<int> A(n), B(n), C(n);
    rep(i, n) A[i] = i + 1;
    rep(i, n) cin >> B[i];
    rep(i, n) cin >> C[i];
    int x = 0;
    int b, c;
    do
    {
        ++x;
        if (vectorEqual(A, B))
            b = x;
        if (vectorEqual(A, C))
            c = x;
    } while (next_permutation(all(A)));
    cout << abs(b - c) << endl;
    return 0;
}

1からNまでのリストAの順列を全列挙して、B・Cに当てはまるときがあったらメモしておく
最後に差の絶対値を取ったら終了！

17　ALDS_13_A - 8 クイーン問題

問題はこちらです！
問題文↓

角と飛車を合わしたような動きをするクイーンがいる
このクイーンを8×8のチェス盤に8個並べる時、どのクイーン同士も取られない置き方にしたい
初めの数個は置く位置を指定して、解は1つだけに絞れるようにするので、このただ1つの解を求めてください

メッチャクチャ時間かかりました
前の回で使った組み合わせ全列挙と深さ優先探索をすることで解くことが可能です！
多分、順列全探索で解けるのだろうけど思いつかない、、、
結果こんな感じになりました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

vector<pair<int, int>> M;
vector<pair<int, int>> N;
int x = 0;
int y = 0;
bool f = false;

void recursive_comb(vector<int> indexes, int s, int rest, function<void(vector<int>)> f)
{
    if (rest == 0)
    {
        f(indexes);
    }
    else
    {
        if (s < 0)
            return;
        recursive_comb(indexes, s - 1, rest, f);
        indexes[rest - 1] = s;
        recursive_comb(indexes, s - 1, rest - 1, f);
    }
}

void foreach_comb(int n, int k, function<void(vector<int>)> f)
{
    vector<int> indexes(k);
    recursive_comb(indexes, n - 1, k, f);
}

// どのクイーン同士も取られない置き方か.
bool isHit()
{
    N.resize(M.size());
    copy(all(M), N.begin());
    f = false;
    auto lambda = [](vector<int> indexes)
    {
        f |= (N[indexes[0]].first == N[indexes[1]].first ||
              N[indexes[0]].second == N[indexes[1]].second ||
              abs(N[indexes[0]].first - N[indexes[1]].first) == abs(N[indexes[0]].second - N[indexes[1]].second));
    };
    foreach_comb(N.size(), 2, lambda);
    return f;
}

// xがMに入っているか.
bool xInM(int x)
{
    bool flag = false;
    rep(i, M.size())
    {
        flag |= (M[i].first == x);
    }
    return flag;
}

// 再帰的にQueenを設置する.
void setQueen()
{
    // もし、xが最後まで行ったら終了.
    if (x == 8)
    {
        return;
    }
    // もうすでにxが存在していたらパス.
    if (xInM(x))
    {
        ++x;
    }
    else
    {
        M.push_back({x, y});
        // もし、どのクイーン同士も取られない置き方だったら次に行く.
        if (!isHit())
        {
            ++x;
            y = 0;
        }
        else
        {
            ++y;
            M.pop_back();
            while (y == 8)
            {
                // どんどん遡る.
                x = M.back().first;
                y = M.back().second + 1;
                M.pop_back();
            }
        }
    }
    // DFSのループ.
    setQueen();
}

int main()
{
    // input.
    int n;
    cin >> n;
    rep(i, n)
    {
        int x, y;
        cin >> x >> y;
        M.push_back(pair(x, y));
    }

    // 深さ優先探索.
    setQueen();

    // 結果を作成する.
    vector<string> ans(8, string(8, '.'));
    rep(i, M.size())
    {
        ans[M[i].first][M[i].second] = 'Q';
    }

    // 出力.
    rep(i, 8)
    {
        cout << ans[i] << endl;
    }
    return 0;
}

2時間ぐらい格闘しましたよ、、、

最後に...

最後までお疲れ様でした！ ではまた！