■166F - Three Variables Game
構築は苦手
a+b+c=0は明らかNG
a+b+c=1は打てる手が一択なので簡単
a+b+c>=2は基本的に大きい方から小さい方に移せばいい。
1,1,0で(1,1)が選ばれたときは次のターンに支障がないように動く
■167F - Bracket Sequencing
括弧列の成立条件は(を+1,）を-1としたときに
最後まで足して0になること、途中で負にならないこと。
文字列毎に、トータルでプラスになるかマイナスになるか、
途中での最小値は幾つになるかを知らべる。
例((()ならトータル+2、最小+0
トータルの符号で右側で使うか左で使うかが決まる(上りと下り)
上り下り内で使う順番考えてシュミレーションを行う。
■168F - . (Single Dot)
この辺りは競プロを始めた辺りのABCなので印象が強い
解説を読んでも、解説動画を見てもなんでそんなことが思いつくんだ？とたまげた記憶。
実際、今解いても実装量的にはABC-Fではボスクラスだと感じる。
基本的な方針としてはbfsで行けるマス数の合計を考えればいい。
しかし、それだとマスの数が多すぎる。
なので座圧する必要がある。
座圧後に同じようにbfsを行い、到達可能マスのもとの面積を答えに足すイメージ。
難しいのは、移動不可能な部分の扱い方。
これも座圧するついでにうまいこと管理すれば良い。
移動範囲がINFになる判定は、外に壁を作っておき壁に接するマスに到達したらINFとして扱えば良い。
■169F - Knapsack for All Subsets
初参加回かな。
１：fps解放
[2,2,4]で4を作るのは
f1 = 1 + x^2
f2 = 1 + x^2
f3 = 1 + x^4として
f1f2f3 + f1f2 + f2f3 + f1f3 + f1 + f2 + f3のx^4の係数
因数分解するために1を足して
(1 + f1)*(1 + f2)*(1 + f3)-1
つまり
(2+x^2)(2+x^2)(2+x^4)のx^4の係数
２：dp
dp[i][j]:=i番目までみて、集合Tの中の部分集合Uの和がjになるような選び方の通り数。
U⊂T⊂Sとあって、Sがi番目まで全て、Tが問題でいうT、UがTの部分集合で和がjになるもの。
新しい要素Aiの追加先が三種類あるのでそのとおりに遷移させる
■170F - Pond Skater
当時はFなんて解説見ても実装できなかったのを覚えてる。
いまやどこからどう見ても拡張ダイクストラ
dp[i][j][k]:=場所(x,y)でzを向いている時と定義する
kマス水かきが出来る部分は、水かき１回に1/kのコストがかかると考え
方向転換して進む際に切り上げられると思えば良い。
doubleで扱うとどうせ誤差で死ぬので、最初からk倍しておき
方向転換した際に(x+(k-1))/k) * k + 1とすれば良い。
