-
masashinakata
- 474
- 0
- 0
- 0
-
- いいね！0
olphe
@_olphe
C、'(' -> ')'の数と')' -> '('の数はわかる。また、各変更は'(' - ')'が初めて最小値を取るところ前後で使う、使わないが別れる。 全体が条件を満たすように気を付けつつDPをして通り数を求める
2018-02-15 02:08:38
olphe
@_olphe
D、葉の数についての重心的なものを求めて、プライオリティーキュー並べればいいんだけど前半部分が分からなかった(にぶたん的に求められるだろうか)
2018-02-15 02:09:29
けんちょん
@drken1215
CSA 069 DIV2 A: うむ B: 一度でも下がる部分があったらそれを含む最大の非増加箇所をflipするしかない。元々全体が非減少だったらごにょごにょ C: dp[どこまで見たか][操作後の '(' の数 - ')' の数] = 操作回数の最小値、いわゆる最短路と数え上げを同時にやるDPなのん！ E: 続く
2018-02-15 02:10:27
tomerun
@tomerun
「再帰」でググったら「もしかして：再帰」が出てくるの、なんか悪ノリ感を感じてしまう（再帰とググる人は再帰がなんなのか知らないだろうのに分かってる人向けの冗談を表示してるところ）。細かいことを気にしすぎだとは思うが
2018-02-15 02:10:35
こうきやまぐち
@Ymgch_K
@TangentDay 僕は多分なにかを勘違いしているのだと思うんですが、Dって奇数次の点を適当に出力するだけじゃなにがまずいんですか？（辺の重複がダメなのかと思ってオイラー閉路作ってから切るやつもやりましたが同じケースで落ちました）
2018-02-15 02:10:36
agw
@masashinakata
Bは、通常ならば例えば「辞書順最小の対を表示する」だけ求めるところをついでに組み合わせ数を求めてきたのでC相当。Cは通常ならば「最小のフリップ回数」だけ求めるところを「最小のフリップ回数とその組み合わせ数」を求めてきたところでD相当なように思う
2018-02-15 02:11:13
けんちょん
@drken1215
E: 解けてよかったのん！！！観察として、一番上の段を乗せるときに3段以上下の順序にはまったく影響を受けない。このことからDPの状態としてありうる状態を絞り込む。結局最後は、2×2の行列累乗に帰着した。
2018-02-15 02:11:50