2023年01月18日 (水)[AtCoder] 精進。107 問ある ARC-A のうち最後に残った１問 ARC128-A「Gold and Silver」(茶 diff)。コンテスト当日も(#26588127 WA×6)今日も(#38133790 WA×6)、現在持っている金と銀の量を保持して、金を銀に(銀を金に)交換した方が得をする場合に金(銀)の量と取引履歴を更新していった。なんか今日の方が遅いしメモリ消費も多いし同じケースで WA になってるし、バカなの？■今日の２個目の提出 #38134402 (TLE×5)。小数の代わりに有理数を使ったら WA が１減って残りの WA が TLE に化けた。TLE の背後に WA が隠れている可能性はあるけど、たぶん考え方は間違ってないんだと思う。交換レートである A の値の上限が１ギガであるときに愚直に金銀の量を変化させていってはいけないのだ。■提出 #38140604 (AC)。現在持っている金の量と現在持っている銀を金に交換した場合の大小関係が問題なのだから、現在持っている金の量を１に固定して銀の量を金の量に対する比率で保持しても問題がない。そこから整理すると過去のある時点の A の値と現在の A の値の大小を比較するだけになって、小数や有理数で比率を保持する必要もなくなった。あとは取引履歴を記録するのに配列を複製する非効率を避けるなどした。■これが茶 diff とは信じがたい。たぶん見えていないものがあって遠回りな考え方をしてるんだと思う。たとえば過去のある時点の A と現在の A の比較ではなく隣接する２つの A の比較だけでいいらしいけどその理由とか。ともあれ現時点で ARC-A が全部埋まった。他に埋まっているものはない。次に埋まりそうなのがあと６問(279/285)である ABC-C。