CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)に参加しました。

結果

A,B,C,Dの4問正解でした。

E問題が愚直な解き方でなら解けるけどTLEになるような解き方しか思いつかなかった。解けそうな気はするのにどこにどう手をつければ良いのか分からなかった。

A - New Scheme

問題文のとおりに数列が条件を満たすかどうかを判定する問題。

数列が以下の条件を満たすのかどうかを確認してYes/Noを出力する。広義単調増加だけは隣の項も見ないと判断できないので、この部分で配列外アクセスの可能性があるけど、それ以外の条件は数列の1項だけで判定できる内容になっている。

広義単調増加である
100以上675以下である
25で割り切れる

最初か最後の項が後半2つの条件を満たしているかどうかを判断し、残りの部分は0からN-1までか1からNまでの範囲でiとi+1かiとi-1を比較して広義単調増加かどうかを確認した。

B - Default Price

回転寿司でN皿食べたという設定で、N皿分の皿の色を順番に与えられるので合計金額を答える問題。皿の色はM種類＋αあり、M種類分はそれぞれ金額が設定されていて、＋α部分の色は一律で金額が設定されている。

M種類以外の色も存在するのが面倒な点だと思う。

N枚の皿に何色が何枚あるのかを集計して、M種類の皿だった場合はそれぞれのに設定された金額をもとに金額を計算し、＋α部分の色だった場合は一律で設定されている金額をもとに金額を設定した。
具体的には、連想配列でM種類の色をもとに金額を管理して金額計算字には色をもとに何円か判断した。連想配列に設定されている金額が0円だった場合、その色は＋α部分の色になるので別途一律で設定されている金額を持ってきて金額計算を行った。

C - Standings

指定された順番で人をソートする問題。

N人が $A _ {i}$ + $B _ {i}$ 回コイントスをして $A _ {i}$ 回表、 $B _ {i}$ 回裏になった場合の表になる率を降順に並べつつ、率が同じ場合は人に振られた番号が昇順になるように並び替える。

2つ要素を受け取ってboolを返す大小判定関数を用意して、通常のソートの第3引数にその関数を渡せば、その判定関数の判定結果を基にソートができる。なので、表になる率と番号を2セット受け取って大小判定する関数と、全員分のデータをまとめた配列を用意して、ソートを行って、その結果から番号を順番に出力した。

はじめに提出するとWAが4つあって、バグったのかなと思って何回か修正して再提出したけど、原因はそこじゃなくて率を計算するときの精度の問題だった。計算して小数になっている率を比較に利用すると精度の問題で誤差を含む場合にWAになると思ったので、比較の方法を少し修正してソートを行った。

結局、大小比較の関数は（A,B,番号）のタプルを2つ受け取ってbool値を返すようにしつつ、率の判定も $A _ {i} * (A _ {j} + B _ {j}) > B _ {j} * (A _ {i} + B _ {i})$ と元々の式から式変形したものを利用して割り算が発生しない形にして処理した。