ARC 044 B - 最短路問題

問題

問題概要

A1をstartとした時の頂点までの最短経路の情報が与えられる. その木の高さで作ることのできるグラフは何通りあるか, mod1e9+7で答えろ.

解法

まず, A１からの最短経路の情報が与えられているはずなので, A1以外で最短経路が0であればそのようなグラフは作れない.
また, 最短経路は連続したものであるといえる. (最短経路が0, 1, 3のように与えらた場合, 2がないので, どのようにやってもグラフは作れない)
ではグラフが作れる条件を満たしている場合どのようにすれば場合の数が数え上げることができるかだが, まず最短経路が同じもの同士を繋いでも最短経路が変わることはないので, 同じ高さ同士のものは好きなようにつなぐことができる. 同じ高さの頂点を2つ選び方法は, sum[i] := 距離iの頂点個数として, sum[i] C 2 で求まり, その辺を使うか使わないかそれぞれ選ぶことができるので, pow(2, sum[i] C 2)通りあることになる.
次に距離の違うもの同士をどのように繋ぐかだが, まず, 距離の差が1より大きいものと繋いでしまうと, 最短経路の情報がずれてしまうのでダメ(1と 3をつなぐと最短経路3のものが最短経路2になってしまう)
よって距離i, i+1の場合を考えれば良いことになる. 距離i+1の頂点は, iの頂点のどれかと必ず繋がないと, グラフとつながっていないことになってしまうので, i のどれかと繋ぐようにする. i+1の頂点一つについて考えれば,
pow(2, sum[i]) - 1
となる. -1はどれも選ばないのをなくすため.
あとは, これをi+1の頂点全てについて考えれば良い.

ミス

考察段階でだいぶ悩んだ. 1つの辺をつけるかつけないかの2通りということを意識して考えていけば, もっとすんなりいけた?

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

ll n;
ll a[200010];
ll sum[200010];

//x^k mod
long long powmod(long long x, long long k, long long m){ // 繰り返し二乗法(logk)
    if(k == 0) return 1;
    if(k % 2 == 0) return powmod(x * x % m, k / 2, m);
    else return x * powmod(x, k - 1, m) % m;
}

