パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 273）に参加しました。
結果
A,B,Cの3問正解でした。
D問題は解き方や高速化の方針は解説と一致しているのになぜかTLEがいくつか出てACできなかった。
想定解通りの解き方しているのにTLEになるのは納得いかないなあ。
A - A Recursive Function
要するにNの階乗を出力する問題。
再帰関数を作って解くなり、ループで計算するなり好きな解き方をすれば良いと思う。 言語によっては階乗計算用の関数が用意されてそう。
B - Broken Rounding
1の位からの位まで順番に四捨五入した時の最終結果を答える問題。
四捨五入の実装が面倒くさいだけの問題。
四捨五入する位に5を足して、で割って端数を切り捨てて同じ数をかけて桁数をもとに戻していった。
C - (K+1)-th Largest Number
何回問題文を読んでもなにをどうすれば良いのか良くわからなかった。
とりあえず入力例1とその解説を読んで処理内容を推測して解いていった。
なんとなく読み取った範囲だと、
数列の項より大きい数が何種類あるのかを数えて、K種類の場合の項数を答えるっていうのをK=0～N-1まで順番に出力すれば良いっぽい。
なのでどの値が何個あるのか数えて、重複を省いて大きい順に並び替える。
ある値より大きい数の種類数がいくつかっていうのは、要するに0-indexで大きい順に何番目かということ。
結局、 K番目に大きい値が何個あるのかをK=0~N-1まで順番に出力すれば良い。
D - LRUD Instructions
高速にシミュレートして答える問題だと思う。
巨大なマス目の中に少しだけ壁がある状態で指定された行動のシミュレートを行う。
1回の行動で移動する距離がとても大きい場合があるので1マスずつのシミュレートではTLEする。
この問題の肝はたぶんこのシミュレートをどうやって高速化するのかという部分だと思う。
マス目のサイズに対して壁の量はかなり少ないので、 今いる位置から移動方向にある1番近い壁の位置を高速に求めて、壁にぶつかるから壁の手前で止まるか壁に届かないから指定された距離移動するかを判断して現在位置を更新、出力していけば良い。
今いる位置から移動方向にある1番近い壁の位置を高速に求めるのは、今いる位置と移動方向の行（または列）の壁の位置のリストから二分探索で求めれば良いと思う。
そのために行別と列別に壁の位置のリストを用意しておく。そのリストも全行、全列分用意するとメモリ不足になるので連想配列などを使って壁がある行・列だけ用意しておく。
上記をまとめると以下を繰り返す。
- 壁の座標を受け取ったときに行別と列別に壁の位置リストを作り、列番号や行番号を指定すればそのリストを参照できるようにする。
- 移動方向と移動距離を受け取ったときに、現在地をもとに移動方向に壁があるかどうかを確認
- 壁がない場合、指定された距離移動
- 壁がある場合、移動方向で1番近い壁を二分探索で探し、移動距離をもとに壁の手前まで、或いは指定された距離を移動
- 移動後の位置がマス目の外側にいかないように補正する。
公式解説の想定解法と上記の解き方は同じはずなのに、解説のサンプルコードと同じC++で実装してもTLEするテストケースがいくつか有った。納得いかないなあ。
改めて解説を読んだり自分のコードを見直してみようとは思うけど…
