2022-04-09 Slay the Spire の『レリックって必要？』実績を解除した
PAST #9: 第九回 アルゴリズム実技検定 L - 嘘つきな生徒たち を解いた。解いたときに考えたことを書く。
問題: https://atcoder.jp/contests/past202112-open/tasks/past202112_l
得点を嘘とするかしないかの 2 通りで 2^N 。嘘とする・しないの 2 つの遷移のある DP っぽく考えてみて TLE になった。あれこれ考えたあと唐突に単なる最長増加部分列 (LIS) の長さを求める問題だと気づいて TLE は解決した。
ただ A を逆順にして LIS すると WA が結構出る。 LIS としては正しいけどこの問題として正しくない例として「最下位が点 P を取る」という主張を 1 として扱うのは不可だと気づいた。各要素に上限下限をつけて 4 WA くらいまで減ったはず。
ただそこからは減らせず断念した。
解説を読むと逆順にして LIS は正解。上限下限を設けて絞るのも正解。ただ A_i - i からなる B_i に対して広義単調増加の LIS を取るようだった。うーん……。確実に増えることを保証するためにそうする……のかな……。よく分からなかった。
提出: https://atcoder.jp/contests/past202112-open/submissions/30802332 解説: https://atcoder.jp/contests/past202112-open/editorial/3070
Slay the Spire の『レリックって必要？』実績を解除した。
ディフェクトの『オールフォーワン』を軸としたデッキになった。元々はフロストオーブを軸としたものが狙いだったのだけど集中力・スロットに関するカードがまったく来なかった。代わりに『オールフォーワン』が 2 枚来た (要らない) 。意外と『フォースフィールド』が活躍した。『フォースフィールド』もコスト 0 にすれば『オールフォーワン』の対象になるのが活きた。レベル 3 のボスがタイムイーターで絶望した。レベル 3 に入ってからコスト 0 の方向からなるべく切り替えようといろいろ追加で差した。最終的にはタイムイーターでは『ホワイトノイズ』で『反響化』を引いて『切断』と『フォースフィールド』をうまく回したら勝てた。多段攻撃が 21x3 まで行ったけどなんとか耐えられた。
今日のコミット。