abc255に挑んだ初心者の感想

atcoderの過去問abc255にチャレンジした所感を述べるだけです．ちなみにコンテスト参加経験は11回しかない、茶色人間です．d問題以降は解けていないし、e問題以降は見てすらいないです．

A - You should output ARC, though this is ABC.

行列を作って、指定された要素を出力するだけです．これくらい簡単な方が、初心者的に自身がつくので◎です．

B - Batters

以前abc256を解いているときに、間違えて255のb問題を解いてしまったので、代わりに256のb問題を解きました．b問題にしてはちょっと考えたかな~くらいの難易度でした．各ベースにいる人数を配列で保持し、各iごとにその配列に操作を加えます．条件分岐を適切に設定できれば解けると思います．

C - ±1 Operation 1

数列のとれる最大値と最小値をまず計算します．次に、xの値がこの値に対してどの位置にいるかによって場合分けします．

①の場合、x-maxが答えで、③の場合はmin-xが答えです．
②の場合は定式化して考えましょう
X + res = D * n + A (0≦n≦N-1)
　　X-A=D*n - res 
答えはX-AをDで割った余りから求められそうな感じがします．
余りがpなら、pとD-pの内小さい方が答えです．
ここで、負の数の割り算が面倒なので、正の数に正規化します．
q = X-A < 0 なら　q = -q
D < 0 なら　D = -Dとします。
これを行っていい理由を以下で説明します.
例えば、
12 % 5 = 2
-12 % 5 = -2
12 % -5 = 2
-12 % 5 = -2
となりますが、結果は割る数5の正負に依存しないので負の符号を取り除いてもよいです．また、割られる数が負の時あまりも負になりますが、今回得たい結果は正の数なので、負の符号を取り除いてもかまいません．いろいろごちゃごちゃ述べましたが、一番学ぶべきことは

負の数の割り算はだるいから、正規化しろ!!!

ということです．

D - ±1 Operation 2

解けませんでした( ；∀；)
私がどう考えたかと言いますと…
まず、全探索したら計算量的にダメだから、1回のクエリをO(1)またはO(logN)で処理しなければならないと感じました．
そこで、一つ前のクエリの結果を利用すればよいのでは?と考え、無理やり立式したところ、長時間考えて非常に複雑な式が完成しました．この時点でやる気を喪失しました。XiとAiの大小関係が重要なので配列Aをソートして2分探索を行い、立式から累積和が必要なことは判断できたのですが、もっと大切なポイントを忘れていました．

とりあえず立式する!!!

あれこれ考える前に答えを立式するべきでした．単純だけど忘れがちなことであり、立式するだけで解けるような問題もあった気がします．立式すると

A(1) <= A(2) <= …<=A(k)<=X<=A(k+1)<=…<=A(n)ならば
ans = Σ(i=1~k) (X-A(k)) + Σ(i=k+1~n) (A(n)-X)
となり、ソートと累積和を使えば簡単に解けることが分かります．
とりあえず立式はとりあえず全探索並みに意識した方が良いと感じました．

まとめ

C問題まで解けたので茶色的にはOKです．ただ、C問題で負の数の割り算を考えるのが難しく、何回かWAを食らってしまいました．余りは全部正の値にしてほしいのが本音ですが、仕様にケチをつけても仕方がないので、「負の数の割り算は工夫して避ける」が正解だと思います．また、D問題は解くのに必要な要素(ソートや累積和)は思いついたのですが、肝心の立式ができていませんでした．．．「とりま立式」を肝に銘じたいと思います．