little star's memory

競プロの参加記など

AtCoder Regular Contest 112

犯罪ACしたのいつ以来だろ。

コンテストページ

以下は参加した感想。

A - B = C

Cを固定すると、BはL以上R以下だから、AはL+C以上R+C以下になる。ゆえにAは$[L,R] \cap [L+C,R+C]$の範囲を動く。Cが増えるとこの範囲の長さは1ずつ減っていき、C=Rのとき共通部分の長さは0なので、答えは1+2+...+xの形になる。これは三角数で、$\frac{x(x+1)}{2}$に等しい。

ARC、こういう感じの算数が多くて難しい。

B - -- - B

4パターンある。

  • B, B-1, B-2, …, B-x
  • B, -B, -B-1, -B-2, ..., -B-x
  • B, B-1, B-2, ..., B-x, -B+x
  • B, -B, -B-1, -B-2, ..., -B-x, B+x

答えは$[-B-x_1, -B+x_2] \cup [B-x_3, B+x_4]$の長さになる。A問題が2区間の共通部分で、B問題が2区間の和集合だ。

これも難しい。

C - DFS Game

さっぱり。早めに見切りをつけたのはよかった。

D - Skate

どのマスから出発しても(1,1)にたどり着けるから、(1,1)を起点に考えればよい。到達可能な行・列を管理する。まずは外周をまわる。地面があったらさらに探索する。これ以上探索できなくなったとき、まだ通ってない地面があれば、そこにたどり着けるように1個地面を追加する。これを繰り返してすべての地面を通ったとする。このとき到達できない行の個数・列の個数のうち小さい方を答えに加算する。

これを実装すると1ケースだけTLEが出た。これをどうするか、3通りを考えた。

  • 高速化する。
  • 速い言語で書きなおす。
  • 1ケースを特定して無理やり通す。

Rustで書き直そうと思ったけど、パソコンを買い替えたばっかりでRust環境を構築していなかったのであきらめた。残る2つのどちらにするか考えたけど、1ケースだけだし頑張ればいけそう、ということで無理やり通すことにした。調べると、地面が大量にあるときは地面をSetにつっこむだけでかなり時間がかかることが判明。そこで地面がたくさんあるときは0を出力することにした。個数は何回か試したけど、500000以上で分岐したらACした。

ということで、これは嘘解法なんですねー。外周が氷でそれ以外が全部地面のときに普通に間違った答えを出す。

KotlinでTLEしたけど、ほかの言語だったらACしていたりしたのかな。

UnionFindが使えるらしい。さっぱりわからなくてLotus Leavesを見に行ったりしてた。