脳log[20230516]

2023年05月16日 (火) [AtCoder] 精進。AGC047-A「Integer Product」(水 diff)。以前に解こうとして解けなかった問題。小数部分を９桁に固定した固定小数点数として扱って、２の因数と５の因数を数えて 10 が 18 個以上作れる組み合わせを数えるというところまでは以前も考えた。いったい何がわからなかったのか。たぶん A 数列の組み合わせを考えようとして O(N^2) をどうにかする方法がわからなかったのだろう。でも考えてほしい。2 の因数も 5 の因数も 18 個までしか数える必要がない。A 数列の各要素は 18×18 の平面にプロットできる。そうすると組み合わせは 19^4 ≒ 13 万通りしかない。■提出 #41467175 (AC / 511 ms)。同じ要素を組み合わせないようにだけ注意。そこはひっかからなかったけど入力を固定小数点数化するところでバグらせて、０の数がときどき１多かったりした。こういう添字と数の変換って指を使ってよくよく数えるんだけど間違えるんだなあ。