POH6 霧島ミッション

paiza.jp

動的計画法で解いてるのが多いけど、Union-Find木でといた。
今回のPOHは回文よりも、こっちのがコードゴルフ的にも解法のアプローチ的にもいろいろありそうで好き。

class UnionFind < Hash
  def initialize
    super do |hash,key|
      hash[key] = key
    end
  end
  def union(i,j)
    self[parent(i)] = self[parent(j)]
  end
  def parent(k)
    if k == self[k]
      k
    else
      self[k] = parent(self[k])
    end
  end
  def same?(i,j)
    parent(i) == parent(j)
  end
end

tree = UnionFind.new

n = gets.to_i
map = gets.split.map(&:to_i)
n.times do |i|
  j = i + map[i]
  tree.union(i,j)
end

m = gets.to_i
m.times do
  i = gets.to_i
  puts tree.same?(i,n-1) ? "Yes" : "No"
end

珍しくC++版も書いてみた。昔入門書よんだけどunion予約語だって忘れてた。

#include <iostream>
using namespace std;

#define N 101
#define RANGE(x,l,u) ((x)>=l && (x)<=u)

int group[N];
int parent(int i){
    return i == group[i] ? i : group[i] = parent(group[i]);
}
void merge(int i, int j){
    group[parent(i)] = parent(j);
}
bool same(int i,int j){
    return parent(i) == parent(j);
}

int main(void){
    int n, m, t, q, i;
    for(i = 0; i < N; i++){
        group[i] = i;
    }
    cin >> n;
    for(i = 0; i < n; i++){
        cin >> t;
        if(RANGE(t+i,0,n-1)) merge(i, t + i);
    }
    cin >> m;
    for(i = 0; i < m; i++){
        cin >> q;
        cout << (same(q,n-1) ? "Yes" : "No") << endl;
    }
    return 0;
}