ABC308

7完。久しぶりに勝って気分がいい。

A - New Scheme

複雑すぎるだろふざけんな。直前の値の初期値を100にすればif文ちょっと短くなると思ったけど証明する負荷が大きいと見てやらなかった。ABCの配点のことらしいです。気づいていたら多少楽に書けたかも。

B - Default Price

mapに価格を入れると、ない色を指定したとき0が出てくるの微妙だなと思っていたが、実装を進めていくとmapが返すのは価格ではなくインデックスになって(CとDが別々に与えられるので)0が返るのは好都合だった。きれいに書ける。これも内容的にはBだけど、パッと見複雑だよなあ。

C - Standings

A_iとB_iとiを持ってソート。stable_sortを使って、分数の比較は両辺に分母掛ける。

D - Snuke Maze

"snuke"に同じ文字が複数含まれないことを確認。マスの位置に加えて何らかの状態を持たなければならないかと心配するが、よく考えるとあるマスに到達したときのスタート地点からの歩数はmod 5で決まっている。ということで、単純に("snuke"が円環につながってるとして)隣の文字なら移動できるというだけ。BFSをする。最初の文字が's'でなければならないことに注意。

CとD解いた人数同じくらいなのやばいな。Dけっこう難しいと思うし実装もそこそこ重いし。

E - MEX

とりあえず真ん中(E)を固定してみる。すると、左のMと右のXの個数がわかればいいから、個数を更新しながらできそうだ。まず、Xの位置の0,1,2の個数をそれぞれカウントしておく。そうしておいて前からMとXの位置の0,1,2の個数を更新しながら見ていく。そこがEだったら、MとXのところの数を9通り全探索して、3つの数のmexを求めて、何通りあるかを掛け算して足していく。

F - Vouchers

FGを読んで少し考えて順位表を見た。Fがかなり解かれている。全然わからない。

使わなきゃいけないクーポンはないけど、商品は全部買わないといけない。三角形を描いて端を見ていたが、使える商品が少ないクーポンではなく、使えるクーポンが少ない商品を見ればよかった。Pはソートしてしまっていい。クーポンもLでソートしておいて、使えるのをpriority_queueで追加していって(あれば)一番いいのを使う。しゃくとりみたいに追加していくんだけど、条件の不等式が、問題文まんまなのにPではなくLを動かすからなんか混乱してしまって大変だった。

G - Minimum Xor Pair Query

トライ木でできそう。だいぶ手探りだったけど、実装でだんだん考えが整理されていって最初のイメージがけっこう間違っていたことがわかる。基本的なアイデアは、普通に追加してからその逆を辿れば部分木の2数のxorの最小値などを必要なところだけ更新できるというもの。個数が2以上になったら確定するので、個数が1であるならその1個はこれという値も保持する。当たって2個になったときxorをとり、その最小値をセグ木みたいに一番上まで持ち上げる。ややあやしかったけどAC。あとから考えると、「その1個はこれ」というのはそのノード以下に入った値の総xorでよかったな(1個のときは当然それ自身になるし更新が楽)。