読者です 読者をやめる 読者になる 読者になる

プロコン初心者日記

解いたプロコンの問題を保存しておくためのブログ

【POJ】Conscription

POJ 競技プログラミング Union-Find木 クラスカル法 面白い

POJの問題

3723 -- Conscription

参考書

プログラミングコンテストチャレンジブック [第2版]
今回の解法はこの本から得ています.

難しさ(初心者目線)

・考え方****

・実装****

・面白さ*****

問題概要

・女N人、男M人を雇いたい
・1人10000ドルで雇える ・ただし、女と男の間に親密な関係がある場合がある
・親密な関係は親密度Zで表される
・親密な場合はすでに片方が雇われていたらもう片方は(10000-Z)ドルで雇える
・雇う順番は自由である
・(N+M)人を雇うのにかかる最小のお金を求めよ

方針

・無向グラフで考える
・男と女の番号を頂点とする(男と女共に0から始まるので男は+Nしておく)
・男Aと女Bが親密な関係の場合頂点Aと頂点Bを結ぶ(costは-1*親密度にしておく)
・閉路ができないように辺を小さいコストから選んで行く->最小全域木->クラスカル

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define pb         push_back
#define mp         make_pair
#define ll         long long
#define PI         acos(-1.0)
#define ALL(A)     ((A).begin(), (A).end())
#define vsort(v)   sort(v.begin(),v.end())
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針
//無向グラフで考える
//男と女の番号を頂点とする(男と女共に0から始まるので男は+Nしておく)
//男Aと女Bが親密な関係の場合頂点Aと頂点Bを結ぶ(costは-1*親密度にしておく)
//閉路ができないように辺を小さいコストから選んで行く->最小全域木->クラスカル法
//答えは人数*10000 + 最小全域木のコスト

#define MAX_V 20000 //頂点の最大数
#define MAX_E 50000 //辺の最大数

/////////////////////union-find木/////////////////////
int par[MAX_V]; //親
int rnk[MAX_V]; //木の深さ

//配列の初期化
void init(int V){
    FOR(i, 0, V){
        par[i] = i;
        rnk[i] = 0;
    }
}

//根を探す
int find(int x){
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
}

//合併
void unite(int x, int y){
    int px = find(x);
    int py = find(y);
    //すでに一緒なら何もしない
    if(px == py) return;
    //深い方の木にくっつける
    if(rnk[px]>=rnk[py]){
        par[py] = px;
        if(rnk[px]==rnk[py]) rnk[py]++;
    }
    else par[px] = py;
    return;
}

//同じグループかどうか=根が同じかどうか
bool same(int x, int y){
    return find(x) == find(y);
}

/////////////////////////////kruskal////////////////////////////

struct edge { int u, v, cost; };

bool comp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}

edge es[MAX_E]; //辺の数分
int V, R;

//最小全域木を求めるアルゴリズム=クラスカル法
int kruskal(){
    //短い順にソート
    sort(es, es+R, comp);
    int ret = 0;
    FOR(i, 0, R){
        edge e = es[i];
        if(same(e.u, e.v)) continue;
        ret += e.cost;
        unite(e.v, e.u);
    }
    return ret;
}

////////////////////////main////////////////////////

int main(){
    int n; //テストケースの数
    cin >> n;
    int N, M;
    //改行があるからgetlineいる?
    string s;
    getline(cin, s);
    FOR(i, 0, n){
        scanf("%d %d %d", &N, &M, &R);
        V = N + M;
        //union-find木の初期化
        init(V);
        //親密関係入力->esに保存
        FOR(j, 0, R){
            scanf("%d %d %d", &es[j].u, &es[j].v, &es[j].cost); //cinだとLTE
            //性別を区別する女(0~N-1) 男(N~N+M-1)
            es[j].v += N;
            //親密度分だけ安くなる
            //-1をかけて小さい方がより多くお金が安くなる->小さくなるパスを選ぶ
            //->閉路ができてはいけない->最小全域木
            es[j].cost *= -1;
        }
        getline(cin, s);
        cout << (V * 10000 + kruskal()) << endl;
    }
}

コメント

