ABC157

5完。Aは簡単。BCは嫌い。DEFは好き。精神状態が悪かった(よくあるやつ)けど、普通にやれた。

A - Duplex Printing

切り上げ。

B - Bingo

簡単だが、実装がめたくそ重い。0b111000000, 0b000111000みたいにビットでやるのも考えたけど8個正確に書く手間を考えるとなあ。提出したコードもたいがいだが。

C - Guess The Number

配列に数字を入れていく。既に数字が入っていたら矛盾チェック。そして1桁でないときは最上位が0になってないかチェック。あとは最上位を(入ってなかったら)1にして他の入ってない場所は0で埋める。WA。1桁だったら最上位を0にしましょう。知ってた。こんな簡単な問題に時間をかけられないので仕方のない1ペナ。この問題はクソ。つまらない。

D - Friend Suggestions

ベン図を描く。円は2つ、友達+友達候補とブロックした相手。友達+友達候補はUnionFindでわかるから、あとは友達候補かつブロック関係の数がわかればいい。友達候補もブロック関係もO(N)になりうるのでかなり難しく感じ、Eを読みに行ったりもした。しかし、もう一回考えるとブロック数は全体でKなので全ブロック相手について友達候補かのチェックは(UnionFindで高速に)行える。全体で考えるの面白い。
友達をブロックはしてないので、友達+友達候補の数からブロックした数を引けばいい。実装は、自分を含めた友達の数とブロック相手のvectorを持てばよい。

E - Simple String Queries

「何種類か」だと難しそうだが「表れる文字の集合」であれば簡単そうだ。集合をビットで表してその個数を数えるのはこの前書いたpopcntがある。セグ木で瞬殺だった。50万文字は多いと思ったが、クエリが少ないので13msしかかからない。

F - Yakiniku Optimization Problem

K個を含む円であって最小のものが知りたい。その円は3個の外接円か2個の直径で決まる。いや違う、cがあるから。でもcが1固定の問題は解ける必要があるから、この問題が解ければ外接円は求まる(外接円だけでは解けないのに外接円を内包しているので、つまり難しい)。さて、答えとなる熱源の位置から見てcで肉までの距離を伸び縮みさせるとやはり外接円になっている。最近外接円やったよなと思ってブログを検索するとABC151だった。あのときは半径だけわかればよかった。今回は中心も知りたい。一口に外接円といっても色々な見方がある。「外接円 作図」でググって、垂直二等分線が円に一般化されたやつだなと思った。2点からの距離の比が一定の点の集合は直線か円になる。で、その3つの円(直線を含む(!))はたぶん1点で交わるからそこが候補。ただ、この時点で残り40分。実装は無理だなあと思った。細かいところもあやしいだろうし。3つの円が交わらないケースもありそうで、それがどんなときかでけっこう悩んだ。2つの頂点のcがでかくて他の頂点が関係なくなるときかなあ。とりあえず2点が直径になるケースは書いた。実装は簡単だがコーディング量が多かったので、どうやったら(主にライブラリ整備という意味で)短く書けるかを考えたいと思った。