AtCoder Regular Contest 098
Updated:
今日はずっと頭がスローモーションみたいになっていて、うまくいかなかった。時間には間に合わなかったけど自力で E を通した。
なんとなく最近調子が悪いような気がする。レーティングはしばらく下がるけど、それでも諦めずに考えて、復習をしっかりしたいと思う。
Source codes
Solutions
C - Attention
まず、
$cnt[0][i] = [0, i]$ で
Wの人$cnt[1][i] = [i, N-1]$ で
Eの人
として、 $cnt[i] = cnt[0][i-1] + cnt[1][i+1]$ とする( range を外れるところは $0$ にする)。 $\min_{i \in [0, N-1]} cnt[i]$ が答え。
ポイント
エディタのプロセスが正しく終了していなくて再起動していたら時間がかかった。
D - Xor Sum 2
わからなかったので E から解いた。
解法
$A_i$ たちを縦に $2$ 進法で並べて筆算していくことを考える。この場合 $xor$ の場合と $+$ の場合では「繰り上がり」の処理が違う。前者は繰り上がりをしない。後者は繰り上がりがある。よって、繰り上がりがあると、必ず両者の計算結果は異なる。逆に繰り上がりがないなら両者の計算結果は一致する。したがって、問題文の条件が成立する必要十分条件は、以下の通りにまとめられる。
全ての桁 $0 \leq t < 20$ に対し、 $A_i$ の $t$ 番目の bit が立っているような $l \leq i \leq r$ は $1$ 個以下である。
これを充たす $(l, r)$ の総数は尺取り法で $O(N)$ で求まる。
尺取り法の実装
自己流でやっても十分であるが、プログラミングコンテストチェレンジブックの実装を真似するのが最終的に速い。基本パターンは以下の通り。 $l$ を最後まで走査する場合は以下の通り。
int l = 0, r = 0;
int sum = 0;
while (l < N)
{
while (r < N && sumについての条件)
{
sum += A[r++];
}
答えに関する操作
sum -= A[l++];
}
最小値などを求める際に、 $r$ だけ最後までたどり着けば十分な場合は以下の通りにする。
int l = 0, r = 0;
int sum = 0;
while (true)
{
while (r < N && sumについての条件)
{
sum += A[r++];
}
if (sumについての条件)
{
break;
}
答えに関する操作
sum -= A[l++];
}
ポイント
単純だが一瞬では思いつかなかった。 E の方に行った。
E - Range Minimum Queries
結論から言うと BIT を使う問題である。しかし 0-indexed とする。
考察： Y を固定し貪欲に選ぶ
まず考察をする。制約を追加し $Y$ を最初に決めるとする。すると問題が解けるかどうかはそもそもわからないが、この場合、 $Y$ 以上の数字を小さい方から貪欲に検討し、選べるなら選び、選ばないなら選ばない方が望ましい。このことは直感的にも明らかだと思うが、一応下に証明を書く。
- 知りたいのは $X - Y$ の最小値であるから、 $X$ は小さい方がいい。だからなるべく小さい数字を $Q$ 個選ぶべきである。
- 仮に $X - Y$ の最小値を達成する選び方が $b_0, \dots, b_{Q-1}$ であるとして、ある $q$ が存在し $b_q > b_{q+1}$ となったと仮定する。この場合、 range を決めた時に選ぶ数字は最小値であるため、 $b_{q+1}$ を選んでから $b_{q}$ を選ぶという方法も必ず可能である。すなわち、 $b_0 \leq \dots \leq b_{Q-1}$ を仮定してよい。
主張する貪欲な検討法は、 1. に叶い、かつそれで最適であるのは 2. より保証される。よって示された。
ある数字をクエリで取り出せる条件
そこで、数字の大きい順に pair (value, index) の組をソートして vector で $V$ にいれておく。 $i = 0, \dots, N-1$ に対し、それぞれ $j = 0, \dots, i$ の $V[j]$ たちを使うことで、問題を解くことを考える。つまりこれから選んで良い数字は V[j].first たちだけであり、 Y = V[i].first; である。これらを小さい方から選ぶことにより、そもそも $Q$ 個選べるかを判定する。
何を選ぶことができるのかということを考える。 bool visited[2010]; に V[j].second で触れたところだけ true, そうでないなら false を入れる。ここで、 visited[k] が true であるような $k$ に対し $A_k$ が選べるための条件は、以下の通りである。
条件：ある $l \leq k \leq r$ が存在し、全ての $l \leq t \leq r$ に対し
visited[t]はtrueであり、かつ $l \leq t \leq r$ のうち $A_{k}$ 以上の $A_{t}$ が $K$ 個以上ある。
この条件で、 $l$ はできるだけ小さく、 $r$ はできるだけ大きく選ぶべきである。つまり false がでる限界まで見ればいい。だからこれは累積和みたいにして visited が確定した時点で全ての $0 \leq k \leq N-1$ に対して合計 $O(N)$ の時間で決定することができる。少し定義を変更して、以下のように定める。このほうが求めやすい。
$left[k] = $
!visited[t]であるような $t$ のうち $k$ 以下の最も大きな $t$ 、ないなら $-1$ とする。$right[k] = $
!visited[t]であるような $t$ のうち $k$ 以上の最も小さな $t$ 、ないなら $N$ とする。
ここまで求まれば、あとは「$A_{k}$ 以上の $A_{t}$ が $Q$ 個以上ある」は Binary Indexed Tree で求まることがわかる。つまり次のようにする。
- $j = 0, \dots, i$ に対し、
k = V[j].second;とする。bit.add(k+1);をまずする。次にcnt[k] = bit.sum(left[k]+2, right[k]+1);とする。 BIT は 1-indexed であるのでこうする。 - $j = i, \dots, 0$ に対し、
k = V[j].second;とする。cnt[k] >= Kならばsel++;する。sel == Qとなった瞬間にX = V[j].first;として $Y - X$ を解答の候補とし終了する。その瞬間がないならそもそもその $Y$ ではできない。
計算量は $O(N^2 \log N)$ である。 $N \leq 2000$ なら十分余裕がある。
ポイント
頭がスローモーションで時間内に解くことができなかった。
まず貪欲法の考察は一瞬だった。昇順で持っておく reverse ところも合っていた。条件を正確に把握することができなかった。しばらく Union-Find でやるのではと間違った思考に陥っていた。条件をしっかり書き出せば、 BIT で求まることは自明なのに。
BIT で大丈夫と気づいたのは「$left$ と $right$ を $k$ の関数として決定でき、それが全体で $O(N)$ で求まる」ということに気付いた瞬間である。左右に限界まで見ていくのは無駄な操作だなと思っていた。そこから「$Y$ を固定すれば、$left$ と $right$ を $k$ の関数として決定でき…」と気づいた。これに気づいた時には残り 15 分だった。さすがに間に合わなかった。
- range は BIT か SegTree で処理する。
- BIT で求める際は、 range を index の関数として決定できるのではないか 検討する。
これらがポイントではないかと思う。
あとは実装上のミス。 BIT は 1-indexed であるからここだけずらす必要がある。
F - Donation
ポイント
Others
C - sample: 3, tle: 2.000, time: 10:05, from_submit: 176:14
D - sample: 3, tle: 2.000, time: 07:37
E - sample: 3, tle: 2.000, time: 103:09, from_submit: 65:28
F - sample: 3, tle: 2.000, time: 65:28
最近調子が良くない。しばらくレート溶かすと思うけど、 気にせず溶かしていこう と思う。大事なのは、調子がいいときにいいパフォーマンスを発揮できることである。株価だって上がる前に下がることを回避できない。それと同じようなもの。
吹雪が吹き荒れる中で、どういう準備をしておけばいいかは私はわかっている。結局のところ調子がいい日が来た時に万全の体制で臨めるようにするだけのことである。抜けないトンネルはない。