クラスカル法ではUnion-Find木を用いることで閉路ができるかどうか判定できるので、 最小全域木を求めるのが簡単にできる.
クラスカル法を知らなかったので勉強になった.
クラスカル法 - Wikipedia

【AtCoder】ゲーム

面白い AtCoder 競技プログラミング 深さ優先全探索

AtCoderさんの問題

B: ゲーム - Typical DP Contest | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方****

・実装***

・面白さ****

問題概要

・すぬけくんとすめけくんがゲームを行う.
・ゲームのルールについて
・A,B2つの山がある
・山とは数字が書かれたブロックが1個ずつ積み重なったものを言う
・2人は交互にAかBの山からブロックを取る
・ブロックの数値の合計値が大きいほうが勝ち
・二人とも最善を尽くした時のすぬけくんの点数を求めよ

ヒント(カーソル合わせると見れます)

考え方

深さ優先全探索を再帰関数dfsを用いて行う方法について
すぬけくんのポイントを返り値とする
お互いベストを尽くすので
すぬけくんのターンはdfsが大きくなるように
すめけくんのターンはdfsが小さくなるように選んでいく(下図)
A B
1 6
5 9
上の山の場合す抜けくんはまずは1か6を取ることができる
f:id:nenuon61:20170303211751p:plain メモ化再帰をしないとTLE

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針
//深さ優先全探索+メモ化再帰で
//すぬけくんのポイント=dfs(Aを何個使ったか、Bを何個使ったか、どっちのターンか)
//すぬけくんのターンなら得られるポイントがmaxになるようにしたい
//すめけくんはすぬけくんのポイントがminになるようにしたい

int A, B;
int a[1001], b[1001];

//メモ化
int dp[1001][1001][2];
//who=1がすぬけ、0がすめけ
int dfs(int ai, int bi, int who){
    if(dp[ai][bi][who]!=-1) return dp[ai][bi][who];
    if(ai==A && bi==B) return 0;
    int ret = 0;
    //すぬけくんターン
    if(who==1){
        int rettmp1 = 0;
        int rettmp2 = 0;
        if(ai<A) rettmp1 = dfs(ai+1, bi, who^1) + a[ai+1];
        if(bi<B) rettmp2 = dfs(ai, bi+1, who^1) + b[bi+1];
        ret += max(rettmp1, rettmp2);
    }
    //すめけくんターン
    else{
      int rettmp1 = 999999999;
      int rettmp2 = 999999999;
      if(ai<A) rettmp1 = dfs(ai+1, bi, who^1);
      if(bi<B) rettmp2 = dfs(ai, bi+1, who^1);
      ret += min(rettmp1, rettmp2);
    }
    return dp[ai][bi][who] = ret;
}

int main(){
    //入力
    cin >> A >> B;
    FOR(i, 1, A+1) cin >> a[i];
    FOR(i, 1, B+1) cin >> b[i];
    //初期化
    FOR(i, 0, 1001) FOR(j, 0, 1001) FOR(k, 0, 2) dp[i][j][k] = -1;
    cout << dfs(0, 0, 1) << endl;
}

コメント

【CODEFORCES】Molly's Chemicals

CODEFORCES 競技プログラミング 全探索 map 面白い

CODEFORCESの問題

Problem - C - Codeforces

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方****

・実装**

・面白さ****

ヒント(カーソル合わせると見れます)

問題概略

・n個の異なった薬品を持っている
・薬品iの効果は{\alpha_i}である
・n個の薬品が並べられるので連続した薬品を選んで混ぜて整数kの累乗になるようにしたい
・この時の混ぜ方は何通りあるか

入力

n k
{\alpha_1 \alpha_2 ,,, \alpha_n}

1≦n≦10^{5}
1≦|k|≦10
{-10^{9}}{\alpha_i}{10^{9}}

Input

4 2
2 2 2 2

Output

8

n=4, k=2の問題
2^{1}になるのは左から1個目のみ,2個目のみ,3個目のみ,4個目のみ選んだ場合
2^{2}になるのは左から[1,2]と[2,3]と[3,4]のセットを選んだ時
同様に2^{3},2^{4}になる場合も調べたら8通りになる

Note

k^{0}=1であることに注意

