AtCoder Regular Contest 097 - 情報妖精の競プロ日記

AtCoder Regular Contest 097に参加しました！
ABC097 旧版:
abc097.contest.atcoder.jp
ABC097 beta:
https://beta.atcoder.jp/contests/abc097/beta.atcoder.jp
ARC097 旧版:
arc097.contest.atcoder.jp
ARC097 beta:
https://beta.atcoder.jp/contests/arc097/beta.atcoder.jp

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 097 / Regular Contest 097
rated 1200 / 2800
5/12(土) 21:00 ～ 22:40 (100分)
100-200-300(200)-400-600-800 (6問)
ペナルティ: 5分

方針

C,D問題を早解き、E問題も挑みたい。
可能ならF問題だけど時間足りないだろうし……。

A - Colorful Transceivers

要は $|c-a| \leq d$ か $|b-a| \leq d$ かつ $|c-b| \leq d$ のどちらかが成り立っていれば通話可能です。

B - Exponential

まず、bは必ず $\sqrt{X}$ 以下になります。bを最小でも二乗するので、 $\sqrt{X}$ 以下でないとXよりも大きくなってしまいます。
後は、2から $\sqrt{X}$ までの数を順にXを超えない範囲でp乗していき、その値のうち最大値を出力すれば良いです。
なお、 $1 \leq X \leq 3$ においては1が解になることに注意してください。

K-th Substring

まず、問題文を見るとKがやけに小さいことが分かります。
ここで、substringの個数を考えてみるとせいぜい|s|K個の範囲で収まりそうです。
つまり、substringを全列挙してソートしてしまえば答えが分かります。
この時、同じsubstringが存在する可能性があることに注意し、適切に重複を削除してください。
オーダーは $O(|s|K \log{|s|K})$ です。

D - Equals

まず、入れ替えは好きな回数行うことができるので、入れ替え対象に目的の地点が入ってるかのみを考えれば良いことが分かります。
ここで、 $p_i$ と $p_j$ が入れ替え可能で、かつ $p_j$ と $p_k$ が入れ替え可能である時、 $p_i$ と $p_k$ もまた入れ替え可能です。
これは3個だけでなく、任意の個数で成り立つことが分かります。
これを $p_1$ から $p_N$ までのN点のグラフで考えてみると、 $(x_i, y_i)$ について $p_{x_i}$ から $p_{y_i}$ に枝が引かれていると考えた時、
自身と同じグラフに属する全ての点に移動できると考えることができます。
つまり、各 $p_i$ についてiが同じグラフに属していれば $p_i=i$ にできると考えられます。
同じグラフに属しているか、といえばUnion-Find法が適切ですから、後はUnion-Find法をすれば $O(Nα(N))$ で解くことができます。

結果

ooxx 2完(700点) 23:26(0WA)
214位パフォーマンス: 1935
レート: 1777→ 1794(+17)

感想

C問題の全列挙に発想が咄嗟に行かなかったのが痛い……。
substringでしかも $K \leq 5$ なので、最初の文字を固定したときそこから0～K-1文字伸ばしたsubstringまでしか解になりえない、ということに頭が咄嗟に回らなかった。
ただ、CもDも難しくはない(特にDはUnion-Findを知っていれば一瞬)ので、典型の練習としては良さそうですね。
E問題以降を解けなかったのは完全に自分の実力不足なので精進し直しますー。