ABC213感想戦
ABC213 に参加しました。結果は、Eまでできて、レートは少しだけ上がりました。画像はコンテスト中に書いていたメモです。
A問題は、A, Bが与えられて、A xor C = B を満たす C を求める問題。一瞬、全部調べようかと思ったけど、A xor A = 0 だと思い直して、 C = A xor B を計算すればいいことに気づく。1分。
B問題は、順位が下から2番目である選手の番号を答える問題。ソートして下から2番目を求めればいいや、と思ったけど、「選手の番号」を答えるところを見過ごしていた。pair にして、2つ目の要素に番号を保存しておいて、ソートして解く。ここまでで4分。
C問題は、格子状にカードを置いて、カードのない行・列を取り除いていくと最後はどうなるかを答える問題。
要するに、各カードについて、行・列に関する座標圧縮をすればOK。自分が昔解いていたコードを使い回そうとするも、あまりうまく使い回せずにてこずる。ここまでで18分。
D問題は、木が与えられるので、ルールに従って移動するときの道順を答えるもの。
まぁこれはオイラーツアーをやるだけで、追加でやることといえば、各点からの行き先をソートすることくらい。もともと持っていたオイラーツアーのコードをベースにして解く。ここまでで30分。
E問題は、マスが与えられて、左上から右下に移動する状況。2x2の領域を破壊できるんだけど、その破壊回数の最小値を答える問題。
これはあまりパッとは解法が浮かばなくて、まず、横に全部破壊しながら進んで、下に全部破壊しながら進めば、まぁ500回くらいではいけそう。これが上限だ、ということはわかる。
後はあんまり何も思いつかなくて、つながっている領域を調べた後、各領域を最短何回の破壊でたどりつけるかを考えればいいのかな、とか思ってたけど、それはそれで難しそう。
で、考え直して、今いる場所から考えて、上下左右に破壊なしで行けるところと、破壊1回追加でいけるところをキューに入れていけばいい、というのにたどりつく。それを実装して終了。66分。
その後、F問題を見て何も思いつかず、何もできなくて終了。
レートは少しだけ微増でした。終了後、解説を見たけど、Fは解ける気がしない。