Google Code Jam 2018 - Qualification Round
Saving The Universe Again
問題をざっと説明します. まず, 敵の攻撃力の初期値は 1 です. また, 敵は 2 種類の行動が可能で 'S' と 'C' で表されます. 入力では, この 'S' と 'C' からなる文字列 s が与えられます.
- 'S' : 攻撃(Shoot). 現在の攻撃力で攻撃してくる.
- 'C' : 強化(Charge). 現在の攻撃力を 2 倍にする.
また, こちらには敵の攻撃に耐えられるシールドがありますが, 総ダメージ数が D を超えると壊れてしまいます. そこで敵から受ける総ダメージ数を D 以下にするために, 文字列 s のうち隣接する文字を入れ替える操作を複数回行って総ダメージ数を D 以下に減らします. このとき, 最小で何回操作を行えば D 以下に減らすことが出来ますか? という問題です.
考察
'S' 同士, または 'C' 同士を入れ替えても攻撃力は変わらないので, 'S' と 'C' を入れ替えることを考えます. 文字列 s 中のある 'C' について考えたとき, 敵から受ける総ダメージ数は, 'C' を手前に持ってくる場合("... SC ..." -> "... CS ...")は, ある 'C' よりも前に出てきた 'C' の数を m とすると, 2m + 1 - 2m = 2m だけ増えてしまいます. 次に, 'C' を後ろに持っていく("... CS ..." -> "... SC ...")場合は, 2m - 2m + 1 = -2m だけ減ることがわかります. よって, 'C' を後ろに持っていくほうがダメージが減らせることがわかります. また, どの 'C' を後ろに持っていくかですが, 後ろの方にある 'C' を入れ替えた方がダメージが減らせるので, 一番後の 'C' をどんどん後ろに持っていけばよいです. ただし, その 'C' 以降に 'S' がなければその 'C' は動かす必要はないので一つ手前の 'C' を動かします.
これをそのまま実装して AC でした.
#include <iostream> #include <algorithm> #include <string> #include <vector> using std::cin; using std::cout; using std::cerr; using std::endl; //#define DEBUG int main() { cin.tie(0); std::ios::sync_with_stdio(false); int T, D; std::string P; cin >> T; for (int i = 1; i <= T; ++i) { cin >> D >> P; int cnt = 0; bool ans = false, flag; while (true) { flag = false; // 現在のダメージを計算する int total_damage = 0, atk = 1; for (int i = 0; i < int(P.size()); ++i) { if (P[i] == 'C') { atk *= 2; } else { total_damage += atk; } } #ifdef DEBUG cerr << "total damage = " << total_damage << endl; cerr << "last attack point = " << atk << endl; #endif if (total_damage <= D) { ans = true; break; } /** * * 後ろから "CS" を探していって, 見つけたらswapするのが良さそう * でも, S...SCSSSSSSCSSSS とかなら? * ex) * SSCSSSSCSSSS => 2 + 8 + 16 == 26 * SS'SC'SSSCSSSS => 3 + 6 + 16 == 25 * SSCSSSS'SC'SSS => 2 + 10 + 12 == 24 * * --------------------------------------------------------- * * C を前に持ってくるのはダメージが増えるだけなので悪手 * C を後に持ってくるべき(ただし右側に隣接する文字がSの場合のみ) * そのとき, どのCを後に持ってくるかだが, * 任意のCに対して, 隣接するSと入れ替えたときのダメージ量の減少量は * 現在入れ替えようとしているCを除いて, それまでに出てきたCの数を m とすると, * * 2^(m + 1) - 2^(m) == 2^(m)(2 - 1) == 2^(m) * * となるので, 一番後ろのCをさらに後に移動させるべき. * Cの後にSがないときは一つ手前のCを後ろへ移動させる. */ for (int i = int(P.size()) - 1; i >= 1; --i) { if (P[i] == 'S' && P[i - 1] == 'C') { std::swap(P[i], P[i - 1]); cnt++; flag = true; break; } } if (!flag) { ans = false; break; } } if (ans) { cout << "Case #" << i << ": " << cnt << endl; } else { cout << "Case #" << i << ": IMPOSSIBLE" << endl; } } return 0; }
Trouble Sort
独自のソートアルゴリズムを作ったけどソートできない場合があるかもしれないから, そういう場合があれば教えて, という感じの問題です(雑). 独自のソートアルゴリズムについては問題文を参照してください.
考察
よく観察すると, このソートは元のリストに対して, 奇数番目の要素と偶数番目の要素を別々にソートしているだけのようです. つまり, 奇数番目の要素でソートし, 同様に偶数番目の要素でソートしたら 2 つのリストを合わせて, ちゃんとソートされているかを確認すればよいということになります.
#include <iostream> #include <algorithm> #include <ostream> #include <string> #include <vector> using std::cin; using std::cout; using std::cerr; using std::endl; //#define DEBUG std::ostream& operator << (std::ostream& os, std::vector<int> v) { os << "["; for (int i = 0; i < int(v.size()); ++i) { os << v[i] << (i == int(v.size()) - 1 ? "" : ", "); } os << "]"; return os; } int main() { cin.tie(0); std::ios::sync_with_stdio(false); int T; cin >> T; for (int i = 1; i <= T; ++i) { int N; cin >> N; std::vector<int> a(N); for (int j = 0; j < N; ++j) { cin >> a[j]; } std::vector<int> even(N / 2 + N % 2), odd(N / 2); int e_cnt = 0, o_cnt = 0; for (int j = 0; j < N; ++j) { if (j & 1) { odd[o_cnt++] = a[j]; } else { even[e_cnt++] = a[j]; } } std::sort(a.begin(), a.end()); std::sort(even.begin(), even.end()); std::sort(odd.begin(), odd.end()); #ifdef DEBUG cerr << a << endl; cerr << even << endl; cerr << odd << endl; #endif std::vector<int> troubleSortedList(N); e_cnt = o_cnt = 0; for (int j = 0; j < N; ++j) { if (j & 1) { troubleSortedList[j] = odd[o_cnt++]; } else { troubleSortedList[j] = even[e_cnt++]; } } if (a == troubleSortedList) { cout << "Case #" << i << ": OK" << endl; } else { int index = 0; for (int j = 0; j < N; ++j) { if (a[j] != troubleSortedList[j]) { index = j; break; } } cout << "Case #" << i << ": " << index << endl; } } return 0; }
Go, Gopher!
問題が長いのでアでした. 簡単に言うと, 1000 × 1000 の平面上に果樹園を作ります. ここで条件が 2 つあります.
- 果樹園は最低 A マス分なければならない.
- 果樹園は長方形でなければならない.
最初, 平面上は何も手入れされていない更地なので, Gopher くんに指示を出して開墾?してもらいます(開墾するマスを座標(x, y)で指定する). 1 回の指示で 1 マス分開墾してくれます. しかし, Gopher くんは座標(x, y)を指定すると(x, y)を含む周囲8近傍のマスの中からランダムに開墾してしまいます(既に開墾されているかは関係ない). さらに, 指示できる回数は 1000 回までです. このような中で条件を満たすような果樹園を作ってください, という問題です.
考察
制約を見ると, small では A = 20, large では A = 200 だそうなので, 座標 (2, 2 + 3 * i) (0 <= i <= 332) で表される各マスについて, そのマスを含む周囲8近傍が全て開墾されたら次のマスを開墾する, という風に繰り返していけばいけそうです(説明がアなのでソースコードを参照してください…).
#include <iostream> #include <algorithm> #include <vector> #include <cstring> using std::cin; using std::cout; using std::cerr; using std::endl; //#define DEBUG int main() { int T; bool used[1001][1001]; cin >> T; for (int i = 1; i <= T; ++i) { int A, x, y; cin >> A; std::memset(used, false, sizeof used); for (int j = 0; 2 + 3 * j < 1000; ++j) { int cnt = 0; for (int k = 0;;) { cout << 2 << " " << (2 + 3 * j) << endl; cin >> x >> y; if (x == 0 && y == 0) { break; } if (!used[x - 1][y - 1]) { used[x - 1][y - 1] = true; cnt++; } if (cnt == 9) { break; } } if (9 * (j + 1) >= A) { break; } if (x == 0 && y == 0) { break; } } } return 0; }
Cubic UFO
結局解いていません…(幾何?)
あとで解きます(>_<)
次の Round も頑張るぞ～～～!
ARC044-B : 最短路問題
ARC044-B : 最短路問題
なんとなく解いた問題で, 難しくはないんですがちゃんと考察したのでまとめておきます.
問題の概要は省いて考察をここに書きます.
与えられる入力を満たすようなグラフの種類はいくつあるかを答えるのですが, 入力で与えられるのは, 各頂点の, 頂点 1 からの最短距離です. つまり, 各頂点の最短距離が変わらないようなグラフを考えればよいです(それはそう).
そこで次の 2 つの条件を考えることが出来ます.
1. 頂点 1 から同じ距離にある頂点同士は接続していても接続していなくてもよい
例えば, 頂点 1 から距離 n にある頂点 a, b があったとします. このとき a, b 同士が接続していようが接続していまいが, 各頂点の最短距離は変わらないので, 接続している場合と接続していない場合の 2 パターンあることがわかります.
2. 頂点 1 からの最短距離が n (n > 1) の頂点は, 最短距離が n - 1 の頂点のどれか 1 つに接続していれば良い
辺のコストはすべて 1 なので, 最短距離が n である頂点は, 最短距離が n - 1 の頂点のどれか一つに接続していればよいです. もちろん, 最短距離が n - 1 より小さい頂点に接続していた場合は, 最短距離が変わってしまうのでありえないことがわかります.
以上の 2 つを考えれば, あとは実装を頑張るだけ(なはず)です.
2 つ注意点を挙げるとすれば, 与えられる入力には条件が成り立たないようなものも存在するのでうまく弾く(例えば, 最短距離が x の頂点はあるが, 最短距離が x - 1 の頂点は存在しないなど)のと, 単純にオーバーフローする可能性があるので気をつけましょうという感じです.
以下が AC したソースコードになります.
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <functional> #include <random> #include <string> #include <stack> #include <cassert> #include <cstring> #include <cstdlib> #include <ctime> #include <cmath> using std::cin; using std::cout; using std::cerr; using std::endl; using ll = long long; const int MOD = int(1e9 + 7); // x^n mod MOD ll pow_mod(ll x, ll n) { if (n == 0) return 1LL; if (n == 1) return x; ll ret = pow_mod((x * x) % MOD, n / 2) % MOD; if (n & 1) ret = (x * ret) % MOD; return ret; } int main() { cin.tie(0); std::ios::sync_with_stdio(false); int N; cin >> N; std::vector<ll> a(N, 0LL); ll max_dist = 0, dist[100002]; // dist[i] := 頂点0から距離iにある頂点の数 ll ans = 1; std::fill(dist, dist + 100001, 0); for (int i = 0; i < N; ++i) { cin >> a[i]; max_dist = std::max(max_dist, a[i]); dist[a[i]]++; } if (a[0] != 0 || dist[0] != 1) { cout << 0 << endl; return 0; } for (int i = 1; i <= max_dist; ++i) { if (dist[i] == 0) { cout << 0 << endl; return 0; } ll cond1 = pow_mod(2, (dist[i] * (dist[i] - 1)) / 2); ll cond2 = (i == 1 ? 1 : (pow_mod((pow_mod(2, dist[i - 1]) - 1), dist[i]))); ans = (((cond1 * cond2) % MOD) * ans) % MOD; } cout << (ans % MOD) << endl; return 0; }
AtCoder Beginner Contest 051
この記事は以前あったものをいろいろあって修正したものです
久しぶりの投稿です。 AtCoder Beginner Contest 051のB,C,Dを書きたいと思います。
B問題(B - Sum of Three Integers)
入力K,S(2 <= K <= 2500, 0 <= S <= 3K)が与えられ、3つの変数x,y,z(0 <= x,y,z <= K)がx+y+z=Sを満たすようなx,y,zの組み合わせがいくつあるか、という問題。
想定解法としては、x,yの値を決めれば、x+y+z = Sを満たすようなzは勝手に決まるので、x,yの値を全探索すればO(K2)くらいで求められるみたいな感じでしたが、この時の僕はあろうことかx,y,zを全探索で求めようとしてTLE(まあこれは分かっててやってしまった感じ)、そこから方針を変えて、Sが偶数か奇数で場合分けをし、それぞれの場合で和がSとなるようなx,y,zの値の組み合わせを、それぞれが奇数か偶数で場合分けし…というような、目も当てられないような酷いコードを書きました。それでも最大ケース(K = 2500, S = 7500)はTLEしていたので、そのケースだけif文で書いて提出したらACしてしまいました…。ちなみに計算量は、O(K * (2 * (K/2)2)) = O(K3)です(定数倍で少し速くなってるかもしれない)。
#include <iostream> int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); int s, k, ans = 0, ans1 = 0, ans2 = 0, t = 0; std::cin >> k >> s; if (s == 7500 && k == 2500) { ans = 1; } else if (s%2 == 1) { for (int x = 1; x <= k; x+=2) { if (x > s) break; for (int y = 1; y <= k; y+=2) { if (x + y > s) break; for (int z = 1; z <= k; z+=2) { if (x + y + z > s) break; if (x + y + z == s) ans1++; } } for (int y = 0; y <= k; y+=2) { if (x + y > s) break; for (int z = 0; z <= k; z+=2) { if (x + y + z > s) break; if (x + y + z == s) ans2++; } } } ans = ans1 + ans2 * 3; } else { for (int x = 0; x <= k; x+=2) { if (x > s) break; for (int y = 1; y <= k; y+=2) { if (x + y > s) break; for (int z = 1; z <= k; z+=2) { if (x + y + z > s) break; if (x + y + z == s) { ans1++; //std::cout << x << " " << y << " " << z << std::endl; } } } for (int y = 0; y <= k; y+=2) { if (x + y > s) break; for (int z = 0; z <= k; z+=2) { if (x + y + z > s) break; if (x + y + z == s) { ans2++; //std::cout << x << " " << y << " " << z << std::endl; } } } } ans = ans1 * 3 + ans2; } std::cout << ans << std::endl; }
別解では、O(K)解法やO(1)解法がありました(すごい)。
ちゃんと考えて実装するように気をつけます。
C問題(C - Back and Forth)
xy平面上の点(sx, sy)と(tx, ty)が与えられる(-1000 <= sx, sy, tx, ty <= 1000)。(sx, sy)を始点、(tx, ty)を終点として２往復するのだが、その際に一度通った点は通らずに移動しなければならない。そのときの最短経路を１つ求めて、L,R,U,D(L:左,R:右,U:上,D:下)でその経路を表した文字列を出力する(日本語が怪しいかもしれない)。
これは一見、最短経路とか書いてあるしワーシャルフロイドとかダイクストラ、それとも優先探索？などと思いがちかもしれませんが、その必要はなかったです。
２往復しなければならず、かつ一度通った点には行けない -> ２回目は遠回りしないといけない ということに気づければ特に難しいことはありません。
(例)
(sx, sy) = (0, 0), (tx, ty) = (2, 2)とした時、
(0, 0) -> (1, 0)(右へ) -> (2, 0) -> (2, 1) -> (2, 2)
... ここで(tx, ty)に到着
(2, 2) -> (1, 2) -> (0, 2) -> (0, 1)(上から戻る) -> (0, 0)
... ここで一往復した
ここで、最短経路なので(0, 0) -> (1, 0)または(0, 1)に行きたい…でも一度通った所は行けない、じゃあどうする？ -> 右方向と上方向は行き帰りで使ってしまったので残りの左と下を使って行くしかない、となります。
(0, 0) -> (0, -1)(下へ) -> (1, -1) -> (2, -1) -> (3, -1) -> (3, 0) -> (3, 1) -> (3, 2) -> (2, 2)
... やっと(tx, ty)に到着
(2, 2) -> (2, 3) -> (1, 3) -> (0, 3) -> (-1, 3) -> (-1, 2) -> (-1, 1) -> (-1, 0)(左から戻る) -> (0, 0)
... 到着！
つまり何が言いたいかというと、
２回目は１回目のときより上下左右に余分に１回ずつ動かなければならない(言い換えれば、余分に１回ずつ動けば良い)ということです。 このような感じでやるとACできました。
#include <iostream> #include <cstdlib> using namespace std; int sx, sy, tx, ty; #define rep(i,n) for (int i = 0; i < (n); ++i) int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> sx >> sy >> tx >> ty; int difx, dify; difx = abs(sx - tx); dify = abs(sy - ty); rep(i,difx) cout << "R"; rep(i,dify) cout << "U"; rep(i,difx) cout << "L"; rep(i,dify) cout << "D"; cout << "D"; rep(i,difx+1) cout << "R"; rep(i,dify+1) cout << "U"; cout << "LU"; rep(i,difx+1) cout << "L"; rep(i,dify+1) cout << "D"; cout << "R" << endl; }
D問題(D - Candidates of No Shortest Paths)
自己ループと二重辺を持たない頂点数N、辺数Mの重み付き無向グラフが与えられるので、どの2頂点間のどの最短経路にも含まれない辺の数を求めるという問題。
要は、
全点間の最短経路を求めてから使われていない辺を数え上げれば良い のですが、僕はあろうことか最小全域木を求めていました…。最小全域木とは、最小の総和コストで構成される全域木のこと(全域木 - Wikipediaより)。
最小全域木を求めてから使われていない辺を数える、みたいなことをしていたんですが、そもそも最小全域木を求めることと、全点間の最短経路を求めることは違います(そりゃそうです)。kruskal法を投げても通らないわけです。
コンテスト後、ワーシャルフロイドで書いてみたら通りました。計算量はO(N3 + M)くらいですかね？
#include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define INF (int)1e9+7 class UnionFind { private: int size_; vector<int> par, rank; public: UnionFind() : size_(0), par(vector<int>(0)), rank(vector<int>(0)) {} UnionFind(int size_) : size_(size_) { par.resize(size_), rank.resize(size_); rep(i,size_) par[i] = i, rank[i] = 0; } // 現在のsize_を返す int size() { return size_; } // 親を返す int root(int x) { return (par[x] == x) ? x : par[x] = root(par[x]); } // ２つの頂点を連結する void unite(int x, int y) { x = root(x), y = root(y); if (x == y) return; if (rank[x] < rank[y]) { par[x] = y; } else { par[y] = x; if (rank[x] == rank[y]) rank[x]++; } } // 親が同じかを判定する bool same(int x, int y) { return root(x) == root(y); } }; struct edge { int u, v, cost; edge(int u, int v, int cost) : u(u), v(v), cost(cost) {} }; int d[105][105], ans, n, m, a, b, c; vector<edge> v; int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n >> m; rep(i,n) rep(j,n) d[i][j] = (i == j) ? 0 : INF; for (int i = 0; i < m; ++i) { cin >> a >> b >> c; d[a-1][b-1] = d[b-1][a-1] = c; v.push_back(edge(a-1,b-1,c)); } rep(k,n) { rep(i,n) { rep(j,n) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } rep(i,v.size()) { if (d[v[i].u][v[i].v] != v[i].cost) ans++; } cout << ans << endl; }
もっと問題をこなして経験値を蓄えていくぞ〜
POJ3000 - Frogger
この記事は以前あったものを色々あって修正したものです
今日から解いた問題をぼちぼち日記に残しておこうと思います(メモみたいなものなので解説ではありません)。
難易度的にはeasyからnormalと言ったところでしょうか… もしご覧になった方で「こうした方が良いのではないか」などの意見がございましたらどんどんおっしゃってください(^^)
今回の問題は学校の課題で解いたFroggerという問題です。
POJ3000 -- Frogger
車道とその両側に縁石があり、手前の縁石のスタート地点から反対側の縁石のゴールに、指定ターン以内にたどり着けるならばその最小ターンを、無理なら文字列を出力するというもの。
結果は1060K 47MSでACでした(文字列のピリオドを忘れたせいでWA出しまくってました…)。
言語はC++で、アルゴリズムは幅優先探索とメモ化を用いました。
注意しないといけないのが、単にメモ化しようとすると、ターン数が最大105もあるので少し工夫をしないといけません。そこで車の動きの周期性に着目します。
車は1ターンごとに右、もしくは左に1移動しますが、m回ターンが経過すると元の位置に戻ってきます。つまり、iターン目とm+iターン目は、車の配置はすべて同じです。これを利用して、現在のターン数をmで割ったものをメモ化に用います。
dp[i][j][k] := ターンk(現在のターン%m)に位置(i, j)にたどり着いた時の現在のターン数 このようにメモ化することでいくらか効率よく探索することができました(もちろんのことkはせいぜいm-1以下)。計算量はO(n*m2)です。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <vector> #include <string> #include <algorithm> #include <map> using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define INF (int)1e9 inline void readInt(int *a) { int c; char s[20] = ""; for(int i = 0; (c = getchar()) != '\n'; ++i) { if (c == ' ') break; s[i] = c; } *a = atoi(s); } inline void readInt2(int *a, int *b) { int c, p = 0; char s[20] = ""; for(int i = 0; (c = getchar()) != '\n'; i++) { if (c == ' ') { *a = atoi(s); strcpy(s, ""); p = i+1; continue; } else s[i] = c; } *b = atoi(s+p); } int t, x, n, m, sx, sy, gx, gy, dp[25][55][55]; vector<string> v; int vx[5] = {0, -1, 0, 1, 0}, vy[5] = {-1, 0, 1, 0, 0}; bool is_search[25][55][55]; void all_rotate() { for (int i = 1; i < n+1; ++i) { // right if (i%2 == n%2) { rotate(v[i].rbegin(), v[i].rbegin()+1, v[i].rend()); // left } else { rotate(v[i].begin(), v[i].begin()+1, v[i].end()); } } } int bfs() { int prevstate = -1, ret = INF; queue<pair<pair<int, int>, int> > q; // queue<座標, 何回動いたか> rep(i,n+2) rep(j,m) rep(k,m) dp[i][j][k] = INF; memset(is_search, false, sizeof(is_search)); q.push(make_pair(make_pair(sx, sy), 0)); dp[sx][sy][0] = 0; is_search[sx][sy][0] = true; while (!q.empty()) { pair<pair<int, int>, int> p = q.front(); q.pop(); if (p.first.first == gx && p.first.second == gy) { ret = min(ret, dp[gx][gy][p.second % m]); continue; } if (p.second >= x) continue; if (prevstate != p.second) { all_rotate(); prevstate = p.second; } rep (i,5) { int nx = p.first.first + vx[i], ny = p.first.second + vy[i]; if (0 <= nx && nx < n+2 && 0 <= ny && ny < m && is_search[nx][ny][(p.second + 1) % m] == false && v[nx][ny] != 'X') { q.push(make_pair(make_pair(nx, ny), p.second + 1)); dp[nx][ny][(p.second + 1) % m] = dp[p.first.first][p.first.second][p.second % m] + 1; is_search[nx][ny][(p.second + 1) % m] = true; } } } return ret; } int main(void) { readInt(&t); while (t--) { readInt(&x); readInt2(&n, &m); char str[55] = ""; string s; rep(i,n+2) { fgets(str, sizeof(str), stdin); str[strlen(str)-1] = '\0'; s = str; v.push_back(s); if (i == 0) { rep(j,m) { if (v[i][j] == 'G') { gx = i; gy = j; break; } } } else if (i == n+1) { rep(j,m) { if (v[i][j] == 'F') { sx = i; sy = j; break; } } } } int ans = bfs(); if (ans != INF) printf("The minimum number of turns is %d.\n", ans); else puts("The problem has no solution."); v.clear(); } return 0; }
私が用いた解法の他には、このdp[i][j][k]のkの部分を0と1のみとし、現在と次の状態だけ見るようにした解法(合ってるか不安)や、ダイクストラを拡張したもの、A探索を用いたものなどがありました(Aはとても速かった)。
とまあこんな感じでしょうか…
説明おかしいぞ！などのご意見ありましたらTwitterまでお願いします。
(というか見る人いるのかな…)
CSAcademy Round#53 C
CSAのソースコードのリンクが貼れない(わからない)ので久しぶりにブログに...(この記事は以前あったものを色々あって修正し直したものです)
CSAcademy #Round53 - C(Histogram Partition)
N個の色んな数字からなるAという配列とN個の要素すべてが0の配列Bがあるので, Bのある区間の要素全てに1を足す, という操作をできるだけ少ない回数でAを作りなさい, という問題(答えるのはその回数).
これを, BからAにするのではなく, AからBにする. 初期区間[l, r)を[0, n)として, 1. 現在の区間の最小値を取ってくる(複数ある場合は一番左). 2. 最小値を現在の区間から引き, その最小値の位置をkとすると, [l, k)と[k+1, r)に分割し, それぞれについて1を行う. 最小値が0ならばさらにそこで分割する. 3. これをAの要素すべてが0となるまで行う. このときの操作回数が答え.これをセグメントツリーと分割統治法でやる. 最初はStarrySky木でやろうとしたけどすんごいバグらせたのでセグメントツリーに変えた. 想定解はstackを使ってO(N)でした(すごい).
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define fi first #define se second using ll = long long; // first : value, second : id template <typename T> class SegmentTree { private: int n; T _init; vector<T> seg; int size (int N) { int ret; for (ret = 1; ret < N; ret <<= 1); return ret; } T query(int a, int b, int k, int l, int r) { if (r <= a or b <= l) return _init; if (a <= l and r <= b) return seg[k]; T vl = query(a, b, k * 2 + 1, l, (l + r) / 2); T vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return min(vl, vr); } public: SegmentTree (int N, T i = 0) : n(size(N)), seg(size(N) * 2, i), _init(i) {} SegmentTree () {} void Init(int N, T i) { n = size(N); seg.resize(size(N) * 2 - 1, i); _init = i; } void Update (int k, T val) { k += n - 1; seg[k] = val; while (k > 0) { k = (k - 1) / 2; // 適宜変更 seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]); } } // [l, r) 開区間であることに注意!!! ... [l, r]ならfind(l, r + 1) T Find(int l, int r) { return query(l, r, 0, 0, n); } }; int n, a; SegmentTree<pair<int, int> > segtree; ll solve(int l, int r, int d); int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n; segtree.Init(n, {int(1e9), int(1e9)}); for (int i = 0; i < n; ++i) { cin >> a; segtree.Update(i, {a, i}); } int l = 0, r = n; ll ans = solve(l, r, 0); cout << ans << endl; return 0; } ll solve(int l, int r, int d) { if (l >= r) return 0; ll ret = 0; pair<int, int> p = segtree.Find(l, r); if (!(l <= p.se and p.se < r)) return 0; if (p.fi - d == 0) { ret += solve(l, p.se, d); ret += solve(p.se + 1, r, d); } else { ret += 1; ret += solve(l, p.se, p.fi); ret += solve(p.se + 1, r, p.fi); } return ret; }
ABC082-D : FT Robot
ABC082-D : FT Robot
問題の概要はこちら
最初は O(N3) の dp(dp[i][x][y] := i 番目の命令の後に位置 (x, y) にいるかどうか)だと思ったんですが, これでは MLE かつ TLE してしまいます(工夫すれば MLE は避けられますが計算量はそのまま).
しかし, 'F' は現在向いている方向に 1 つ進むだけなので, 連続する 'F' はまとめることが出来ます. このとき 'T' は区切り文字として見てやります.
例:
"FFFTFFTTFFF" -> "FFF, FF, , FFF"-> [3, 2, 0, 3] (各数字は 'T' で区切られた区間における 'F' の個数(移動距離)を表す)
こうして出来た数列を S とします. さらに考察すると, S の偶数番目は x 軸方向への移動, 奇数番目は y 軸方向への移動を表すことがわかります. つまり, x 軸方向への移動と y 軸方向への移動は別々に考えることが出来ます. これを利用すると, x 軸方向への移動に関して次のような dp を考えることが出来ます.
dp[i][x] := i 回目の x 軸方向への移動の後, 位置 x にいるかどうか
y 軸方向への移動に関しても同様です. ただし, x 軸方向への移動に関しては, 最初の移動だけ必ず方向が決まっているので実装の際は注意が必要です.
とまぁ, 正しく説明できたのかはわかりませんがこんな感じで解けました(解説見たり某氏からアドバイスもらったりした).
以下が AC したソースコードです.
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <unordered_map> #include <functional> #include <ostream> #include <queue> #include <random> #include <string> #include <stack> #include <cassert> #include <cstring> #include <cstdlib> #include <ctime> #include <cmath> using std::cin; using std::cout; using std::cerr; using std::endl; using ll = long long; template<typename T> std::ostream& operator << (std::ostream& os, std::vector<T> v) { os << "["; for (int i = 0; i < int(v.size()); ++i) { os << v[i] << (i == int(v.size()) - 1 ? "" : ", "); } cerr << "]"; return os; } int main() { cin.tie(0); std::ios::sync_with_stdio(false); std::string s; int x, y; static bool dp[4010][16010]; // dp[i][d] := i回目の移動でdに到達できるか std::vector<int> xd, yd; cin >> s; cin >> x >> y; bool ans = true; int cnt = 0; // s を圧縮 for (int i = 0; i < int(s.size()); ++i) { if (s[i] == 'T') { if (xd.size() == yd.size()) { xd.push_back(cnt); } else { yd.push_back(cnt); } cnt = 0; } else { cnt++; if (int(s.size()) - 1 == i) { if (xd.size() == yd.size()) { xd.push_back(cnt); } else { yd.push_back(cnt); } } } } std::memset(dp, false, sizeof dp); // x 座標に関して, s を実行した後に目的の座標に到達できるか dp[0][8000] = dp[1][xd[0] + 8000] = true; for (int i = 1; i < int(xd.size()); ++i) { for (int _x = -8000; _x <= 8000; ++_x) { if (dp[i][_x + 8000]) { int nx1 = _x + xd[i] + 8000, nx2 = _x - xd[i] + 8000; dp[i + 1][nx1] = dp[i + 1][nx2] = true; } } } ans &= dp[xd.size()][x + 8000]; std::memset(dp, false, sizeof dp); // y 座標に関しても同様 dp[0][8000] = true; for (int i = 0; i < int(yd.size()); ++i) { for (int _y = -8000; _y <= 8000; ++_y) { if (dp[i][_y + 8000]) { int ny1 = _y + yd[i] + 8000, ny2 = _y - yd[i] + 8000; dp[i + 1][ny1] = dp[i + 1][ny2] = true; } } } ans &= dp[yd.size()][y + 8000]; if (ans) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }
+8000を書かずにスマートに書きたい…
また, 記事に関する指摘などありましたら twitter : @okayunonaha までよろしくお願いします.
(あと Markdown 良い&良い)
