7K4B blog

猫でも分かる何か

ABC340 に参加した感想


なんだかんだ言って精進してなくても茶色には落ちない程度の実力は保てる感ある。プログラミング技術って将棋とかに比べると劣化しづらいのかもしれない。


愚直に書いたらTLEしたのですぐにフィボナッチ的なDFSだと気づいたが、フィボナッチ的な再帰はfor文で書けるから不要みたいに暗記していたため盲点だった。一応フィボナッチ数列を解く古いライブラリは捨てずにいたので、それを修正する感じで実装してみようとしたが、バグらせてTLEした。慣れてないアルゴリズムを書くみたいなのが自分は苦手なので、今回は無理かもしれんなと努力するのを諦めて寝ていたが、OEISくらいは試してみるかと試したところ
 a(n) = n + a(floor(n/2)) + a(ceiling(n/2)) = n*floor(log_2(4n))-2^{floor(log_2(2n))}
みたいなO(1)の数式を発見(https://oeis.org/A003314)して提出したらACした(笑)一度くらい考察をすっ飛ばしてOEISの裏技的テクでACしてラクしてみたいという気持ちがあったので、思いがけずそれが達成できたのは良かった。OEISを使ったので1行しかプログラムを書いてない。
https://atcoder.jp/contests/abc340/submissions/50174845


実家。
https://atcoder.jp/contests/abc340/submissions/50177346