AtCoder Beginner Contest 224

　Gまで七完。二桁順位は嬉しい。

コンテストへのリンク

コンテスト後のツイート

F sample1のとき、1は千の桁一回、百の桁一回、十の桁二回、一の桁四回。これを一般化する感じで。
G 期待値の式を変形すると「T-x以上のときはA支払う」という戦略のときの値は計算できる。このxで三分探索。
H フローかな？　と思ったがグラフが作れず終了。フローという直感は正しかったのかな。

— titia (@titia_til) October 23, 2021

H - Security Camera 2

　解説放送を見てAC。

　ちゃんと理解はできていないけれど、双対を取ると簡単な問題に帰着される場合があることは分かった。

　今回は、

・フローを使いそう→だけどそのままの問題だと上手くいかない→双対を取ってみよう

　くらいな感じで良いのかな。

　双対問題が何になるかを考えるところは難しい。けれど、コストと容量が、最大と最小が入れ替わるといったあたりを考えて、あとはsampleが合うようにごちゃごちゃやる……くらいの気持ちで良いか。

　ちゃんと立式して、正確に双対問題を記述できる力もあれば良いのだろうけど、コンテスト中にやるのは厳しそう。資料とか見ながら時間をかければ、自力でやることはできそうな気もするし（本当？）。