int main(void){
    ll max_a = 0;
    cin >> n;
    rep(i, n){
        cin >> a[i];
        chmax(max_a, a[i]);
    }

    if(a[0] != 0){
        printf("0\n"); return 0;
    }
    reps(i, 1, n) if(a[i] == 0){
        printf("0\n"); return 0;
    }

    rep(i, n){
        sum[a[i]]++;
    }
    rep(i, max_a + 1){
        if(sum[i] == 0){ // グラフの高さにで飛んでいるものはない
            printf("0\n"); return 0;
        }
    }

    ll ans = 1;
    //同じ高さのものをつなぐ
    reps(i, 1, max_a + 1){
        //同じ高さの頂点を2つ選ぶ方法は, sum[i] C 2 通り
        ans *= powmod(2, sum[i] * (sum[i] - 1) / 2, MOD);
        ans %= MOD;
    }
    //下のやつと一つ上のやつをつなぐ 
    for (int i = max_a; i >= 1; --i){
        //任意の下のやつ1つに対して上のやつを選ぶか選ばないか (何も選ばないのはダメ)
        ll t = powmod(2, sum[i - 1], MOD) - 1;
        ans *= powmod(t, sum[i], MOD); //下の奴がsum[i]個あるので
        ans %= MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

ARC 044 A - 素数判定

問題

問題概要

Nが素数ならPrime
Nが合成数で, 1の位が2,5で割り切れず, 各桁の和が3で割り切れないとき, Prime
それ以外なら Not Prime

解法

まず, 普通に素数判定をし, 素数ならPrime.
次に, 1のくらいが2, 5で割り切れず, 各桁の和が3で割り切れないければ, Primeとして それ以外はNot Primeとなる.

ミス

各桁の和が３の倍数の時は, その数は3の倍数でした. 忘れてた.
N = 100a+10b + c = 99a + 9b + (a + b + c)
なので, a+b+c(各桁の和)が3の倍数であれば, 3の倍数となる. 各桁の和が9の倍数なら, 9の倍数でもあるのか.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


int main(void){
    string s; cin >> s;
    ll n = stoll(s);
    if(n == 1){
        printf("Not Prime\n"); return 0;
    }
    auto d = s.back() - '0';
    int sum = 0;
    bool f = true;
    for(auto u : s) sum += u - '0';
    for (int i = 2; i * i <= n; ++i){
        if(n % i == 0){
            f = false;
            break;
        }
    }
    if(f){
        printf("Prime\n"); return 0;
    }

    if((d % 2 != 0 && d != 5) && sum % 3 != 0){
        printf("Prime\n");
    }else{
        printf("Not Prime\n");
    }
    return 0;
}

Codeforces 400 (Div. 1 + Div. 2, combined) B. Sherlock and his girlfriend

問題

問題概要

i番目のものをi+1として考えて, 色を塗っていく. 塗る色はその数の素因数と同じ色にしてはいけない. 塗る色の最小数を求める問題.

解法

その数しか素因数を持たない素数はすべて同じ色で塗ることが可能. そのようにすると, 素数でない数はすべてその数が持つ素因数が同じ色で塗られているので, その色以外の色で塗ることができる. つまり素数は色1, 素数でないものは色2で塗ることができる.
ただし, n = 1, 2の時は別でやる.

ミス

なし.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


bool isprime[100100];
//エラトステネス
void eratos(int m){
    for (int i = 0; i <= m; ++i) isprime[i] = true;
    isprime[0] = isprime[1] = false;
    //iを残してiの倍数を消していく
    for (int i = 2; i <= m; ++i){
        if(isprime[i]){
            for (int j = 2 * i; j <= m; j += i){
                isprime[j] = false;
            }
        }
    }
}

int main(void){
    int n; cin >> n;
    if(n == 1){
        printf("1\n");
        printf("1\n");
        return 0;
    }else if(n == 2){
        printf("1\n");
        printf("1 1\n");
        return 0;
    }
    eratos(n + 10);
    printf("2\n");
    reps(i, 2, n + 2){
        if(isprime[i]){
            printf("1 ");
        }else{
            printf("2 ");
        }
    }
    printf("\n");
    return 0;
}

Codeforece 400 (Div. 1 + Div. 2, combined) A. A Serial Killer

問題

問題概要

文字列が2つ与えられる. ひとつの文字列を指定された文字列に置換する操作を行うクエリに応える.

解法

setで管理しながら, 置換される方をeraseして, 加える方をinsertしていけばいい.

ミス

なし.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int main(void){
    set<string> se;
    vector<string> ans;
    rep(i, 2){
        string t; cin >> t;
        se.insert(t);
        ans.pb(t);
    }
    int n; cin >> n;

    rep(i, n){
        string t1, t2; cin >> t1 >> t2;
        se.erase(t1);
        se.insert(t2);
        for(auto u : se){
            ans.pb(u);
        }
    }
    int cnt = 0;
    for(auto u : ans){
        if(cnt % 2 == 0) cout << u << " ";
        else cout << u << endl;
        cnt++;
    }
    return 0;
}

codeforces 401 div2 D. Cloud of Hashtags

問題

問題概要

与えられた文字列をすべて与えらた順番で辞書順にする. そのために各文字列から末尾の文字を好きなだけ取り除いていい. 取り除く文字の最小数を求める問題.

解法

一番後ろの文字はそのままにできることがわかるので, 後ろから順番に見ていき, 貪欲にできるだけ文字を残していけばいい. どこまで残すかの判定は, i番目とi+1番目の文字列を考えた時に, s[i][p] と s[i + 1][p] のようにiとi+1の文字列のp番目の文字を比較した時に, i番目の文字がi+1番目の文字以下である間は残して, 超えたらその文字より手前でi番目の文字列を切ればいい.

ミス

計算量大丈夫なんかな. resize便利

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


int n;
string s[500100];

int main(void){
    scanf("%d", &n);
    rep(i, n) cin >> s[i];
    for (int i = n - 2; i >= 0; --i){
        if(s[i] > s[i + 1]){ //変える必要あり
            int p = 0;
            while(p < s[i + 1].size() && p < s[i].size() && s[i][p] <= s[i + 1][p]) p++;
            s[i].resize(p);
        }
    }
    rep(i, n){
        printf("%s\n", s[i].c_str());
    }
    return 0;
}

codeforces 401 div2 B. Game of Credit Cards

問題

問題概要

数列a, bが与えられる. 数列ｂは好きな順番に変更することができる.
(1) a[i] > b[i] となる i の個数の最小数
(2) a[i] < b[i]となる i の個数の最大数
を求める問題

解法

2部マッチングの最大数を使ってとく.
数列bを任意の順番に動かすことができるので, (2)はa_i < b_j となるものすべてに辺をはって 2部マッチングの最大数を計算すればいい.
(1)はa[i] <= b[i]となる i の個数の最大数を求めることができれば解くことができるので, a_i <= b_j となるものすべてに辺をはって, 2部マッチングの最大値数を計算すればいい.
実装方法は最大流を求めるライブラリを使って, スタート地点とゴール地点を作ってやればいい.
また貪欲に得方法もある. (1)の場合, aの小さいところから貪欲にa<=bを満たすものの数をカウントしていけばいいし, (2)の場合, aの小さいところから貪欲にa<bをしていけばいい.

ミス

難しい.

コード

二部マッチング

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

const int MAX_V = 2010; //必要な頂点数
struct Flow{
    struct edge{
        int to, cap, rev;
    };
    vector<edge> G[MAX_V];//隣接リスト
    bool used[MAX_V];
 
    void add_edge(int from, int to, int cap){
        G[from].push_back((edge){to, cap, (int)G[to].size()});//from -> to
        G[to].push_back((edge){from, 0, (int)G[from].size() - 1});//to -> from
    }
    //増加パスを探す
    int dfs(int v, int t, int f){
        if(v == t) return f;
        used[v] = true;
        for (int i = 0; i < G[v].size(); ++i){
            edge &e = G[v][i];
            if(!used[e.to] && e.cap > 0){
                int d = dfs(e.to, t, min(f, e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    //sからtへの最大流
    int max_flow(int s, int t){
        int flow = 0;
        while(1){
            memset(used, 0, sizeof(used));
            int f = dfs(s, t, INF);
            if(f == 0) return flow;
            flow += f;
        }
    }
};

int n;
int main(void){
    int n; cin >> n;
    string a, b; cin >> a >> b;
    Flow fw1, fw2;
    // s -> a() -> b() -> t

    //s->a
    rep(i, a.size()){
        fw1.add_edge(n * 2, i, 1);
        fw2.add_edge(n * 2, i, 1);
    }
    //b->t
    rep(i, b.size()){
        fw1.add_edge(n + i, n * 2 + 1, 1);
        fw2.add_edge(n + i, n * 2 + 1, 1);
    }


    // a[k] <= b[k] の最大値を求める
    rep(i, a.size())rep(j, b.size()){
        if(a[i] <= b[j]) fw1.add_edge(i, n + j, 1);
    }
    //Bが勝てる最小数
    cout << n - fw1.max_flow(n * 2, n * 2 + 1) << endl;

    // a[k] <b[k] の最大値を求める
    rep(i, a.size())rep(j, b.size()){
        if(a[i] < b[j]) fw2.add_edge(i, n + j, 1);
    }
    //Aが勝てる回数の最大値
    cout << fw2.max_flow(n * 2, n * 2 + 1) << endl;
    return 0;
}

貪欲

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int n;
int main(void){
    int n; cin >> n;
    string a, b; cin >> a >> b;
    vector<int> va, vb;
    for(auto u : a) va.pb(u - '0');
    for(auto u : b)vb.pb(u - '0');
    sort(all(va)); sort(all(vb));

    //a[i] > b[i] の最小数 a[i] <= b[i]の最大数
    //aの小さいところから貪欲にa<=bをしていけばいい
    int ans1 = 0;
    int p = 0;
    rep(i, n){
        while(p < n && va[i] > vb[p])p++;
        if(p < n) ans1++, p++;
        if(p >= n) break;
    }
    cout << n - ans1 << endl; // 最小値に戻す

    // a[i] < b[i]の最大数
    //aの小さいところから貪欲にa<bをしていけばいい
    int ans2 = 0;
    p = 0;
    rep(i, n){
        while(p < n && va[i] >= vb[p]) p++;
        if(p < n) ans2++, p++;
        if(p >= n) break;
    }
    cout << ans2 << endl;
    return 0;
}

codeforces 401 div2 A. Shell Game

問題

問題概要

カップを3つ用意して, その中のどこかに玉をいれる. カップの番号を左から0, 1, 2としてn回動かす. その動かし方は, 奇数回の時は0と1を入れ替えて, 偶数回の時は1と2を入れ替える. n回入れ替えたあとの位置が与えられるので, はじめ何番目の位置に玉が入っていたかを求める問題.

解法

012
102
120
210
201
021
という順番で動きはじめの012に戻る. これは周期6で動くので, mod6の値を使って計算すればよい.

ミス

実験が大切.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int main(void){
    vector<vector<int>> v = {
        {0, 1, 2}, {1, 0, 2}, {1, 2, 0}, {2, 1, 0}, {2, 0, 1}, {0, 2, 1},
    };

    int n, x; cin >> n >> x;
    n %= 6;
    printf("%d\n", v[n][x]);
    return 0;
}