エイシングプログラミングコンテスト2022（AtCoder Beginner Contest 255）に参加しました。
結果
A,B,Cの3問正解でした。 最近D問題からがうまく解けないことが多くてレーティングがちょっとずつ溶けていっている…
B問題の考察が甘くて1WAしたのが痛かった。
C問題は考察自体は正しいと思いつつ何故かWAになったので愚直に解くようにして無理やりACした。解説読んだけどやっぱり考察自体はあっていた。どこかでバグがあったのかなあ。
D問題はちょっと考えが足りなかった…
A - You should output ARC, though this is ABC.
22の配列を用意して、指定された要素の値を出力する問題。
配列の扱い方を知っているかどうかな問題だと思う。
配列の参照が0からなのか1からなのかで指定された要素番号を1ずらす処理が必要。
もしくは配列の参照が0始まりの言語の場合は33の配列を用意して1-1から2-2までの要素だけを使えば、指定された要素番号をそのまま答えれば良くなる。
B - Light It Up
問題文を読むとはじめは難しそうと思ったけど、結局、明かりを持っていない人と1番近い明かりを持っている人との距離の最大値を求めるという割りと簡単そうな問題だった。
明かりに照らされるためには、少なくとも明かりを持っていない人と明かりを持っている人との距離以上の明かりの強さが必要。最小値を求めるので明るさは距離と同じであればいい。
NやKは高々1000程度なので2重ループでも十分高速に解ける。
明かりを持っていない人毎に明かりを持っている人との距離の最小値を求める。 N-K人分の求めた距離の内、最大値を計算して答えれば良い。 要するに計算した最小値の中から最大値を答えれば良い。
C - ±1 Operation 1
XとXに一番近い等比数列の項との距離を答える問題。
Xが数列の1番小さい数値より小さい（1番大きい数値より大きい）場合は、1番小さい値との距離（1番大きい値との距離）を計算して答えればいい。
Xが数列の最大値と最小値の間にある時がちょっと難しい。
公差がDということは数列の値はAだけずらすとDの倍数になる（等比数列の後の値はA＋Dx）。
なので、XをAだけずらしてD割った余りを計算して、余りがDか0になるまで「操作」を行えば、行った回数が答えになる。
と言う考察をして実装したけど一部がWAになって困った。Dの範囲はとO(N)でもなんとかTLEしなさそうなので、Xが数列の最大値と最小値の間にある時は愚直に確認してみることにした。
それでなんとかACできたけど、C問題の割に時間がかかってWAもちょっと多かった。
D - ±1 Operation 2
数列の各項とXとの距離の合計を答える問題。
愚直に解こうとするとO(NQ)になって、数列の長さ(N)と質問の数(Q)がなのでTLEしそう。
質問の数的に各質問をO(1)とかO(logN)くらいで答えられないとTLEしそう。
あと、数列Aの順番は重要じゃないのでソートしておいたほうが都合が良さそう。
愚直に計算するのはダメそうなので、Xの値によって答えの推移になにか規則性があるのかと思って規則性の考察ばかりしてた。XがAの最小値や最大値の外側だと規則性があるけど数列Aの最大値・最小値に挟まれる場合は不規則に変わっていくので規則性を探して数式化してっていうのは結局無理そう。
解説をみたけど、結局は愚直に解きつつ式変形と累積和の事前計算で答える問題だったっぽい。
そもそも解く方針が間違ってたみたい。
