ABC309 (デンソークリエイトプログラミングコンテスト2023)
85分+5WA 6完 784th performance:1631
思ったよりかは死ななかったがrate1800が遠い
atcoder.jp
A 私は左右を上下左右と読みました、悪問 (21:01->21:02)
サンプルにも上下隣接がないの、極悪（あったらあったで首を捻り続けてそうな気がするが）
B 隣接を求めて反時計回りにいい感じの回数入れ替えていく、隣接を求めるのが反時計回りか時計回りかで混乱するし、条件分岐が多くて時間を溶かした (21:13)
atcoder.jp
C ソートして順に見て合計がKより小さくなった日を求める (21:18)
atcoder.jp
D BFSして前後最も遠い点を探す。 (21:27)
最初「なるほど、2つに分かれているグラフを結んだときに1とNが最短になるときか……1とNを結べば常に1では？」となった、そんなのDで出題されるか。「最短距離」と聞くとすぐダイクストラを連想する人が多いのかトレンド入りとかしてたけど、辺長1のグラフの最短距離はたいがいBFSで済むので変な学習をしてる人がいないか心配ではある（BFSもダイクストラも更新順が変なDPという認識があんまないのかも）
atcoder.jp
E 保険が効く長さを更新しつつBFS (21:40)
同じ人間が複数の保険に入っている場合があり、そこらへん入出力で見逃しそうという感じがした（短いほうの保険で上書きしてしまう）
atcoder.jp
Dの影響もあり、普通にグラフにしたが、問題の制約から常に親は子より若い番号であるから、受け取るDPで解ける。
atcoder.jp
F (22:25)
条件を満たす2つの箱のサイズを{a1,a2,a3} ＜ {b1,b2,b3}とする。a1≦a2≦a3とすると、b1≦b2≦b3となるように並べ替えたときにa1＜b1, a2＜b2, a3＜b3となる。したがって、すべての箱のサイズはa1＜a2＜a3となるように並べ替えてよい。並べ替えたものを(h,w,d)とする。
Nの制約より、明らかにソートはOK。最初は最大と最小を比べるだけでOKかと思ったが、(1,10,3),(2,3,4),(3,4,5)みたいなときにダメ。2番目のサイズについても昇順に見たいので(w,d)の優先度付きキューとかでなんとかならないかと思ったが、(1,2,10),(2,3,4),(3,4,5)みたいなときにダメ。mapで「wがX以下のときのdの最小」を管理できないかと思ったが、後ろに波及するのでダメ。
ここでmapを使ったあたりから座標圧縮するとなんか良さそうな感じに気付く。「wがX以下のときのdの最小」はもう少し難しいデータ構造を使えばできそうな感じがしたのでちょっと考えた感じセグメント木が使えそうだと気付く。wはそのままでは10^9でセグメント木に乗らないが、座標圧縮すれば2*10^5になり間に合う。それでなんとか書き上げて提出するがWA。落とし穴に3箇所ぐらい嵌った。
1箇所目がソート順。単に昇順で良さそうだが、常にh(i-1)＜hiが保証されているわけではなく、h(i-1)=hiの場合があり、w(i-1)＜wi, d(i-1)＜diのときにOKと誤判定してしまう。hを昇順、wを降順とすることで、h(i-1)=hiのときは常にw(i-1)≧wiにできる。ソート用のラムダ関数を間違えて1RE、1WA出ていたもののランタイムエラーの影響と考えて、ラムダ関数を直して突っ張ったがもう2箇所ミスがあり、+1WA。
2箇所目がセグメント木の更新。常に出てきたseg[w']=dと更新していたが、w'はこれより前に登場している可能性があり、seg[w']＜dとなっている場合がある。最小値更新する必要がある。これを直して+1WA。dも降順にソートすればOKじゃね？と思ったが、hi≠hj, wi=wjのパタンがあるのでダメ。
3箇所目がセグメント木のprodの範囲。w'を含めてしまっていたが、これはhi＜hj, wi=wj, di＜djのパタンをOKと誤判定してしまう。w'を除いた範囲にする必要がある。これを直して4WAでなんとか突破した。
座標圧縮してセグメント木とかかなり牛刀を持ち出してしまった感じがしたが、解説を読む限り想定解でビビった。そのうえで900人近くこれを通していることにもビビった。レベルが高い。
G Fで沼ったときにちょっと見て包除原理と筋肉！という感じがしたのでパス。X≦5あたり行列累乗かなあとか思ったが、2^(2X)状態を考える感じのDPらしい。
