AB二完と冴えない結果。
No.1374 Absolute Game
解説AC。
解説を見ればその戦略が最適なことは理解できる。……が、直感的には今一つピンと来ていない。
それぞれが取れる戦略は限られている（大きい方か小さい方か、どちらかから貪欲が最適であろうと予想できる）ので、そのいくつかを適当に書いてみれば無理矢理ACすることはできた気がするが、ちゃんとやるにはどうすれば良いんだろう。
立式しようと思えば、解説のように立式するのはそう難しくないので、「とりあえず立式」案件かなぁ。
こういうゲーム系の問題だと、今一つ立式しようという気になれないけど、立式した方が分かりやすいことが多いのかも。
No.1375 Divide and Update
（今更だが）自力AC。
・配列Aに対して、l, rを選んで区間[l, r]をXに変更するという操作を行う。sum(A)を合計を最大にするのは？
という問題を考えると、Aの各要素からXを引いて、累積和を使えば解ける。
Aの要素を増やしながらこれができれば、さらに逆からYについて同様のことを行うことにより元の問題が解ける。
これは、累積和の最大値を管理・更新してしながらAの要素を追加していけば良い。
最初考えたときは、BITかセグ木かが必要な気がしたけど、そういったデータ構造を使わず累積和だけでACできたのはちょっと意外でした。
No.1378 Flattening
AGCでほぼ同じ問題が出題された。AGCでは自力ACできて良かった。
0 件のコメント:
コメントを投稿