【AtCoder】ABC040 B. □□□□□
AtCoderの問題
B: □□□□□ - AtCoder Beginner Contest 040 | AtCoder
参考書
難しさ(初心者目線)
・考え方**
・実装*
・面白さ***
問題概要
・大きさが同じn枚の正方形の紙がある
・何枚かを使って長方形(正方形も含む)を作る
・その時|縦の長さ-横の長さ|+使わないカードの枚数を最小にしたい
・最小値を求めよ
n≦100,000
方針
作れる長方形と余りを全探索で求める.
縦の長さを1からsqrt(n)まで探索する.
nまで探索する必要はない.
例えばn=10の時、もも同じだから.
このようにすればくらいでも時間内に終わる.
素数かどうかの判定で使われる手法.
コード
#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; int min_amari = 999999999; //全探索 for(int i=1; i<=sqrt(n); ++i){ int w, h, amari; w = i; h = n / i; amari = n % i; min_amari=min(min_amari,abs(w-h)+amari); } cout<<min_amari<<endl; }
【AtCoder】ABC044 C. 高橋君とカード
AtCoderの問題
C: 高橋君とカード / Tak and Cards - AtCoder Beginner Contest 044 | AtCoder
参考書
現在AtCoderの過去問AB(たまにC)解いてます.
難しさ(初心者目線)
・考え方***
・実装**
・面白さ**
問題概要
・数字がN個ある()
・何個か使ってAで割り切れる数を作りたい
・何通りあるか?
方針
・動的計画法
・dp[i][j][k]:=まででj個使ってkを作れる総数
を使うか使わないかの漸化式が考えられる
- 使わない場合は使う個数jとkは変わらない
dp[i+1][j][k] += dp[i][j][k]
- 使う場合は使う個数+1、kはk+x[i]
dp[i+1][j+1][k+x[i]] += dp[i][j][k]
コード
#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) ll dp[60][60][3000]; ll N,A; ll x[60]; int main(){ cin>>N>>A; FOR(i, 0, N) cin>>x[i]; FOR(i, 0, 60) FOR(j, 0, 60) FOR(k, 0, 3000) dp[i][j][k] = 0; dp[0][0][0] = 1; FOR(i, 0, N){ FOR(j, 0, N){ FOR(k, 0, 3000){ if(dp[i][j][k]==0) continue; //使わない時 dp[i+1][j][k] += dp[i][j][k]; //使う時 dp[i+1][j+1][k+x[i]] += dp[i][j][k]; } } } ll ans = 0; FOR(i, 1, N+1){ ans += dp[N][i][i*A]; } cout << ans << endl; }
【RCO】日本橋ハーフマラソン予選 A問題
AtCoderで開催された日本橋ハーフマラソンの予選のA問題です.
A問題に時間をかけすぎてBが悲惨なことになりました.
ちなみに予選115位でした…
A: Multiple Pieces - RCO presents 日本橋ハーフマラソン 予選 | AtCoder
参考書
問題概要
・50*50のマスに0~9の数字が書いてある
・9個の連結したマスを1グループとする
・グループ内の数同士の掛け算をそのグループの得点とする
・全てのグループの得点の和が最終的なスコア
・スコアを最大化するようにグループを作ってください
方針
・なるべく大きい数同士同じグループにしたい
と思ったので、実装しやすそうな9の周りから大きい数字を選んで行くという方法をとりました。
実装例
焦って書いたコードなので汚いです.
このコードだとA問題だけでは75位でした.
#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 H, W, K; vector<string> inputmass; int mass[51][51]; bool used[51][51]; typedef pair<int, int> YX;//座標 typedef pair<int, YX> P;//値,座標 int main(){ cin >> H >> W >> K; cin.ignore(); FOR(i, 0, H){ string s; getline(cin, s); inputmass.push_back(s); } FOR(i, 1, 51){ FOR(j, 1, 51){ mass[i][j] = inputmass[i-1][j-1] - '0'; } } //連結できるならqueに入れておく //4方向を見る int vx[4] = {0, 1, 0, -1}; int vy[4] = {-1, 0, 1, 0}; priority_queue<P> que; stack<YX> output; int C = 0; //9の周りでグループ作る->8の周りで->... for(int num = 9; num > 0; --num){ FOR(yi, 1, H+1){ FOR(xi, 1, W+1){ //すでに使われていたらもしくわnum(9->8->7->...)でなければcontinue if(used[yi][xi]==true || mass[yi][xi] != num) continue; while(!que.empty()) que.pop(); que.push(P(mass[yi][xi],YX(yi, xi))); used[yi][xi] = true; //queの周りを調べる //0出なければ連結させる int k = 0;//グループ内の数の個数-1 while(1){ if(k==8){ C++; while(!que.empty()){ P p = que.top();que.pop(); used[p.second.first][p.second.second] = false;//あまりは戻す } break; } //8個できるまでに連結できなかったら戻す if(que.empty()){ FOR(kesu, 0, k){ YX yx = output.top();output.pop(); used[yx.first][yx.second] = false;//グループにできてないので戻す } while(!que.empty()){ P p = que.top();que.pop(); used[p.second.first][p.second.second] = false; } break; } //使うところを保存 P p = que.top();que.pop(); output.push(p.second);//あとで出力する k++; //周りを調べる int y0 = p.second.first; int x0 = p.second.second; FOR(vi, 0, 4){ if(y0 + vy[vi] <= 0 || y0 + vy[vi] > H || x0 + vx[vi] <= 0 || x0 + vx[vi] > W) continue; if(mass[y0+vy[vi]][x0+vx[vi]]==0 || used[y0+vy[vi]][x0+vx[vi]]==true) continue; que.push(P(mass[y0+vy[vi]][x0+vx[vi]],YX(y0+vy[vi], x0+vx[vi]))); used[y0+vy[vi]][x0+vx[vi]] = true; } } } } } cout << C << endl; while(!output.empty()){ YX yx = output.top();output.pop(); cout << yx.first << " " << yx.second << endl; } }
コメント
1個隣だけでなく何個か先も見て得点が大きくなる場合を探す方法でやってみようと思います。
【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)); } } } }