C*A[i]-A[i]
で計算される。これの部分累積和が最大になる範囲を求める。場合分けはしない。判断をすれば判断ミスをするし、分岐すれば分岐した先それぞれでミスをするので。部分累積和の最大を求める方法だけど、名前が付いているらしかった。「Kadane's Algorithm | 最大部分配列 問題 - Ark's Blog」。名前で特定するより自分でひねりだすほうが簡単では? ダイクストラ法もね、優先順位付き(重み付き) BFS という、実態に即した命名の方が理解を促す面があると思うんだよね、固有名詞で特定するよりもね。■B 問題「Bought Review」。星は増やすことしかできない。星を水増しして総数を増やすことに意味はない。それを確認すると無駄な情報が見えてくる。星3の数はいらない。星123を増やす選択肢もいらない。星1と星2を星4と星5で打ち消すための配分を考える問題。二分探索が頭をよぎって線形性を探したけど、実は星4を2つ増やすコストと星5を1つ増やすコストの大小で即座に優先すべき選択が決定する。ぴったり打ち消すのがいいか、1つ星を余らせた方が効率的にも絶対的にも得かは、条件次第で判断が分かれるところ。最適な式を探るより候補を3つ並べる方が簡単。■D 問題「Digit vs Square Root」。小さい N に対して答えを列挙してみると、答えが見つかる範囲が 10 の冪乗とそこからいくつか下った狭い範囲に偏っていることがわかる。1、10、9、8、100、99、98、1000、999、……といった具合。あとはがんばる。ランダム入力に対して愚直解法と答えを突き合わせて1時間20分かかった。つらい。実装しながら Project Euler の Problem 63 Powerful Digit Counts に似ているなと思っていた(20110308p01.02)。■日記を書いているあいだに結果が出た。コンテスト成績証。ARC にはレートを吸われるばかりなので、微増は勝ち。