2025年11月16日 (日)[AtCoder] 今日は estie プログラミングコンテスト2025 （ARC210）があった。■A 問題 Always Increasing。直前の要素からいくつプラスされている必要があるかという情報を管理しながらクエリをシミュレートする。実際の提出では増分ではなく数列の実際の値を BIT で管理して無駄に log を付けた。21 分かかっています。■B 問題 Remove Median Operations。１回のクエリをシミュレートすることはできると思うんだけど、クエリ毎にシミュレーションを繰り返していては当然間に合わない。困ったね。先の問題をチラ見して追い返されたりしながら考えていると、数列 B を数列 A に放り込む操作はまとめて行ってもいいような気がしてきた。A と B を混ぜて小さい方から N/2 個、大きい方から N/2 個を取り出して合計したものが答えではないか。それの正しさは X から X の中央値を削除する代わりにマークを付けてシミュレートしていけばなんとなく(！)わかる。あとは昨日の ABC-E と同じように BIT で数と和を管理して答える。40 分かかっています。■C 問題 Fair Coin Partition。だいたいの答えは出た。最初にどんどん繰り上げていって、大きいコインから順番に M 人に配る。小は大を兼ね、逆はそうではないので、大きいコインを無駄にしないように最初にすべて繰り上げて大きいコインから順番に最大限消費していく。その次が問題。M 枚未満の半端なコインを今度は繰り下げていきたいのだけど、最初に持っていたコインより細かく砕くことはできない。何枚繰り下げることができるのか把握しきれなかった。