構文解析する必要はない.まず + で切れるか試し,次に * で切れるか試し,次に ^ で切れるか試す.全部ダメなら,括弧で全体が覆われていればそれを外し,そうでなければ元の文字列そのままが答になる.
n 個目までの caravan に helm を計 h 個,armor を計 a 個積んでいるとき,同様にして積める boots の個数の最大値をDP.普通に概算すると 100*500*500*500*500 とかになるが実際は caravan の大きさ制限から枝を刈ると十分に速い.
問題文が曖昧な気がするが,とにかく時間優先で処理すればOK.特に各ジョブは1時間しか要さないので面倒なことはせずに,1時間ずつループを回して処理できるジョブを処理していくとよい.
- 1PE: 問題ごとに「テストケースとテストケースの答の間には空行を挟むこと」と「テストケースの答の後に空行を出力すること」があって紛らわしい……,いずれにせよちゃんと読む.
各ノードについてそれぞれのsignalが来た時,部分木がvalidになるかを計算する.全二分木で,与えられ方が優しいので簡単なループを回すだけで木DP可能.
書いてある通りに.
- 1WA: 隣接する辺が交差してると判定されないようにしていたら,辺どうしが重なるときにも交差してないと判定されていた.はじめから問題文に忠実に判定していればこのWAは無くせたはず.