CODE QUEST Normal, Extra 全問解説
問題
割と面白かったです。
毒沼ノ試練・超毒沼ノ試練
概要：フィールドを勇者が歩いて魔王までたどり着く。始め勇者はHPが36であり、魔王にたどり着くときにはHP50以上である必要がある。フィールドには、死神・毒の沼・回復エリアの3つがある。勇者は4近傍に移動可能であり、毒の沼ではHP--, 回復エリアではHP++である。死神にあたってはならない。このような操作列を構成せよ。
解法：chokudaiサーチすると2分くらいで解が見つかる。
圧縮ノ試練・超圧縮ノ試練
概要：ag?からなる文字列が与えられる。?はaかgのどちらか好きな方に変更することを想定する。agからなる二値文字列について、aaaaaはa5に、gggggはg5に、aggaggaggは(agg)3のように圧縮できる。文字列を最短に圧縮せよ。
解法：区間DPで厳密解が求まりそうだが、ちょっとサボって全探索＋目でぐっと睨むをやった。
連鎖ノ試練・超連鎖ノ試練
概要：最長しりとり問題を解け。
解法：実は最長しりとりは求められていなくて、DFSで適当に1分回すと求まる。日本語つらいのでpythonでやる。
狙撃ノ試練・超狙撃ノ試練
概要：マッチしてはいけない文字列集合とマッチすべき文字列集合が与えられるので、それを満たす正規表現を作れ。
解法：Easyは普通にやる。Hardは「かつ」のパターンを知っていますか問題。
