トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)に参加しました。
結果
A,B,Cの3問正解でした。
C問題を難しく考えすぎてかなり時間を無駄にした。 最近まずは全探索を考えるっていう基本を忘れがちだと思った。
A - Counting Passes
問題文の通り実装して答える問題。
N人の点数が入力されるのでL点以上を取った人数を答える。
標準入力と数値の大小判定ができれば答えられる問題。
B - Minimize Abs 1
なんか変数がいっぱい出てきてなんか面倒そうだなと思った問題。
長さNの数列が入力されるから条件を満たす長さNの数列Xを出力する問題。
Xの条件がちょっとややこしい。（Yとか言う変数が急に出てくるのが悪い）
ある範囲[L,R]が指定されるので、からの距離がこの範囲の任意の値(Y)の距離以下となるような
を求めて数列Xを答える という問題。
（
となるXを答える問題。）ただし
が
の時、
となる。そうじゃないと
の時に条件を満たせなくなる。
が
のときは
は[tex:A{i}]に1番近いRかLになる。
そうじゃないとYが[tex:A{i}]に1番近いRかLの時に条件を満たせなくなる。
要するには
を最小化するYに合わせれば良い。
よって、が
かどうかを判定して、
は
かRかLのどれかを当てはめれば良い。
C - Minimize Abs 2
非負整数Dが与えられるので
を最小化する問題。
Dの制約がとなっているのでDはかなり大きくなる可能性がある。
いろいろ考えて迷走した結果かなり時間をロスしてしまった問題。
ACできる解法としては、xかyのどちらか一方を0からの範囲で全探索して、他方は
で算出する。そうやって求めたx,yをもとに
を計算していき最小値を答えとして出力する。
最初は、
Dがかなりでかいのと最小値を求める問題だったので二分探索で対応するのかなと思って解いていた。
xとかyを二分探索で探索してをどこまで小さくできるのかを探索すれば良いのかなと思って解いてた。
よくよく考えると二分探索は単調増加や単調減少する時に適応できる探索方法だけど、
今回最小化しようとしている式は単調に変化するような式じゃないから使えない。解き方を考えるときに単調性まで考慮できていればそもそも二分探索は候補に挙がらないなあ…
