ABC308 (CodeQUEEN 2023 予選)
43分+1WA 6完
atcoder.jp
A はい (21:01)
atcoder.jp
B 最初C,Dを20以下の整数と勘違いした、map (21:06)
atcoder.jp
C 分数構造体を作っていますか?はい。ただ比較をlog取って済ませるタイプ(たしか分母×分子がlong longに収まらないタイプの問題用だった)にしてて誤差で1WA、10^18はlong longで間に合うので辺々払って比較した (21:15->21:16)
atcoder.jp
等号演算子を定義しなくて済むので、stable_sortを使うのがよいですね
atcoder.jp
D BFS、条件をコピペしまくった (21:21)
atcoder.jp
まあ"snukes"を用意してfindしましょう
atcoder.jp
E M0,M1,M2,X0,X1,X2について累積和して数え上げ、全パタン書き出したのはよくない方針だった (21:34)
atcoder.jp
M, Xを二次元vectorにしてmexの計算はプログラムにさせましょう
atcoder.jp
Eを探すのは2文字目からで良いから、M[0]にアクセスする必要がないので、1-indexedにしなくても累積和がどうにかなりそう
F 割引額の大きいほうから使える商品で一番安いのを選ぶ貪欲でよい、multisetで二分探索して除去 (21:43)
atcoder.jp
公式解説は「安い商品から使える割引券で一番割引額が大きいのを選ぶ」という逆の貪欲でしたが、ユーザ解説でこちらの貪欲も証明されています(証明してから貪欲を投げろ)
atcoder.jp
G なんかbitごとにいい感じにやればxを使うXOR最小値求まりそうだなあと思って色々やったけど複雑すぎて諦めた
解説AC、天才の発想すぎて無理……「整数集合から2つ選んだXORの最小は整列させた隣り合う数のXORのどれか」、典型感はないけど類題あったりするのかなあ
atcoder.jp