ABC351

6完。お腹の調子が悪かったけどコンテスト中は問題なかった。FGの崖で珍しく座ってるだけになった。

A - The bottom of the ninth

ちゃんと9回裏が存在する点数になっている。チーム高橋が何点上回っているかを求め、それに1を足したものが答え。

B - Spot the Difference

やるだけ。Bらしい、いい問題。

C - Merge the balls

i個目のボールにくっつけていく(相手がいなくなったらそのまま列の一番右に加える)イメージで実装。スタックを用意して、くっつけたら2倍になるので1を足す。1を足す操作は高々N回くらいなのでintで大丈夫(コンテスト中ははっきりわかってなかったが、1を足すたびに全体のボールの個数(最初はN)が1減るのでN-1回以下とわかる)。

D - Grid and Magnet

'#'の隣の'.'を'@'に書き換えておく。制約から答えは1以上なので'@'の自由度(常に1)は考えなくていい。UnionFindで'.'の連結成分を求め、その連結成分のサイズに周囲の'@'の個数を足せば連結成分内の'.'の自由度がわかる。'.'から見て同じ'@'を複数回数えてしまうことがありサンプル通らず。'@'から周囲の'.'(のleader)に配るようにすれば高々4個の要素の重複管理なのでできる(std::setを使っても十分高速)。難しかった。周囲4マスを見る処理を繰り返すが、そこはコピペなのでコーディング量は多くない。なぜ20分以上もかかっているのか自分でもわからない。まあ'@'に関する考察が難しかったからこんなもんかもな。

E - Jump Distance Sum

ウサギは斜めに動く。縦横に動くとして考えてみると、横だけ1次元なら解けるし、縦横独立に考えられる。位置の偶奇と縦横によって2*2通りのvectorを持ち、x,yの和が奇数ならxに1を足して偶数にし、和の1/2と差の1/2(どちらも整数)をvectorに突っ込んでいく。2*2のループを回し、ソートしてそこまでの和を持ちながらやればできることはすぐわかるが具体的にどうやるか考えて書く。符号付き64bitに収まることは確認してあったが、普通にintの乗算でオーバーフローしててWA。WAの原因にはすぐ気づいたけど、こんなWAを出すようじゃ常に64bitを使う戦い方をしない理由が出せなくなっちまう。

F - Double Sum

普通に考えていくと、自分より左で自分より小さいものの和と個数がわかればいい。E問題と似すぎていると思った。座圧してセグ木でできそう。答えが符号付き64bitに収まることも書いてあるので特に考えず書く。BITでできそうとも思ったが時間がかからないほうを選んだ。

(追記)evimaさんの別解の、小さい順に配置していくのはなるほど。座標圧縮要らないのいいねえ。BITを抽象化して使ってみた。