ABCFの4完。なんか自分にとって嫌らしい問題ばかりで楽しめなかった。結果も悪かった。E問題では誤差で死んでることに気づかず4WAという醜態を晒した。
A - Online Shopping
これB問題でしょ。intに収まるかだけ確認。
B - Glass and Mug
面白い設定か短時間ではわからない。何も考えず言われた通りに実装するしかない。
C - T-shirts
洗濯する日が来た時点で、状況は初日に戻る。つまり、1と2を数えておいて0が来たら何枚必要か求めてそれの最大値が答え。購入する枚数は、まず2の個数だけ購入する必要があり、そのうえで1の個数がM枚で足りていればそのままでよく、足りなければ足りない分を購入する必要がある、これだけ購入してあれば足りる。と思ったらサンプル通らず、末尾に0がなかったらそこ集計されないじゃん。直してACしたが、今考えると毎回集計すればよかった。
D - Swapping Puzzle
この前の、しょうもない実装で時間を溶かした反省から、4分ほど考えて飛ばした。その時点で解けてはいなかったけど、こういうのは飛ばしたほうが無難、あまりにも無難なのだ。
コンテスト終了後に時間を測って解いた。追加で7分ちょっとかけてAC。（最大ケースで考えて）一旦回数は無視すると、ありえるパターンは縦横それぞれ順列で表せて5!通りずつ。120^2*5^2なら全探索できる。next_permutationを2重にやって一致してるかも愚直に判定。一致してたら最小操作回数を転倒数で求める。
E - Lucky bag
2乗の和を求めればいい。一応計算したんだけど、計算が終わったら10分経っててひどい。dp[e][k]を、グッズの集合kをe個の袋に入れるときの2乗和の最小値とした。まずdp[1][k]を埋める。15ならN^2*2^Nとかも余裕だろと思ってやっていた。実装していて気づいたが、D-1回の更新が必要。そのそれぞれに2^N回、更にその部分集合とかも見るとなるとどうか。この部分集合見るやつは3^Nでできるから、D*3^Nでなんとか間に合う。メモリはD*2^N。DPの更新だが、最適な入れ方の袋を1つの袋とそれ以外の袋に分けたときそのどちらも最適になっているはずなので、逆にそういうのが現れるように全列挙して最小値をとればいける、つまり1袋とそれ以外という分け方だけでいい。NとDを混同しやすく、大変だった。2乗の平均から平均の2乗を引く。提出してWA。
終了後も考え続けたが、2乗和が2^60以上になっている可能性に気づいたくらいで、WAの個数は何も変わらず。袋のほうが少ないので空の袋はないとしていいと最初に思ったけど問題文にある通りそれも考慮した実装にしていた。そんなところで余裕ぶってないで空の袋はないとしてやっていればよかった（空の袋がある場合、複数入っている袋が存在するのでそこから1個持ってくればスコアが改善する）。誤差についてはコンテスト中にも思ったが、答えが大きければ絶対誤差が大きくてもいいんだから大丈夫とか思ってた。でもそうとは限らない。引き算をしているから。どう実装するか悩んだが、単に2乗和の最小値にDを掛けた。そこから1乗和の2乗を引く。ここまで整数でやって、最後にD^2で割る。2乗和の最小値にDを掛けてオーバーフローしないか？Dが大きいなら1つの袋に集中することもないから大丈夫だろうと、計算せずに提出してAC。
平均が最初からわかってるのは気づいてたけど、それを最初から使ってdoubleでDPすれば最後にDで割るだけなのか。
本当に後味が悪い。まあ誤差死する方針を引けたことはラッキーだったな。
F - Random Update Query
計算時間を気にしないなら各A_iについてシミュレーションして簡単。まとめてやるとなると遅延セグ木だが、乗るか？他になさそうなので書いてみる。（遅延セグ木でできるなら）双対セグ木というやつでできるのだろうけど。最初は、区間の幅と変更する値Xを持つことにしていたが、難しいのは作用が重なってきたときの合成で、紙の上で改めて考える。区間の幅がw、現在の期待値がtのとき（最初変数名をeにしていたけど単位元のeと被ったので変更した）、(1/w)*X+(1-1/w)*tみたいになる。これがただの1次関数だと気づくのに時間がかかった。これをダブルでかまして式を整理してようやく気づいた。1次関数であればA+B*tの形で持つだけ。これは合成もできる。さて、セグ木の（この問題では使わない）演算をどうするか。最初単に左側の値にしていたが、これだと単位元に右側から掛けても単位元になってしまう。単位元を0にしていたので、0だったら違うほうを使うことに。だいぶ不自然だけど。0のときは0になるのでまあ。最後、塗り潰しは逆から見るのが典型なんですねーとか言いながら、気づいてみれば自分が実装していたのは順方向だった。ループを順方向に直してサンプルが通ったので提出してAC。
G - Not Too Many Balls
終了後このブログも大体書き終わってから読んで考えてみたが、NやMが小さければフローで解けるじゃん。なんとか工夫できないか考えたけどできないので解説を見た。最小カットは考えてたけどほんとにそうなのか。たしかに最小カットで考えるなら和の積で表せるね。そのあとは全然わかんねけど。
