競技プログラミングの大会 AtCoder Regular Contest #101 に参加したのでC問題だけ解説を書きます。D問題は解けなかった……

C. Candles

問題概要：直線上にN個のろうそくがある。いま位置 0 にいる。徒歩でK個のろうそくに点火した。移動距離の最小値を求めよ。

あえて点火を避ける理由がないので、移動した範囲にあるすべてのろうそくに点火することになります。移動範囲は「i 番目のろうそくの位置」から「(i + K) 番目のろうそくの位置」までという形だけ考えます。

移動は「位置0 → i番目 → (i + K)番目」と「位置0 → (i + K)番目→ i番目」の2通りです。ろうそくの位置の符号は関係ありません。本番の提出では無駄に場合分けしてしまいましたが、絶対値を使えばいいだけだった……

これをすべての i について計算して、最小値を求めればOK。

提出：

D. Median of Medians

問題概要：数列の区間の中央値の中央値を求めよ。ただし A の中央値は (sort A)[ |A|/2 ]。

分かりませんでした。考察した内容を記しますが、この方針でACできるかは不明です。

まず最初に問題文を誤読して、A が最初からソート済みだと思っていました。このときは各位置 i について、その位置を含む区間の個数を数えればよくて、それは l = 1 + 2 i, r = 2 (N - i) とおくと min(l, r) 個です。逆バケツソートして中央値を計算すればOK。閑話休題

各要素 a について「a を含む区間で中央値が a になるもの」の個数を数えて逆バケツソート、は良さそう。a を含む区間 l..r の中央値が a になることは、a より小さい要素の個数 m が (r-l) / 2 であることと同値です。 m = (r-l) / 2 をうまいこと変換して区間の総和 s = 0 という形にすれば累積和に持ち込めて……と考えていましたが、うまい変形が思いつきません。

(ダメそうですね)

追記 (2018/09/10)：公式の解説PDFを読んで実装しました。むずい……

おわりに

C完。久しぶりの Rated (レート更新対象) で緊張感があり楽しかったです。Cを解くのが速めだったのか、レートは 15 上がりました。