AOJ 0530 Pyon-Pyon River Crossing
問題ページ
ぴょんぴょん川渡り | Aizu Online Judge
考えたこと
制約が色々小さくて最小コストを求めるので拡張dijkstraやDPを考える。
dp[i][j][k] = (i行目j列目まででk回一行飛ばしをしたときの最小滑りやすさ) としてDPを考えるとO(NMmax(k)^2)で計算量的には問題なさそう。岸から石に移るときの処理がうまくまとめられなかったので例外処理をする。こういうときはコメントを書くなり紙で整理してから実装しないとバグらせるので気をつけながらDPを書くと通った。
問題文が長くて実装面倒でICPCっぽさを感じた。
//#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; //#define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; vector<PII> stone[155]; int dp[155][15][100]; signed main(void) { while(true) { int n, m; cin >> n >> m; if(!n) break; REP(i, n) { int k; cin >> k; stone[i].clear(); REP(j, k) { int x, d; cin >> x >> d; stone[i].PB({x, d}); } } memset(dp, 0x3f, sizeof(dp)); REP(i, stone[0].size()) dp[0][i][0] = 0; REP(i, stone[1].size()) dp[1][i][1] = 0; // i行目j列 一行飛ばしをk回やった REP(i, n-1) REP(j, stone[i].size()) REP(k, m+1) { if(dp[i][j][k] == 0x3f3f3f3f) continue; // (i, j)から一行飛ばししないとき // dp[i+1][l][k] を minで更新 REP(l, stone[i+1].size()) { int dif = abs(stone[i][j].first - stone[i+1][l].first); int tmp = dif*(stone[i][j].second + stone[i+1][l].second); chmin(dp[i+1][l][k], dp[i][j][k] + tmp); } // (i, j)から一行飛ばしするとき // dp[i+2][l][k+1] を minで更新 if(i == n-2 || k == m) continue; REP(l, stone[i+2].size()) { int dif = abs(stone[i][j].first - stone[i+2][l].first); int tmp = dif*(stone[i][j].second + stone[i+2][l].second); chmin(dp[i+2][l][k+1], dp[i][j][k] + tmp); } } // n-1行目のmin、n-2行目でm-1以下のmin int ret = INF; REP(i, stone[n-1].size()) REP(k, m+1) chmin(ret, dp[n-1][i][k]); REP(i, stone[n-2].size()) REP(k, m) chmin(ret, dp[n-2][i][k]); cout << ret << endl; } return 0; }
AOJ 0596 Taxis
問題ページ
タクシー | Aizu Online Judge
考えたこと
最短距離と言われたのでdijkstraを考える。遷移先が距離r[i]以下の頂点であるdijkstraをすればよさそう。全頂点からそれぞれdijkstraをしてある頂点から距離がr[i]以下の点を全列挙しておけば、あとはdijkstraでよさそう。前処理にO(EVlogV)で大体1*10^8くらいになりそうだけどTLが8secで緩いのでこれでも通りそうと思い投げたら通った。
//#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; //#define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; int c[5010], r[5010]; struct edge{int to, cost;}; int n, d[5010]; vector<edge> g[5010]; VI v[5010]; void dijkstra(int s) { priority_queue<PII, vector<PII>, greater<PII>> que; fill(d, d+n, INF); d[s] = 0; que.push(PII{0, s}); while(que.size()) { PII p = que.top(); que.pop(); int v = p.second; if(d[v] < p.first) continue; for(edge e: g[v]) { if(d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.push(PII{d[e.to], e.to}); } } } REP(i, n) if(d[i] <= r[s]) v[s].PB(i); } void dijkstra2(int s) { priority_queue<PII, vector<PII>, greater<PII>> que; fill(d, d+n, INF); d[s] = 0; que.push(PII{0, s}); while(que.size()) { PII p = que.top(); que.pop(); int vv = p.second; if(d[vv] < p.first) continue; for(int i: v[vv]) { if(d[i] > d[vv] + c[vv]) { d[i] = d[vv] + c[vv]; que.push(PII{d[i], i}); } } } cout << d[n-1] << endl; } signed main(void) { int k; cin >> n >> k; REP(i, n) cin >> c[i] >> r[i]; REP(i, k) { int x, y; cin >> x >> y; x--, y--; g[x].PB({y, 1}); g[y].PB({x, 1}); } REP(i, n) dijkstra(i); dijkstra2(0); return 0; }
AOJ 0580 Fish
問題ページ
魚の生息範囲 | Aizu Online Judge
考えたこと
3次元imosすればよさそうだけど制約的に無理。領域木とかを考えてもわからないので解説を見たらただの座圧ではい。O(N4)で解ける
これくらいは思いつきたかった…
//#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; #define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // xx, yy, zzにそれぞれ座圧する元の配列を突っ込むとx, y, zが座圧された配列で返ってくる // zip[座圧前] = 座圧後、unzip[座圧後] = 座圧前 VL xx, x, unzipx(100010), yy, y, unzipy(100010), zz, z, unzipz(100010); unordered_map<int, int> zipx, zipy, zipz; void compress() { x = xx; sort(ALL(xx)); xx.erase(unique(ALL(xx)), xx.end()); REP(i, xx.size()) {zipx[xx[i]] = i; unzipx[i] = xx[i];} REP(i, x.size()) x[i] = zipx[x[i]]; y = yy; sort(ALL(yy)); yy.erase(unique(ALL(yy)), yy.end()); REP(i, yy.size()) {zipy[yy[i]] = i; unzipy[i] = yy[i];} REP(i, y.size()) y[i] = zipy[y[i]]; z = zz; sort(ALL(zz)); zz.erase(unique(ALL(zz)), zz.end()); REP(i, zz.size()) {zipz[zz[i]] = i; unzipz[i] = zz[i];} REP(i, z.size()) z[i] = zipz[z[i]]; } int dp[105][105][105]; int sx[55], sy[55], sd[55], gx[55], gy[55], gd[55]; signed main(void) { int n, K; cin >> n >> K; REP(i, n) { cin >> sx[i] >> sy[i] >> sd[i] >> gx[i] >> gy[i] >> gd[i]; xx.PB(sx[i]); xx.PB(gx[i]); yy.PB(sy[i]); yy.PB(gy[i]); zz.PB(sd[i]); zz.PB(gd[i]); } compress(); REP(i, n) { FOR(z, zipz[sd[i]], zipz[gd[i]]) FOR(y, zipy[sy[i]], zipy[gy[i]]) FOR(x, zipx[sx[i]], zipx[gx[i]]) { dp[z][y][x]++; } } ll ret = 0; REP(i, z.size()) REP(j, y.size()) REP(k, x.size()) { if(dp[i][j][k] >= K) { ret += (unzipz[i+1]-unzipz[i])*(unzipy[j+1]-unzipy[j])*(unzipx[k+1]-unzipx[k]); } } cout << ret << endl; return 0; }
AOJ 0537 Bingo
問題ページ ビンゴ | Aizu Online Judge
考えたこと
N2要素で要素の値は1以上M以下、要素の合計がSの狭義単調増加な数列が何通りあるか求めればいい。
dp[i][j][k] = (i番目までで最大の要素がjで合計がkの数列の通り数) としてDPしようとしたが遷移のうまい方法がわからず悩む。dpの要素数の時点でO(MSN2)で遷移はO(1)でできないとだめそう。累積和を持っておくDPだったり色々考えても思い浮かばない。
結局わからず解説を見ると、ループの順番をうまいことやると普通にO(MSN2)で解ける。
学び
ループの順番を頑張るとうまくDPできることがある。他の問題にも応用できそうだし覚えておきたい。
//#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 100000; //#define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; int dp[50][3010]; signed main(void) { while(true) { int n, m, s; cin >> n >> m >> s; if(!n) break; n *= n; memset(dp, 0, sizeof(dp)); dp[0][0] = 1; // 数列中の最大の要素がi FOR(i, 1, m+1) { // j番目までで合計がkのとき何通りか for(int j=n; j>=1; --j) FOR(k, i, s+1) { (dp[j][k] += dp[j-1][k-i]) %= MOD; } } cout << dp[n][s] << endl; } return 0; }
Codeforces Round #431 (Div. 2) D. Rooter's Song
問題ページ
codeforces.com
解法
まず、各ダンサーが待つ時間をスタート位置を変えるという形で処理する。(p[i], 0)からスタートするダンサーであれば(p[i], -t[i])、(0, p[i])からスタートするダンサーであれば(-t[i], p[i])からスタートすると扱うことで全てのダンサーが単位時間あたり1マス進むと処理することが出来る。
次に各ダンサーがどのダンサーと衝突するか考える。全てのダンサーは単位時間あたりにxまたはyが1増加するので最初の時点でx+yが等しいダンサーはどの時点であってもx+yは等しいといえる。したがってx+yの値が等しくないダンサーと衝突することは絶対にありえないといえる。
x+yの値によってダンサーをグループ分けし、それぞれのグループで衝突した結果どうなるか考えることにする。以下の図のように左上からy座標の大きい順に、3 4 5 1 2のダンサーが衝突しなかった場合にたどり着く最終地点が割り当てられる。x軸のダンサーをxについて昇順、y軸のダンサーをyについて降順で貪欲に割り当てていくことで衝突を考慮した最終地点が求められる。
衝突をゼッケンの交換とみなしてqueueを使う解法があるらしいが理解できてないのであとで考える（類題:PCK 蟻)
Codeforces Round #431 (Div. 2) C. From Y to Y
問題ページ
codeforces.com
考えたこと
構成ゲーっぽい。適当な文字列についてcostがどのように求められるのか考えてみる。
まず、異なる文字種が影響し合うことはなさそう。ある文字種がN個存在するときについて考えると、costはN(N-1)/2になりそう。いくら実験しても操作の順番がcostに影響することはなかったので操作の順番は関係ないと思い込む。
A[i] = i*(i-1)/2 を前計算しておき、k以下の一番大きいA[i]を貪欲に取っていくとしてみる。k=100000付近のを試してみるが文字列長は問題なさそう。logオーダーで減っていくのでは？と思いこむ。
制約を見直したらk=0が含まれている。慌てて対処して投げたら通った。
学び
貪欲に取っていくパートでkはルートのオーダーで減っていくとTLで見た。k以下の最も大きいA[i]はkのルートオーダーになるのはそれはそうっぽい。26回ルートを取るならまず問題なさそう。
Codeforces Round #431 (Div. 2) B. Tell Your World
問題ページ
Problem - B - Codeforces
考えたこと
頂点を二つに分類してそれぞれの頂点群が直線上に乗っていて各直線が平行であるかを判定すればよさそう。
まず、頂点1とiを2頂点として選ぶ。この2頂点を通る直線を一本目として考える。この直線上にない頂点が全てある別の直線上に乗っていて、2直線が平行であればYesと判定する。また、頂点1以外の頂点が一直線上に乗っていて頂点1はその直線上にない場合も頂点1を通る平行な直線を引けばよいので可能。
実装して出したらWAを出す。1indexと0indexを間違えている部分を一箇所発見したので直して出す。
WAが出る。1indexと0indexを間違えている部分をもう一箇所発見したので直して出す。
pretestが通る。システスで落ちた。1indexと0indexを間違えている部分をさらに一箇所発見したので直して出す。
AC
罠
1-indexはクソ
