2016年12月10日のAtCoderの記録。言語はRubyです。
問題はこちら：AtCoder Regular Contest 065
私の回答一覧はこちら：自分の結果
前回ABC048を余裕を持って完答できたので、「こりゃ次回からはARCのほうに参加したほうが良いな」と思ったのですが、まさかの正解無しという結果でした。苦いデビュー戦というやつですな。
C問題
'dream' 'dreamer' 'erase' 'eraser' の4つを好きな数だけ好きな順番で並べた文字列、に当てはまるか否かを判定する問題。
dreamer... という文字列があったとしても dream / erase...なのかdreamer / ...なのか判定できない。ちょこちょことif判定すれば何とかなりそうだがあんまりスマートじゃない。
そうだ、再帰を使おう。と考えたのが間違いの元であったようだ。
$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問題のときも、最大で10万回の再帰をするコードを提出してるけど、このときはAcceptedなんだよなぁ。今回と以前とで何が違うのか分からない。
D問題
頂点集合Vに対して、V上のグラフG1, G2が与えられる。Vの各頂点に対して、G1に関してもG2に関しても連結である頂点の個数を求めよ。という問題。
考えた道筋を記録しておくが、上手く行かなかったアイデアである。
最も単純に思いつくのは、以下のようなアルゴリズムである。(擬似コード)
for each v in V
幅優先か深さ優先で探索して
G1 上で連結である頂点の集合を求める
G2 上で連結である頂点の集合を求める
2つの頂点集合の共通部分を求める
共通部分の要素数を出力
end
しかしこれは時間をオーバーする。1回の探索にかかる時間が最悪でO(|E|)である(Eはグラフの辺)。問題条件は、|V|が最大$2×10^5$、|E|が最大$10^5$である。
Pythonで競技プログラミングする時に知っておきたい知識を参照すると、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で撃沈した。
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を定石として頭に入れておいたほうが良さそう、くらいかなぁ。