ATC 001 B Union Find
人間は愚か。えぬわいです。
Union-find木の講座用の問題らしい。
Union-Find木とは
- グループの併合と判定ができるアルゴリズム
- 併合するのは、グループ同士、判定できるのは、ノード。つまり、グループは木で表される。
初期化
はじめに N 個のノードを用意する。はじめは、辺はない。
併合
片方の木の根からもう片方の木の根に接続する。
判定
それぞれのノードの根を辿り、同じノードだと同じグループ。違かったら別のグループ。
木のランク
ここでは、木を構成する最大段数を意味する。
以下実装。
MAX_N = 100000 par = [0 for i in range(MAX_N)] # par[i] は、ノード i の親ノードの番号 rank = [0 for i in range(MAX_N)] # rank: ノード単体の時が 0 def init(n): global par, rank for i in range(n): par[i] = i # 親は自分自身 rank[i] = 0 # 単体のとき、rank は 0 # 判定: ノード x の根を求める def find(x): global par if par[x] == x: # 根のノードは自分自身が親 return x # return find(par[x]) この場合、縦に連なる場合で最悪ケースになるので改良する else: par[x] = find(par[x]) # 辿ったノードを根に付け替える return par[x] # 併合: ノード x と ノード y を同じグループにする。考えとしては、根を見つけてつなぐ。 def unite(x, y): global rank, par root_x = find(x) root_y = find(y) if root_x == root_y: # そもそも同じグループだった return if rank[root_x] < rank[root_y]: par[root_x] = root_y # ランクの大きい方の根に小さい方の木の根をつなぐ elif rank[root_y] < rank[root_x]: par[root_y] = root_x else: par[root_y] = x rank[root_x] += 1 # ランクが同じ時だけランクが増える def same(x, y): return find(x) == find(y) N, Q = map(int, input().split()) init(N) for i in range(Q): p, a, b = map(int, input().split()) if p == 0: unite(a, b) else: print('Yes' if same(a, b) else 'No')
前蟻本読んだ時より、すんなり入ってきた感じがする。理解深まった感がある。 あと、同じATCの問題に、フーリエ変換の問題があって面白そうだなと思った。(やってない)周波数特性求めるのにしか使ってないので、現実的な問題に即して使えるんだなぁという感じがした。あとでやりたい。
ABC 085 B Kagami MochiとABC 091 B Two Colors Card Game
setとmapを使う問題。
c++で set と map を使ったことがなかったので、調べてやってみる。
#include <cstdio> #include <set> using namespace std; // auto は型推論 int D[100], N; int main() { scanf("%d", &N); set<int> st; int d; for (int i = 0; i < N; i++) { scanf("%d", &d); st.insert(d); } // C++ での、何かの大きさを参照するときは、size printf("%lu\n", st.size()); return 0; }
覚えるべきは、
#include<set> std::set<class> var; var.insert(value); var.size();
らへん。
#include <iostream> #include <map> #include <algorithm> using namespace std; int N, M; int main() { map<string, int> mp1; cin >> N; string s; for (int i = 0; i < N; i++) { cin >> s; mp1[s]++; } cin >> M; string t; map<string, int> mp2; for (int i = 0; i < M; i++) { cin >> t; mp2[t]++; } int ans = 0; for (auto i = mp1.begin(); i != mp1.end(); i++) { ans = max(ans, mp1[i->first]-mp2[i->first]); } cout << ans << endl; return 0; }
こっちの覚えるべき点は、
#include <map> map<class1, class2> mp; mp[key]; // 参照
らへんかな。
DP終わってないけど、少し飽きたので、先に進みます。明日は、Union-find木の問題やります。
DPのメモ
個人的なDPのメモ。
DPでだいたい最後にdp[0][K]みたいな感じで、0 添字で参照してるので、これをdp[N][K]みたいに書けるようする。というのが目的。
単純なナップザックの問題だと、dpテーブルの添字が何を表しているのか、読み取りづらい。結果的に、漸化式を作るときに混乱しがち。これを回避するために、今一度、再帰から考える。
はじめに、蟻本にも載ってるナップザックの再帰関数。
def rec1(pos, W): if pos == N: return 0 ans = rec1(pos+1, W) if W-w[pos] >= 0: ans = max(ans, rec1(pos+1, W-w[pos])+v[pos]) return ans
これは最終的に、rec1(0, K)みたいに呼び出すことによって、解を得ている。意味としては、0 から N-1 までの荷物から最大価値を計算する というようになっている。しかも、実質、rec(N-1, ...) から呼び出されているので、わかりにくい。
そして、これをrec2(N, K)のように呼び出したいとして、書き直してみる。
def rec2(pos, W): if pos == 0: return 0 ans = rec2(pos-1, W) if W-w[pos-1] >= 0: ans = max(ans, rec2(pos-1, W-w[pos-1])+v[pos-1]) return ans
こんな感じになる。これで、rec2(N, K)として同じ解を得ることができる。比較してみると、配列(リスト)を参照する数字が微妙に違ってくることがわかる。
この関数の意味としては、0 から N-1 までの荷物から最大価値を計算する で上記と同じだが、Nという変わり得る情報が、呼び出しのときに残っているのでわかりやすいと思う(個人の見解)。
DPテーブルを追う時も、i が上がっていく方が考えやすいと思うし、積極的に、下の方の再帰をもとにして、DPを組み立てていきたい。そういうところを実感した点で、自分で書いて文字で説明するかいはあったかなと思う。
aximum-Cup 2018 D Many Go Round(3)
結局こんな感じのDPを書いた。
INF = 10**9+7 def rec(pos, j): if pos == N: if j == L: return 0 return INF # pos 番目を使わない ans = rec(pos+1, j) ans = min(ans, rec(pos+1, (j+a[pos])%M)+(j+a[pos])//M) return ans ans = rec(0, 0) print(ans) print('Yes') if ans < X else print('No')
これをC++に移して、ACした。
#include <cstdio> #include <algorithm> using namespace std; int N, M, L, X; int a[10000]; int dp[10001][1001]; #define INF 10e6+7; int main() { scanf("%d %d %d %d", &N, &M, &L, &X); for (int i = 0; i < N; i++) { scanf("%d", &a[i]); } for (int i = 0; i <= N; i++) { for (int j = 0; j < M; j++) { dp[i][j] = INF; } } dp[N][L] = 0; for (int i = N-1; i > -1; i--) { for (int j = 0; j < M; j++) { dp[i][j] = min(dp[i+1][j], dp[i+1][(j+a[i])%M]+(j+a[i])/M); } } if (dp[0][0] < X) { puts("Yes"); } else { puts("No"); } return 0; }
ACできた。ヤッター。
Maximum-Cup 2018 D Many Go Round(2)
前回の続き
解答通りに、dp[i][j] := i番目までの燃料タンクを使って番号jの休憩所に止まるための周回の最小回数で再帰関数を作ってみる。
INF = 10**9+7
def rec(pos, j):
if pos == -1:
if j == L:
return 0
return INF
# pos 番目を使わない
ans = rec(pos-1, j)
ans = min(ans, rec(pos-1, (j+a[pos])%M)+(j+a[pos])//M)
return ans
ans = rec(N-1, 0)
print(ans)
print('Yes') if ans < X else print('No')
こっからよくわかんないんだけど、DPに移せない。なんでなんだろうなぁ。明日またやります。
Maximum-Cup 2018 D Many Go Round(1)
ひとりぼっちの〇〇生活のカコちゃんがぼっちーの友達になりましたね。えぬわいです。
続き。
難しくなってきたなぁという気持ち。
1 日でなんとかするのは、きつい時期なのかなと。
DPを書く前に普通に再帰関数だけ書いてみてみる。
N, M, L, X = map(int, input().split()) a = [int(i) for i in input().split()] def rec(pos, w): if pos == N: if w == 0: return True return False ans = rec(pos+1, w) if w-a[pos] >= 0: ans = ans or rec(pos+1, w-a[pos]) return ans sw = False for i in range(X-1): if rec(0, i*M+L): print('Yes', i*M+L) break else: print('No')
厳しいぜ。DPした時の計算量は、全然間に合わない。ちょろっと解答を見たんだけど、どうやら、O(NM)に落とせるらしい。明日は、O(NM)に落として書いてみる。
勉強は、集中力と時間の確保！！！
ARC 057 B 高橋君ゲーム
おはやー！(天下ハナビ)。えぬわいです。
続きです。
とりあえず、問題通り、再帰関数を書いてみる。
書いてみる。（ここでバグ見つけて無限に時間かかった）
とりあえず、今日は、DPにできそうな再帰関数。
N, K = map(int, input().split()) a = [] for i in range(N): a.append(int(input())) def rec(pos, rest, yesterday): """ 機嫌の良い日の最大値を返す """ if pos == N: if rest == 0: return 0 return -100000 ans = 0 for i in range(min(a[pos], rest)+1): today = (K-rest+i)/sum(a[:pos+1]) if today > yesterday: ans = max(ans, rec(pos+1, rest-i, today)+1) else: ans = max(ans, rec(pos+1, rest-i, today)) return ans print(rec(0, K, 0)) ```` この問題では、N 日までに、K 勝しないといけないということに気づかなくて、バグってた。 丁度、K 勝してない時も、普通に返してた。完全に読解ミスです。本当にありがとうございました。 ちなみに、これは、DPにすると、`O(N*K*sum(A))`になるので、時間制限オーバー。 別のDPを考える必要がある。 それは、また明日の記事で。 大学行ってきます。 追記: 解答読んだけど、普通にムズいっすね。 見方を変えるDPきついな〜と思いました。 ちょっとまだわかんない部分あるんで、また後日解こうと思う。 別の再帰関数で書こうとしたけど、よくわからなかった。理解力ぅ、ですかね。 めげずに頑張ります。
