AtCoder Regular Contest 065

2016年12月10日のAtCoderの記録。言語はRubyです。
問題はこちら：[AtCoder Regular Contest 065](http://arc065.contest.atcoder.jp/)
私の回答一覧はこちら：[自分の結果](http://arc065.contest.atcoder.jp/submissions/all?user_screen_name=Linus)

前回ABC048を余裕を持って完答できたので、「こりゃ次回からはARCのほうに参加したほうが良いな」と思ったのですが、まさかの正解無しという結果でした。苦いデビュー戦というやつですな。

#C問題

'dream' 'dreamer' 'erase' 'eraser' の4つを好きな数だけ好きな順番で並べた文字列、に当てはまるか否かを判定する問題。

```dreamer...``` という文字列があったとしても ```dream / erase...```なのか```dreamer / ...```なのか判定できない。ちょこちょことif判定すれば何とかなりそうだがあんまりスマートじゃない。
そうだ、再帰を使おう。と考えたのが間違いの元であったようだ。

```ruby
$target = gets.chomp
$frac = ["dream" , "dreamer", "erase", "eraser" ]
 
def addstr(s)
	$frac. each do |frac|
		s1 = s + frac
		if s1 == $target then
			puts "YES"
			exit
		elsif s1 == $target[0 , s1.length] then
			addstr(s1)
		end
	end
	
end
 
addstr("")
puts "NO"
```

アルゴリズム的には問題ない。addstrで次々に文字列を付け加えていって、入力文字列に一致すれば"YES"を出力してすぐに終了。最後までやっても一致しなければ、"NO"と出力する。
計算量は問題ないと判断した。一般には、文字列の候補が4つに枝分かれ→それぞれがまた4つに枝分かれ→……で4^nの指数時間かかってしまう。この問題の場合、不正解のものは枝分かれするとすぐに棄却されるので、それ以上先に進まない。問題の性質上、枝分かれは膨大にならないので、問題にはならないと考えた。
で、結果がRuntime Error。
それぞれの関数で文字列変数を使うから(メモリが制限オーバーして)アカンのかなと思い、変数をグローバル領域に出したりしても変わらず。

手元のRubyでやってみると、入力が1万文字も行かないあたりで

```
stack level too deep (SystemStackError)
```
と出てしまった。
入力の最大長は10万文字なので、このままではダメ。

[ABC036 D問題](http://abc036.contest.atcoder.jp/submissions/761133)のときも、最大で10万回の再帰をするコードを提出してるけど、このときはAcceptedなんだよなぁ。今回と以前とで何が違うのか分からない。

#D問題
頂点集合Vに対して、V上のグラフG<sub>1</sub>, G<sub>2</sub>が与えられる。Vの各頂点に対して、G<sub>1</sub>に関してもG<sub>2</sub>に関しても連結である頂点の個数を求めよ。という問題。
考えた道筋を記録しておくが、上手く行かなかったアイデアである。
最も単純に思いつくのは、以下のようなアルゴリズムである。(擬似コード)

```
for each v in V
　　幅優先か深さ優先で探索して
　　G1 上で連結である頂点の集合を求める
　　G2 上で連結である頂点の集合を求める
　　2つの頂点集合の共通部分を求める
　　共通部分の要素数を出力
end
```

しかしこれは時間をオーバーする。1回の探索にかかる時間が最悪でO(|E|)である(Eはグラフの辺)。問題条件は、|V|が最大$2×10^5$、|E|が最大$10^5$である。
[Pythonで競技プログラミングする時に知っておきたい知識](http://qiita.com/lethe2211/items/38303f4120bfd963679a)を参照すると、1秒間の計算回数はC++のような処理の速い言語でも$10^8$ぐらい。絶対に間に合わない。

しかし、グラフの連結性は対称性を持つ。例えば頂点2を調べていて、頂点2と連結している成分は2,4,6だけだとわかった場合、頂点2と連結する頂点の要素数は3である。同時に、頂点4と連結している頂点の要素数も3である。というところで計算量を削れそうだ。

```
for each v in V
　　vに関する個数が既に求まっていれば、スキップして次の頂点へ

　　幅優先か深さ優先で探索して
　　G1 上で連結である頂点の集合を求める
　　G2 上で連結である頂点の集合を求める
　　2つの頂点集合の共通部分を求める
　　共通部分の要素数を、共通部分の全要素に対して出力
end
```

ここまで考えて実装している途中に時間切れ。
そのあと書き上げたら、小さいテストケースでは通ったが、全体ではTime Limit ExceededやRuntime Errorで撃沈した。

```ruby
n,k,l = gets.split.map { |i|
	i.to_i
}
 
@neighbor1 = []
n.times do
	@neighbor1 << []
end
 
k.times do
	line = gets.split
	i = line[0].to_i
	j = line[1].to_i
 
	@neighbor1[i-1] << j-1
	@neighbor1[j-1] << i-1
end

@neighbor2 = []
n.times do
	@neighbor2 << []
end
l.times do
	line = gets.split
	i = line[0].to_i
	j = line[1].to_i
 
	@neighbor2[i-1] << j-1
	@neighbor2[j-1] << i-1
end
 
def search1(x, ren)
	for n in @neighbor1[x]
		if ren.include?(n) then
			next
		else
			ren << n
			search1(n, ren)
		end
	end
	return ren
end
def search2(x, ren)
	for n in @neighbor2[x]
		if ren.include?(n) then
			next
		else
			ren << n
			search2(n, ren)
		end
	end
	return ren
end
 
answer = []
n.times do
	answer << 0
end
0.upto(n-1) {|i|
	if answer[i] > 0 
		next # もう求まっているので、次の頂点へ
	end
	# iからの連結成分を取得
	list1 = search1(i, [i])
	list2 = search2(i, [i])
#	p list1, list2
	list = list1 & list2
	l = list.length
	list.each {|t|
		answer[t] = l
	}	
}
answer.each {|t| puts t}
```

以上。解説見てみたけど、今後どうすれば良いのか分からんな。Union-Findを定石として頭に入れておいたほうが良さそう、くらいかなぁ。