【POJ】Conscription
POJの問題
参考書
プログラミングコンテストチャレンジブック [第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さんの問題
B: ゲーム - Typical DP Contest | AtCoder
参考書
難しさ(初心者目線)
・考え方****
・実装***
・面白さ****
問題概要
・すぬけくんとすめけくんがゲームを行う.
・ゲームのルールについて
・A,B2つの山がある
・山とは数字が書かれたブロックが1個ずつ積み重なったものを言う
・2人は交互にAかBの山からブロックを取る
・ブロックの数値の合計値が大きいほうが勝ち
・二人とも最善を尽くした時のすぬけくんの点数を求めよ
考え方
深さ優先全探索を再帰関数dfsを用いて行う方法について
すぬけくんのポイントを返り値とする
お互いベストを尽くすので
すぬけくんのターンはdfsが大きくなるように
すめけくんのターンはdfsが小さくなるように選んでいく(下図)
A B
1 6
5 9
上の山の場合す抜けくんはまずは1か6を取ることができる
メモ化再帰をしないと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の問題
参考書
難しさ(初心者目線)
・考え方****
・実装**
・面白さ****
問題概略
・n個の異なった薬品を持っている
・薬品iの効果はである
・n個の薬品が並べられるので連続した薬品を選んで混ぜて整数kの累乗になるようにしたい
・この時の混ぜ方は何通りあるか
入力
n k
1≦n≦
1≦|k|≦10
≦≦
例
Input
4 2
2 2 2 2
Output
8
n=4, k=2の問題
になるのは左から1個目のみ,2個目のみ,3個目のみ,4個目のみ選んだ場合
になるのは左から[1,2]と[2,3]と[3,4]のセットを選んだ時
同様に,になる場合も調べたら8通りになる
Note
であることに注意
考え方
左からの合計値sumをmapに保存していきsum-kx(図中黄色い丸)が存在すれば残りはkx(図中青い丸)である
forは太い青い矢印とkxを求める部分
愚直な実装は青い太い矢印の2重ループだと思うが、0(N2)で間に合わない
kxは1015程度まで調べれば良いので数回であるから早い
コード
#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さんの問題
参考書
難しさ(初心者目線)
・考え方*
・実装**
・面白さ*
コード
#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さんの問題
参考書
難しさ(初心者目線)
・考え方*
・実装*
・面白さ*
コード
#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さんの問題
参考書
難しさ(初心者目線)
・考え方***
・実装***
・面白さ***
コード
#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さんの問題
参考書
難しさ(初心者目線)
・考え方***
・実装***
・面白さ**
コード
#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; }