AtCoder Beginner Contest 036

[TakefumiYamamura]

http://abc036.contest.atcoder.jp/

[TakefumiYamamura]

C - 座圧

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

問題文

N 人の人が座っています。 i 番目の人の座圧は ai です。 すぬけ君は、大小関係を保存したまま座圧のデータを圧縮して保存することにしました。 以下の条件を満たす数列 b1,…,bN を求めてください。 bi はすべて非負整数である。 ai<aj ならば bi<bj である。 ai=aj ならば bi=bj である。 上の条件を満たす配列のうち、bi の最大値が最小となる。 このような条件をみたす b は一意に定まることが知られています。

制約

1≤N≤105 0≤ai≤109 ai は整数である。

部分点

30 点分のテストケースでは、1≤N≤103 をみたす。 上とは別の 30 点分のテストケースでは、0≤ai≤105 をみたす。

note

map使ってやった方がいいっぽい。いわゆる次元圧縮

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

struct Num
{
    int val;
    int index;
    static bool ValDesc(Num& a, Num& b){
        return a.val < b.val;
    }
    static bool IndDesc(Num& a, Num& b){
        return a.index < b.index;
    }
};

int main(){
    int n;
    vector<Num> nums;
    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        Num n;
        cin >> n.val;
        n.index = i;
        nums.push_back(n);
    }
    sort(nums.begin(), nums.end(), Num::ValDesc);

    int count = 0;
    int back;
    back = nums[0].val;
    nums[0].val = 0;
    for (int i = 1; i < n; ++i)
    {
        if(back != nums[i].val){
            count++;
        }
        back = nums[i].val;
        nums[i].val = count;
    }
    sort(nums.begin(), nums.end(), Num::IndDesc);

    for (int i = 0; i < n; ++i)
    {
        cout << nums[i].val << endl;
    }

    return 0;

}

[TakefumiYamamura]

D - 塗り絵

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

問題文

N 個の島があります。 島には 1 から N までの番号がついています。 また、N−1 個の橋があります。 i 番目の橋は ai 番の島と bi 番の島をつないでいます。 どの島からどの島へも橋をいくつか経由して到達できることがわかっています。

すぬけ君は、それぞれの島を白または黒に塗ることにしました。 ただし、両端の島が黒で塗られているような橋があってはいけません。 色の塗り方が何通りあるか、109+7 で割った余りを求めてください。

制約

2≤N≤105 1≤ai,bi≤N どの島からどの島へも橋をいくつか経由して到達できる

note

treeDPすればいいだけなんだけど、閉路にならないとはいえなくねって思ってなんかしっくりこない。。。。

#include <iostream>
#include <vector>
#define NIL -1
#define ll long long 
using namespace std;

vector<ll> G[100001];
ll dp[100001][2];
const ll MOD = 1e9+7;

ll f(int, int);
ll g(int, int);

ll f(int i, int p){
    if(dp[i][0] != NIL) return dp[i][0];
    ll ans = 0;
    ll tmp = 1;
    ans += g(i, p);
    ans %= MOD;

    for (int j = 0; j < G[i].size(); ++j)
    {
        if(G[i][j] != p){
            tmp *= g(G[i][j], i) % MOD;
            tmp %= MOD;
        }
    }
    ans += tmp;
    dp[i][0] = ans % MOD; 
    return ans;
}

ll g(int i, int p){
    if(dp[i][1] != NIL) return dp[i][1];
    ll tmp = 1;
    for (int j = 0; j < G[i].size(); ++j)
    {
        if(G[i][j] != p){
            tmp *= f(G[i][j], i) % MOD;
            tmp %= MOD;
        }
    }
    tmp %= MOD;
    dp[i][1] = tmp;
    return tmp;
}

int main(){
    int N;
    cin >> N;

    for (int i = 0; i < N-1; ++i)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for (int i = 0; i < N; ++i)
    {
        dp[i][0] = NIL; //f
        dp[i][1] = NIL; //g
    }

    cout << f(0, -1) % MOD << endl;

}