日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257）に参加しました。
結果
A,B,C問題の3問正解でした。
C問題が意外と手こずって時間がだいぶなくなった。
ちょっと難しく考えすぎてた…
A - A to Z String 2
問題文の通り処理すれば良い問題。
愚直に文字列を構築してX番目の文字を出すのが無難かなと思う。問題の制約的にも十分間に合う速度で解ける。
ちょっと早く解く方法も一応ある。
XをNで割った答えと余りによってがアルファベットの何番目の文字を出力すれば良いかが決まるので、余りが0ならX/N番目のアルファベットを、余りが0以上ならX/N+1番目のアルファベットを出力すれば良い。
B - 1D Pawn
これも問題文の通りに処理すれば良い問題。
問題文に書いている操作の通りに実装してシミュレートすればQ回操作した後の状態を用意できるので、各コマの位置を出力すれば良い。
ループとか条件分岐を正しく処理できるかと言う問題だと思う。
C - Robot Takahashi
難しく考えすぎてかなり時間が掛かった問題。
結論としては、Xを決めた時に高速にf(X)を処理できる関数を作っておいて、後は線形探索でf(X)の最大値を求めれば良い。
問題文を読んで最初は2分探索かなと思ったけど、単調増加とか単調減少ではなくて、どこかまでは増加して、どこかからは減少するので違うなあってなった。
次に、上に凸の二次関数の最大値を求める問題とみて三分探索すれば答えが求められそうと思って実装してみた。
確認はしていないけど、実際は二次関数っぽい形にはなるものの極値がいくつかあるグラフになるっぽいので二次関数ではなく、三分探索も使えない。
制約的に判定をO(N)未満でできれば線形探索でも間に合うのに気づいて、線形探索で実装してみた。判定の部分は予め子供だけ、大人だけの体重のリストをソートして用意しておいて、2分探索でX未満の子供の人数やX以上の大人の人数を求められるようにして対応した。
中途半端にアルゴリズムを覚えていたのでかえって遠回りしてしまった気がする。
最初は愚直に解くのをベースに解法を考えたほうが早く解けるのかなあ。愚直で無理なら真面目に考察して使えそうなアルゴリズムを吟味してみるとか。
