6完 33:42 388位
ライブラリをなにも理解していないことをさらしてしまった
A New Scheme
ABCの配点として正しいかどうかってことですね
言われたとおりにif文を書いて判定
(AC 2:35)
B Default Price
いつものBですね
それぞれの色について何円なのか保存しておけば、ループで調べれば解けます
map使った方が直感的なのでそうしたけど
(AC 5:49)
C Standings
これむずいと思う、茶色の僕は知らなかった
C++だとsort関数に比較する関数を渡してあげることができるので、これを定義します
Ai / (Ai + Bi) < Aj / (Aj + Bj)ですが、誤差が怖いので分母を払ってあげて
Ai * (Aj + Bj) < Aj * (Ai + Bi)とすればよいです
これに加えて、indexの比較も同じ関数内に入れておけばOKです
(解説のようなstable_sortではなく、indexの比較をいれたもの)
Submission #43100882 - AtCoder Beginner Contest 308
(AC 11:35)
D Snuke Maze
いつものD
s -> n -> u -> k -> e -> s ... と動いていくことになるので、それぞれ隣り合うものをみて辺を張れるか判定してあげて、張れるなら張ります
そうしてグラフを作ってあげれば、あとは(1,1)からBFSやDFSをして(H,W)に到達できるかみるとよいです
※陽にグラフをつくらなくても、「マスの上を動かしていって動ける＆まだ行ってない場所に行く」を繰り返せばよいです
(AC 19:18)
E MEX
典型：「3つのものは真ん中を固定」
何度も出題されていますが、こういうタイプの数え上げ・和の計算は真ん中を決めるとうまくいくことが多いです
類題
今回も真ん中のEの位置を決めます
そうすると、「自分より左にあるM」と「自分より右にあるX」しか考えなくてよくなります
これは左右からの累積和を使って簡単に個数をまとめられるのでうれしいです
この問題ではこれに＋αがあります
mexは0,1,2のうちどれがあって、どれがないか？がわかればよいので、「自分より左にあるM」のうち(0の個数、1の個数、2の個数)を求めて、Xについても同様に求めればよいです
あとは各Eについて、Mでどの数字を採用するか・Xでどの数字を採用するかを総当たりして個数を加算してあげれば解けます
(AC 27:43)
F Vouchers
貪欲っぽい問題は正しい貪欲を思いつくのが難しいものも多いですが、「制限の厳しいものから考える」というアプローチが有効なことがそれなりにあります
(この問題に限らず)おきもちとして、いきなりめちゃくちゃ選択肢があるものを考えるのは大変です
なので選択肢が少ないものを考えて、「この厳しい条件ではこうするのがベスト」という方法を見つけてみます
それが全体の問題を解くときに使えないか？と考えると解法が見えることがあります
あらためて今回の問題を考えると、高い商品にはたくさんクーポンを使えるが、安い商品には使えるクーポンが少ないことが分かります
また、安い商品に使えるクーポンは高い商品にも使えるので、使えるクーポンの集合はどんどん増えていくことになります(=あとで使えなくなるから最善ではないけど早めに使わないといけない、ということは起こりません)
よって、安い順にみていって「その時に使えるクーポンのうち最も割引額が大きいものを使う」として問題ありません
これはpriority_queueを使うと実装できます
類題
(AC 33:42)
G Minimum Xor Pair Query
想定解法が天才だった
これは思いつかなかったのでBinary Trie解法を書きます
まず、xorの典型考察として「桁ごとに考える」というものがあります
xorをできるだけ減らそうとすると、k桁目までいっしょでその部分が0になるとうれしいので、「k桁目まで同じものがある」かどうかを調べたくなります
これはBinary Trieでやっていることと同じなので、Binary Trieを使って解けそうだと思います
もう少し詳しく考えていきます
k桁目まで同じものが2つあるとすると、そのxorは答えの候補になります
Binary Trieでは各ノードに「あてはまる数字の個数」「あてはまる数字どれか1つ」を持つことにします
addクエリでは、そのノードの「あてはまる数字どれか1つ」がないならば、addする値で更新します
また、「該当する数字の個数」が2になったときに、2つの子ノードがあればそれぞれの「あてはまる数字どれか1つ」のxorをmultisetに加えます
もしくは、葉ノードの「該当する数字の個数」が2(=等しい値が存在する)のときに0をmultisetに加えます
3,4...など2より大きいときにもっと小さい値ができる可能性がありますが、それはもっと深いノードで2になるところがある or 葉ノードに2つ以上の値があり0になる、のどちらかなので考えなくてよいです
addクエリは比較的簡単ですが、eraseクエリはちょっと面倒かもしれません
大枠はaddクエリと同じですが、「あてはまる数字どれか1つ」を管理する必要があります
「あてはまる数字どれか1つ」が今消そうとしている数かもしれません
その場合は、子ノードの「あてはまる数字どれか1つ」を適当に選んで更新してあげればよいです
ただし、更新した場合はもともとmultisetにあったxorとは異なる可能性があるので、あらかじめそのノードで加えていたxorの値を取り除いてから、新しい値を加えることになります
とりあえず書いたんですが、文章だとかなり煩雑なので実装も置いておきます
(実装のadhocと書かれている部分がBinary Trieに書き加えた部分です)
(AC --:--)
総括
Binary Trieやっと実装がわかってきた
