最終更新: 2020-10-29T15:09+0900
解説 PDF で考え違いを教えてもらおうと思ったら解説動画しかなくて、うんまあ、じゃあいいや。(追記) 13日の現在はPDFもあるみたい。
これを読んでも間違っているとされている定義のどこに問題があるのかわからんのだよね。果たしてそれで解けるものか。>「競プロでよくある「バランスのとれた括弧列」の定義が壊れがちな話 - notブログ」
正規表現の ? を * に変えたことで、AC は増えたけどまだ WA がある。
こういう生成スクリプトでテストした結果、最初の提出で使用した正規表現パターンに問題が見つかった。
def puts s
re = /(?<p>\(\g<p>?\))/ # バグあり。提出 #13147757 より。
re = /(?<p>\(\g<p>*\))/ # 意図通り。提出 #13156522 より。
t = s.gsub(re,'')
print "#{t.empty?}:\t#{s}\t#{t}\n"
end
L,R = '('*5,')'*5
10.times{
puts L+((L+R).chars.shuffle.join(''))+R
}
LR = '()'
10.times{
puts 10.times.inject(''){|s,| s.insert(rand(s.size+1),LR) }
}
そうするともう、提出したスクリプトは完全に自分の意図通りに動作しているはずなんだけど、WA がある。書き間違いではなく、考え違いがある。
)( 型の s を連結する順番によって結果が変わる。)))( と )((( の２つの s があるとき、連結のしかたによって )))((( が残る場合と )( が残る場合に分かれる。)( を残した方が 'Yes' と答えられる確率が高くなる。
)( 型の文字列が１つだけのときに必ず No と答えてしまいそう。今現在 Ruby で一番速い提出は 498 ms だ。>すべての提出 - AtCoder Beginner Contest 167
再帰ありの正規表現(※矛盾した表現)を使ってる時点で勝ち目はない。左括弧の数が負になれないのに気をつけながら、左括弧と右括弧を対消滅させながら、左括弧と右括弧がいくつ残るかを数えればいいんだろうけども。
しかたない、省メモリを売りにしていこう。>すべての提出 - AtCoder Beginner Contest 167
ソートを必要としてないあたりで(※)ちょっとは有利を得てもよさそうなもんなんだけど、トップの提出はソート対象を )( 型に限るなどしてる。※ループ内で２要素のソートもあかんか？
( 型の文字列を最優先に、)( 型のうち ( 優位のものを優先的に、最後に ) 型を、という感じで連結していくのがストレートな解答らしい。
３つの型の文字列を統一的にソートすることもできるし、)( 型だけソートしてもいい。
自分はどれもソートしてないんだけど、)( 型の中から１番目と２番目に条件のいい文字列をピックアップするための比較演算()( 型の文字列１つにつき１～２回)が重くてソートした方が速い。
(ゴルフ勢を除けば)わりと短くてそこそこ省メモリで今のところ Ruby で一番速い。すべては正規表現エンジンとそれを使う gsub のちから。
やってる内容は最初の AC と変わらない。入力をがばっとひとまとめに処理するようにしたのと、最小２要素を取り出すのに一度全体を配列に蓄えてから min メソッドを使うようにしただけ。