AtCoder Beginner Contest 041

[TakefumiYamamura]

http://abc041.contest.atcoder.jp/

[TakefumiYamamura]

C - 背の順

時間制限 : 2sec / メモリ制限 : 256MB

問題文

高橋学級には N 人の生徒がいます。 生徒は 1 から N まで出席番号が振られています。 i 番目の生徒の身長は ai です。 ai はすべて相異なります。

高橋先生は N 人の生徒を背の高い方から順に並べました。 N 人の生徒の出席番号を背の高い方から順に出力してください。

制約

2≦N≦105 ai は整数である。 1≦ai≦109 ai はすべて相異なる。

部分点

30 点分のテストケースでは、N≦1000 を満たす。

note

添字付きマージソートするだけ

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#define ll long long 
#define MAX 1000001
using namespace std;

struct Num{
    ll value, index;
    static bool Asc(const Num& x, const Num& y){ return x.value > y.value ;}

};

int main(){
    ll n;
    cin >> n;
    vector<Num> nums;
    for (int i = 1; i <= n; ++i)
    {
        Num num;
        cin >> num.value;
        num.index = i;
        nums.push_back(num);
    }
    sort(nums.begin(), nums.end(), Num::Asc);
    for (int i = 0; i < n; ++i)
    {
        cout << nums[i].index << endl;
    }

}

[TakefumiYamamura]

D - 徒競走

時間制限 : 3sec / メモリ制限 : 256MB

問題文

N 匹のうさぎがいます。 うさぎは 1 から N まで番号が振られています。

これら N 匹のうさぎが徒競走をしました。 同着はいませんでした。 このとき、着順は N! 通り考えられます。

高橋君は M 人の観客から情報を集めました。 i 番目の観客によると、うさぎ xi はうさぎ yi よりも先にゴールしたそうです。

すべての観客の情報に合致するような着順が何通り考えられるか求めてください。

制約

2≦N≦16 1≦M≦N(N−1)⁄2 1≦xi，yi≦N xi≠yi (xi，yi) の組はすべて相異なる。 すべての観客の情報に合致するような着順が少なくともひとつ存在する。

部分点

30 点分のテストケースでは、N≦8 を満たす。

Note

トポロジカルソートの数え上げをbitDPでやるだけ

#include <iostream>
#include <algorithm>
#include <vector>
#define ull unsigned long long

using namespace std;

int main(){
    int n, m;
    int edges[17][17] = {0};
    ull dp[(1<<16)+1] = {0};//Don't forget initialize.
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int x, y;
        cin >> x >> y;
        edges[y-1][x-1] = 1;
    }
    dp[0] = (ull)1;

    for (int bit = 0; bit < (1 << n); ++bit)
    {
        for (int j = 0; j < n; ++j)
        {
            if((bit >> j & 1) != 1){
                bool check = true;
                for (int k = 0; k < n; ++k)
                {
                    if((bit >> k & 1) != 1 && edges[k][j] == 1 ){
                        check = false;
                        break;
                    }
                }
                if(check){
                    dp[bit|(1<<j)] += dp[bit];
                }
            }
        }
    }
    cout << dp[(1<<n)-1] << endl;

}