考え方

左からの合計値sumをmapに保存していきsum-kx(図中黄色い丸)が存在すれば残りはkx(図中青い丸)である
forは太い青い矢印とkxを求める部分
愚直な実装は青い太い矢印の2重ループだと思うが、0(N2)で間に合わない
kxは1015程度まで調べれば良いので数回であるから早い f:id:nenuon61:20170302210101p:plain
f:id:nenuon61:20170302210105p:plain

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針
//愚直に全探索(2重のfor)でやるとO(N^2)でTLEしてしまう
//[1,i](i=1~N)で作れる薬品の効果をmap[効果]=1としておく
//1~Nで見ていく
//map[1~iの和-k^x]==1だと作れる(ans++)

int main(){
    int n, k;
    cin >> n >> k;

    //map用意αが大きいのでllとしておく
    //0は何も使わない時なので作れるので1としておく
    map<ll, int> MAP;
    MAP[0] = 1;

    ll int ans = 0;
    ll int sum = 0;
    FOR(i, 0, n){
        int input;
        cin >> input;

        //これまで調べた薬品を全て使用した時の和
        sum += input;
        //k=1の時は1を何乗しても1なので1を引く
        if(k == 1){
            ans += MAP[sum-1];
        }
        //k=-1の時は1と-1になるかどうか調べる
        else if(k == -1){
            ans += MAP[sum-1] + MAP[sum+1];
        }
        else{
            //|k|>1の時は十分大きな数まで調べる
            int j = 0;
            while(1){
                ans += MAP[sum-pow(k,j)];
                j++;
                if(abs(pow(k, j))>pow(10,15)) break;
            }
        }
        //これまで調べた薬品を全て使用した時の和を保存
        MAP[sum]++;
    }
    cout << ans << endl;
}

コメント

連続した値の和がxになるかどうかという問題があったらこの方法を用いたいと思う.

【yukicoder】No.90 品物の並び替え

yukicoder 競技プログラミング 全探索

yukicoderさんの問題

No.90 品物の並び替え - yukicoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方*

・実装**

・面白さ*

ヒント(カーソル合わせると見れます)

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針
//Nが小さいので順列を全探索しても9!=362880パターン=4*10^5くらい
//得られる点数は2重ループで計算する.(計算量はM*M/2)
//ギリギリ??
//->N=9M=66で14msだった

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

    //点数を保存score[後][前]
    int score[N][N];
    //memset(score, 0, sizeof(score));
    FOR(i, 0, N) FOR(j, 0, N) score[i][j] = 0;
    FOR(i, 0, M){
        int item1, item2, tmpscore;
        cin >> item1 >> item2 >> tmpscore;
        score[item2][item1] = tmpscore;
    }

    //全探索0~N-1の並び替え
    vector<int> v;
    FOR(i, 0, N) v.push_back(i);
    int ans = 0;
    do{
        int ret = 0;
        //v[usiro]が後ろにある数字v[mae]が前にある数字
        //なのでそれをscoreの配列に入れて点数を調べる
        FOR(usiro, 1, N) FOR(mae, 0, usiro) ret += score[v[usiro]][v[mae]];
        ans = max(ans, ret);
    }while(next_permutation(v.begin(), v.end()));
    cout << ans << endl;
}

コメント

Nが小さかったので全探索ができた.
並び替えはdo{処理}while(next_permutation(並び替えたいvector.begin(), vector.end()));でできる.

【yukicoder】No.207 世界のなんとか

yukicoder 競技プログラミング

yukicoderさんの問題

No.207 世界のなんとか - yukicoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方*

・実装*

・面白さ*

ヒント(カーソル合わせると見れます)

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define pb         push_back
#define mp         make_pair
#define ll         long long
#define PI         acos(-1.0)
#define ALL(A)     (A).begin(), (A).end()
#define vsort(v)   sort(v.begin(),v.end())
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int main(){
    ll int A, B;
    cin >> A >> B;
    string s;
    FOR(i, A, B+1){
        if(i%3==0) cout << i << endl;
        else{
            //stringにすると3を探すのが楽
            s = to_string(i);
            if(s.find("3")!=-1) cout << i << endl;
        }
    }
}

