10月4日の精進 - BsBsこうしょう

AOJ-ICPCの記録が復旧した（そして投げてたコメントが消された）

再AC。いい感じの証明が見つからなくて1日以上かかった。

構文解析はオマケで、本編は変数(R, C, S)の3元1次連立方程式にどう対応するか？　という部分がメイン。普通に解くと掃き出し法が必要になるなどややこしいことになりかねないが、解集合(R, C, S)が 1<= R, C, S <= 20を保証しているので全探索でも十分なんとかなる。

問題はこの連立方程式の解が一意に定まらないのである行ではインデントが分からないが、別の行では元の文字列と括弧の数が一致しているなどして一意に定まってしまうケース。これを解決するのは一見とても難しいように見えるが、実は上の全探索の結果を保持しておくだけで大丈夫だ。

Qのある行では成り立たないが別の行では成り立つひとつの解（の候補）(R, C, S)について考える。これは先ほどの条件よりPのすべての行で成り立った結果だ。したがって十分条件を満たしているため、これらの解の候補ではじき出されたインデント数がすべて一致していれば問題がないということがわかる。

当然すべての括弧が閉じているケースや最初の行では解は0なのでその点だけに注意。

ｽﾀｲﾘｯｼｭ!!!　いや言いたかっただけやろこれ。この問題文から"Stylish"と名付けられる人のセンスが大変疑わしい。ICPCでは（特にAsia-Resional）このように作問者のネーミングセンスが逸脱していると感じられる問題が散見される。

解説AC。下の解説を主に参考にした。

自力ではbitDPということ以外何も分からず。解説にすべて書いてあるので省略するがリンク先のやり方だと場合分けの必要がなくなるためエレガントだ。優秀な競プロerは条件をまとめ、コードを簡略化することが上手いということがうかがわれる。

再AC。個数制限なしナップザックの再発明をしていたので時間がかかった。

最初に自力ACしたときはとても感動した記憶がある。ICPC国内予選の国内予選らしさを、最大限活かした問題のひとつのように思う。