脳log[20251116]

2025年11月16日 (日) [AtCoder] 今日は estie プログラミングコンテスト2025 （ARC210）があった。■A 問題 Always Increasing。直前の要素からいくつプラスされている必要があるかという情報を管理しながらクエリをシミュレートする。実際の提出では増分ではなく数列の値そのものを BIT で管理して無駄に log を付けた。それにもかかわらず BIT だから累積和だからということで勘違いをして、N 番目の値を参照したら N 項の累積和が得られると思い込んで答えが合わなかった。21 分かかっています。■B 問題 Remove Median Operations。１回のクエリをシミュレートすることはできると思うんだけど、クエリ毎にシミュレーションを繰り返していては当然間に合わない。困ったね。先の問題をチラ見して追い返されたりしながら考えていると、数列 B を数列 A に放り込む操作はまとめて行ってもいいような気がしてきた。A と B を混ぜて小さい方から N/2 個、大きい方から N/2 個を取り出して合計したものが答えではないか。それの正しさは X から X の中央値を削除する代わりにマークを付けてシミュレートしていけばなんとなく(！)わかる。あとは昨日の ABC-E と同じように BIT で数と和を管理して答える。それだけのことがすんなりいかないんだな。小さい方から N/2 個と大きい方から N/2 個を得るのに左からと右からで添字を調整してごちゃごちゃするのが嫌で、ソート列を昇順と降順で２つ作って、データは２つだけどコードはコピペで済ませようとした。ところが座圧のためのデータは複製していなかったために結局添字の調整が必要になっていて、それに気がつかなくてデバッグに時間を取られた。#71013020 の 81 行目。Mn↔Mx の交換だけではダメで 77 行目では X[i] だったものを X[~i] にしている。こんな罠に初見でひっかからないはずがなく……。40 分かかっています。■C 問題 Fair Coin Partition。だいたいの答えは出た。最初にどんどん繰り上げていって、大きいコインから順番に M 人に配る。小は大を兼ね、逆はそうではないので、大きいコインを無駄にしないように最初にすべて繰り上げて大きいコインから順番に最大限消費していく。その次が問題。M 枚未満の半端なコインを今度は繰り下げていきたいのだけど、最初に持っていたコインより細かく砕くことはできない。何枚繰り下げることができるのか把握しきれなかった。