コメント

3の付く数字かどうか調べるのが厄介だけど数字をto_stringでstring型にしてからfindで3を探せば一発でわかる

【yukicoder】No.7 プライムナンバーゲーム

yukicoder 競技プログラミング 深さ優先全探索 メモ化再帰

yukicoderさんの問題

No.7 プライムナンバーゲーム - yukicoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方***

・実装***

・面白さ***

ヒント(カーソル合わせると見れます)

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針
//整数nに対して引く可能性のある素数を全て試して最終的に勝てるパターンが1つでもあるならWin
//深さ優先全探索+メモ化再帰でこれを行う
//dfs(n, 先攻) はdfs(n-素数, 後攻)のどれかがLoseならWinになる

//素数保存用vector
vector<int> vp;

//n以下の素数作成用関数
//エラトステネスの篩
void MakePrimeNumber(int n){
    vp.clear();
    int tmp[n+1];
    FOR(i, 0, n+1) tmp[i] = 1;
    FOR(i, 2, n+1){
        if(tmp[i]==0) continue;
        vp.push_back(i);
        int j = i;
        while(j <= n){
            tmp[j] = 0;
            j += i;
        }
    }
}

//メモ化再帰
int dp[10001][2];
int dfs(int n, int me){
    //計算済みならdpを返す
    if(dp[n][me]!=-1) return dp[n][me];

    //前の人が1,0にした場合
    //前の人が負けになる
    //me=1(自分)なら自分は勝ちそうでないなら負けパターンだったということ
    if(n==1 || n==0) return me == 1 ? 1 : 0;

    //引ける素数全探索
    int j = 0;
    int ret = 0;
    while(1){
        //前の人が勝ちなら今の人が負け
        //前の人が負けなら今の人は勝ちなので"!"dfs
        if(n-vp[j]>=2) ret = ret || !dfs(n-vp[j], (me+1)%2);
        else break;
        j++;
        //素数の上限に達したらbreak
        if(j==vp.size()) break;
    }
    return dp[n][me] = ret;
}

int main(){
  int N;
  cin >> N;
  //素数生成
  MakePrimeNumber(N);
  //配列初期化
  FOR(i, 0, 10001) FOR(j, 0, 2) dp[i][j] = -1;
  cout << (dfs(N, 1)==1 ? "Win" : "Lose") << endl;
}

コメント

ゲームでお互い最善を尽くす系の問題.
深さ優先全探索を使う問題.
最善を尽くすをどう表現すれば良いか悩んだ何回かWAを出してしまった.
お互いベストを尽くすので勝てるパターンが一つでもあれば勝ち(ゲーム木を書くとわかりやすい).
また、メモ化再帰を使わないとLTEになる??.
素数を求めるのはエラトステネスの篩が早いです.

【yukicoder】No.4 おもりと天秤

yukicoder 競技プログラミング 動的計画法

yukicoderさんの問題

No.4 おもりと天秤 - yukicoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方***

・実装***

・面白さ**

ヒント(カーソル合わせると見れます)

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針
//動的計画法
//dp[i][j]:i個目まで調べた時に(天秤A-天秤B)がjになるかどうか
//今回はjが0になるかどうか目指す
//途中でjがマイナスになることがある-N*100~N*100の範囲
//そこでN+100プラスして0~N*200で考え,N*100になるかどうか見ていく
//計算量はN*N*100

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

    int dp[N+1][N*200+1];
    FOR(i, 0, N+1) FOR(j, 0, N*200+1) dp[i][j] = 0;
    dp[0][N*100] = 1;

    //動的計画法
    FOR(i, 0, N){
        //入力
        int w;
        cin >> w;
        FOR(j, 0, N*200+1){

            //dp[i][j]があり得ないなら次もないのでcontinue
            if(dp[i][j]==0) continue;
            //一応範囲以外だったらcontinue
            if(j+w>N*200 || j-w<0) continue;

            //Aに置く
            dp[i+1][j+w] = 1;
            //Bに置く
            dp[i+1][j-w] = 1;
        }
    }
    cout << ((dp[N][N*100] == 1) ? "possible" : "impossible") << endl;
}

コメント