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; }
もっと問題をこなして経験値を蓄えていくぞ〜
