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

AtCoder Regular Contest 098に参加しました！
ABC098 beta:
https://beta.atcoder.jp/contests/abc098/beta.atcoder.jp
ARC098 旧版:
arc098.contest.atcoder.jp
ARC098 beta:
https://beta.atcoder.jp/contests/arc098/beta.atcoder.jp

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

要項

AtCoder Beginner Contest 098 / Regular Contest 098
rated 1200 / 2800
5/26(土) 21:00 ～ 22:40 (100分)
100-200-300-500-600-1000 (6問)
ペナルティ: 5分

方針

C,D,Eまで解いて終了かな
早解きコンテストなのは確定

A - Add Sub Mul

比較してください。以上。
一つヒントとして、algorithmのmax関数は、max({A, B, C})のようにすることで一度に複数の要素の最大を取り出すことができます。

B - Cut and Count

各切断箇所に対して愚直に考える方法もありますが、せっかくなのでちょっと綺麗な解法を考えてみましょう。
各文字に対し、一番最初に出てきた場所と一番最後に出てきた場所を覚えておきます。
また、切断場所は指定した場所の右側(例えば切断場所を1文字目とすると、1文字目 | 残りの文字)としましょうか。
この時、各文字について一番最初に出てきた場所 $\leq$ 切断場所 $<$ 一番最後に出てきた場所ならば両方に含まれます。
この方法なら、まず最初に出現地点を覚えるのに $O(N)$ 、次に切断場所の候補が $O(N)$ 、各切断場所について計算量は $O(26) = O(1)$ となります。
全体として $O(N)$ で解けますね！

C - Attention

まず、 $i$ 番目の人がリーダーであると仮定しましょう。
この時、リーダーより左側にいる西を向いている人とリーダーより右側にいる東を向いている人が振り向く人になります。
ここで、まず西について累積和 $sumW$ を考えると、リーダーより左側にいる西を向いている人は $sumW_{N-1} - sumW_{i-1}$ で求まります。
同様に東も同じことをすれば、ある人がリーダーである場合の振り向く人が $O(1)$ で求まります。
ということは、全ての人について $O(N)$ で求まるので解けます。

D - Xor Sum 2

まず、xorについても足し算と同じように分配や交換法則が成り立ったりすることは知っておいてください。
え、知らなかった？今覚えて。
さて、このことを考えると、範囲 $A_i$ から $A_j$ について等式が成立しているなら、この範囲における任意の部分集合について等式が成立します。
そこで、尺取り法というものを考えます。
まず、 $j$ を1ずつ増やしていきます。
そこで、 $A_i$ から $A_j$ の範囲で等式が不成立になったなら、成立するまで $i$ を増やします。
この時、 $(A_i, A_i)$ 、 $A_i, A_{i+1}$ 、……、 $A_i, A_{j-1}$ では等式が成立していたはずなので、 $i$ を増やす度に $j-i$ 個を答えに加算します。
そうすれば、 $i, j$ が最後まで動いた時に答えが求まります。計算量は $O(N)$ 。
オーバーフローには注意しましょう！

E - Range Minimum Queries

まず、 $X$ と $Y$ を固定して考えてみます。
そうすると、 $Y$ 以上の要素のみで構成された連続した部分列からしか値を取り出せないことが分かります。
また、この部分列からはなるべく小さい値を取り出すとしましょう。( $Y$ 固定なので)
このような取り方は、常に部分列に対し一番小さい値を含めるように範囲を定めれば取り出せます。
また、部分列の長さを $L$ とするとその部分列からは要素を $\max(0, L - K + 1)$ 個取り出すことができますね。
…… $X$ 不要なことに気付いたので $Y$ だけを固定して考察します。
まず、先ほどの考察より $Y$ を固定した時に取り出す値の候補は各部分列ごとに $max(0, L - K + 1)$ 個の小さい値として出てきます。
後は、これをソートして小さい方から $Q$ 個取り出し、その時の最小と最大の差がその時の $Y$ における答えになります。
後は $Y$ を動かしていけば良いです。
$Y$ の候補は $N-Q+1$ 個あるので $O(N)$ 、その時における計算量はソートが最も大きく $O(N \log N)$ で終わるので、全体で $O(N^2 \log N)$ 回で計算できます。