AOJ 2299 Tiles are Colorful
問題概要
N×Mのグリッドが与えられる。各空白マスについて上下左右を見た時、最も近いアルファベット付きマスを取り出し、同じ文字のペアが存在する場合削除する。
これを繰り返したとき最大いくつ削除できるか。
考えたこと
各文字はせいぜい0か2個しか含まれないため、そろったものから貪欲に消していけばよいことが分かる
計算時間は各マスを調べるためにO(NM)、そこから上下左右のマスを調べるためにO(logN + logM)、これを何回か繰り返すのでだいたいO(NM*(logN+logM))
（二分探索をつかわずとも愚直に上下左右を調べるのでも間に合うっぽい）
ACコード
#include <bits/stdc++.h> using namespace std; #define FOR(i,s,n) for(int i=s;i<(int)n;++i) #define REP(i,n) FOR(i,0,n) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() bool erased[510][510]; int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12); int H, W; cin >> H >> W; vector<string> f; REP(i,H){ string s; cin >> s; f.push_back(s); } int ans = 0; bool update = true; while(update){ update = false; vector<pair<int, char>> h[510], w[510]; REP(i,H){ h[i].push_back({-1, '0'}); REP(j,W){ if(f[i][j] != '.'){ //横方向に文字を見ていく h[i].push_back({j, f[i][j]}); } } h[i].push_back({INT_MAX, '0'}); } REP(j,W){ w[j].push_back({-1, '0'}); REP(i,H){ if(f[i][j] != '.'){ //縦方向に文字を見ていく w[j].push_back({i, f[i][j]}); } } w[j].push_back({INT_MAX, '0'}); } memset(erased, false, sizeof(erased)); for(int i=0; i<H; i++){ for(int j=0; j<W; j++){ if(f[i][j] == '.'){ //左右上下の文字を取得 //横方向 auto itr1 = lower_bound(all(h[i]), make_pair(j, '0')); //縦方向 auto itr2 = lower_bound(all(w[j]), make_pair(i, '0')); pair<int, char> up,left,right,down; right = *(itr1); down = *(itr2); itr1--; itr2--; left = *(itr1); up = *(itr2); if(up.second != '0'){ if(up.second == left.second){ erased[up.first][j]=true; erased[i][left.first]=true; } if(up.second == right.second){ erased[up.first][j]=true; erased[i][right.first]=true; } if(up.second == down.second){ erased[up.first][j]=true; erased[down.first][j]=true; } } if(left.second != '0'){ if(left.second == right.second){ erased[i][left.first]=true; erased[i][right.first]=true; } if(left.second == down.second){ erased[down.first][j]=true; erased[i][left.first]=true; } } if(right.second != '0'){ if(right.second == down.second){ erased[down.first][j]=true; erased[i][right.first]=true; } } } } } for(int i=0; i<H; i++){ for(int j=0; j<W; j++){ if(erased[i][j]){ ans++; f[i][j] = '.'; update = true; } } } } cout << ans << endl; return 0; }
AOJ2332 Space-Time Sugoroku Road
問題概要
1~Nのマスとサイコロがある。各マスには数字が書き込まれている。
・ が正数の時、駒を
だけ進める。
・ が負数の時、駒を
だけ戻す。
・ が0の時、サイコロを振り
のいずれかに移動する。
このとき1からNに到達するために必要なサイコロの振る回数は何回か？
考えたこと
説明文通りであるが、無限ループに気を付ける。
サイコロの振ることを重み１、マスによる移動を重み0としたときのダイクストラ法を考える。
各マスを頂点とすると各頂点から出る辺はせいぜい1か6なので十分間に合う。
最短経路を考えることでループを枝刈りできるのもうれしい。
最初、メモ化再帰で通そうとしたがsample12で落ちた。しばらく考えたが分からなかったので諦めた。（ループ判定で引っかかってそう）
ACコード
#include <bits/stdc++.h> using namespace std; #define FOR(i,s,n) for(int i=s;i<(int)n;++i) #define REP(i,n) FOR(i,0,n) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() int dist[100010][2]; int P[100010]; int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12); int N; cin >> N; REP(i,N) cin >> P[i]; REP(i,N) dist[i][0] = dist[i][1] = INT_MAX; priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q; q.push(make_pair(0, make_pair(0, 0))); dist[0][0] = 0; while(q.size()){ auto p = q.top(); q.pop(); int d = p.first, v = p.second.first; int f = p.second.second; if(dist[v][f] < d) continue; if(f){ int u = v + P[v]; if(P[u] == 0){ if(dist[u][0] > dist[v][1]){ dist[u][0] = dist[v][1]; q.push(make_pair(dist[u][0], make_pair(u, 0))); } }else{ if(dist[u][1] > dist[v][1]) { dist[u][1] = dist[v][1]; q.push(make_pair(dist[u][1], make_pair(u, 1))); } } }else{ for(int i=1; i<=6; i++){ int u = min(i+v, N-1); if(P[u] == 0){ if(dist[u][0] > dist[v][0] + 1){ dist[u][0] = dist[v][0] + 1; q.push(make_pair(dist[u][0], make_pair(u, 0))); } }else{ if(dist[u][1] > dist[v][0] + 1) { dist[u][1] = dist[v][0] + 1; q.push(make_pair(dist[u][1], make_pair(u, 1))); } } } } } cout << min(dist[N-1][0], dist[N-1][1]) << endl; return 0; }
AOJ 1249 Make a Sequence（AOJ ICPC 200）
問題リンク
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1249
問題概要
3次元空間でTic-Tac-Toe（マルバツゲーム）を行う。x座標, y座標, z座標のそれぞれの方向ベクトルについてM個以上同じ色が隣接している場合その手を打った色が勝ちとなる。
毎ターンごとにx座標とy座標の情報が与えられるので、勝敗の判定を行う。勝敗が決まらなかった場合、Drawを出力する。
LeetCode 1335. Minimum Difficulty of a Job Schedule
問題：https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
概要：配列aが与えられる. これをd分割したときの区間ごとの最大値の和の最小値を求める
考えたこと：区間分割なので「どこで区切ったか」、「どこまで区切ったのか」という情報を扱いたくなる。今回の場合、これは次のように添え字を持つことで動的計画法で実現できる。
dp[i][j] = i番目まで見て、j個の集合が存在する
次に遷移について考える。
i-1番目までを見たとき, 次の分割の番地はi
int minDifficulty(vector<int>& jobDifficulty, int d) { long dp[310][15]; for(int i=0; i<310; i++){ for(int k=0; k<15; k++){ dp[i][k] = INT_MAX; } } dp[0][0] = 0; int n = jobDifficulty.size(); for(int i=0; i<n; i++){ for(int j=i; j<n; j++){ long maxV = 0; for(int k=i; k<=j; k++){ maxV = max(maxV, (long)jobDifficulty[k]); } for(int k=d; k>0; k--){ if(dp[i][k-1] == INT_MAX) continue; dp[j+1][k] = min(dp[j+1][k], dp[i][k-1] + maxV); } } } if(dp[n][d] == INT_MAX) return -1; return dp[n][d]; }
AtCoder Beginner Contest 029 D - 1
問題リンク
atcoder.jp
考えたこと
1以上N以下の自然数に含まれる1の数を数え上げればよいためこれは桁dpで解くことができる.
状態の持ち方としては,
dp[i][j][k] := i番目までを見た時, （jはtightかどうか）1をk個もつような数字の個数
とする. なお, 桁数はせいぜい9なので, ある数字がもつ1の数も9が最大.
#include <bits/stdc++.h> int main() { cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(15); string s; cin >> s; ll dp[15][2][10]={0}; dp[0][0][0]=1; for(int i=0; i<s.size(); i++){ int num = s[i] - '0'; for(int j=0; j<2; j++){ int ma = 10; if(j == 0){ ma = num + 1; } for(int d=0; d<ma; d++){ for(int k=0; k<10; k++){ dp[i+1][j | (d != num)][k + (d == 1)] += dp[i][j][k]; } } } } int ans = 0; for(int i=0; i<10; i++){ ans += (dp[s.size()][0][i]+dp[s.size()][1][i])*i; } cout << ans << endl; return 0; }
