【AtCoder】AGC011 B. Colorful Creatures
AtCoderの問題
B: Colorful Creatures - AtCoder Grand Contest 011 | AtCoder
参考書
難しさ（初心者目線）
・考え方***
・実装**
・面白さ***
問題概要
・N匹の生き物がいる
・それぞれ大きさがAiで色がiである
・この生き物は自分の大きさの2倍以下の生き物を吸収できる
・例えば大きさA色aの生き物が大きさB色bの生き物を吸収したら
・大きさA+B色aの生き物になる
・N匹の生き物が1匹になるまで吸収を繰り返した時ありえる色のパターンは？
方針
・小さい生き物からその生き物の色を最後まで残せるかどうか調べた
・昇順にソートした時、「生き物jまで合体生物の大きさの2倍>=生物j+1の大きさ」なら生き物jまでの色は残せるし生き物j+1の色も残せる
・「生き物jまでの合体生物の大きさの2倍<=生き物j+1の大きさ」なら生き物j+1の色しか残せない
吸収したらソートし直したほうがいいと思ったけどしないでACになった…
いいのかな?
コード
#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) int main(){ int N; cin >> N; vector<double> A(N); FOR(i, 0, N) cin >> A[i]; sort(A.begin(), A.end()); ll ans = 1; FOR(i, 0, N-1){ //どっちにもなれるなら色の可能性+1 if(A[i+1] <= A[i] * 2){ ans++; } //片方にしかなれないなら色の可能性は1になっちゃう else ans = 1; A[i+1] += A[i]; //sortすべき?? } cout << ans << endl; }
【AtCoder】AGC011 A. Airport Bus
AtCoderの問題
A: Airport Bus - AtCoder Grand Contest 011 | AtCoder
参考書
難しさ（初心者目線）
・考え方**
・実装**
・面白さ**
問題概要
・N人の人がバス停にTi時に来る
・それぞれの人はK以下の時間待てるがそれより待つことになると怒る
・バスの最大乗員人数はC人
・全員を怒らせないために必要なバスの台数の最小値は？
・バスが何時に来るかは任意に決められる(複数台同時でも良い)
方針
・あるバスに最初に乗った人が怒らないギリギリまで
・もしくは満員になるまで人を乗せる
・そしてまた新たに次のバスを用いる
・これの繰り返し
コード
焦って書いたコードなので汚いかもです!
#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) int main(){ int N; double C, K; cin >> N >> C >> K; vector<double> T(N, 0); FOR(i, 0, N) cin >> T[i]; sort(T.begin(), T.end()); int ans = 0; //先頭の人 double t = T[0]; int people = 0; bool last = false; FOR(i, 0, N){ //バス出発 if(t + K < T[i]){ ans++; people = 1; t = T[i]; } //乗れた else{ people++; //あるバスで最後の乗客だった場合 if(people==C){ ans++; people = 0; if(i+1==N) last = true; //次の先頭の人 t = T[i+1]; } } } if(!last) ans++; cout << ans << endl; }
【自分用メモ】Union-Find木
Union-Find木のコード
参考書
Union-Find木とは…
・グループ分けを管理するデータ構造
・根が同じ場合同じグループとする
#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) #define MAX_V ノードの数 int par[MAX_V]; //ノードiの親=par[i] 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){ x = find(x);//xの根 y = find(y);//yの根 if(x == y) return; //深い方にくっつける if(rnk[x]>=rnk[y]){ par[y] = x; if(rnk[x]==rnk[y]) rnk[x]++; } else{ par[x] = y; } } //同じグループかどうか bool same(int x, int y){ return find(x) == find(y) }
【自分用メモ】ダイクストラ法
ダイクストラ法のコード
ダイクストラ法とは…
グラフのある頂点から他の頂点への最短距離を求めるときの方法
参考書
ダイクストラ法 - Wikipediaのgifがわかりやすい
#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) #define INF 99999999 #define MAX_E 1000 #define MAX_V 1000 //ダイクストラ法 using queue //頂点の数 int V; //次の頂点、次の頂点へのコスト struct edge{ int to, cost; }; //頂点iと繋がっている頂点の情報 //G[i][頂点iと繋がっている頂点の個数] vector<edge> G[MAX_V]; //始点からのコスト、頂点番号 //priority_queueで並び変えるためにpair typedef pair<int, int> P; //始点sからのコスト int dijkstra(int s){ priority_queue<P, vector<P>, greater<P> > que; fill(d, d+V, INF); d[0] = 0; que.push(P(0, s)); while(!que.empty()){ P p = que.top();que.pop(); //頂点 int v = p.second; //すでに小さくなっていたらcontinue; if(d[v] < p.first) continue; //vと繋がっている頂点についてコストが下がるかどうかを調べる FOR(i, 0, G[v].size()){ edge e = G[v][i]; if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } }
【yukicoder】No.179 塗り替え
yukicoderさんの問題
参考書
難しさ（初心者目線）
・考え方***
・実装***
・面白さ***
問題概要
・白と黒で塗られたマスがある
・黒いマスを赤か青に塗り替えたい
・この時、赤いマスを平行移動させると青いマスにちょうど重なるようにしたい
・白いマス".“と黒いマス”#“が与えられるので、上記の条件で塗り替えられるかどうか求めよ
方針
・塗り替えられていない黒いマスについて(dx, dy)移動した先に塗り替えられていない黒マスがあればOK ・全探索
コード
#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) //方針 //塗り替えられていない黒いマスについて(dx, dy)移動した先に塗り替えられていない黒マスがあればOK //全探索 int main(){ int H, W; cin >> H >> W; //#or.を保存 vector<string> mass(H); FOR(i, 0, H) cin >> mass[i]; //塗り替えたかどうか bool isPainted[H][W]; FOR(i, 0, H) FOR(j, 0, W) isPainted[i][j] = false; //移動した先のマスを塗り替えられたかどうか bool check = false; FOR(dy, -H, H){ FOR(dx, -W, W){ //移動量が0の時は飛ばす if(dy==0 && dx==0) continue; //塗り替えたかどうかの情報初期化 FOR(i, 0, H) FOR(j, 0, W) isPainted[i][j] = false; //注目するマスをFORでまわす FOR(z, 0, (H-1)*W+W){ int y = z / W; int x = z % W; //塗り替えられていない#のマスについて if(mass[y][x]=='#' && isPainted[y][x]==false){ isPainted[y][x]=true; //移動先が範囲外ならbreak移動量変えてやり直し if(y+dy<0 || y+dy>=H || x+dx<0 || x+dx>=W){ check = false; break; } //移動先が塗り替えられていない#ならOK if(mass[y+dy][x+dx]=='#' && isPainted[y+dy][x+dx]==false){ isPainted[y+dy][x+dx]=true; check = true; } //塗り替えられていたらbreak移動量変えてやり直し else{ check = false; break; } } } //falseでなければ全て矛盾なかったということ if(check){ cout << "YES" << endl; return 0; } } } cout << "NO" << endl; }
【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,B２つの山がある
・山とは数字が書かれたブロックが１個ずつ積み重なったものを言う
・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; }
