【AtCoder】ABC106を解いたのでメモ【Python3】
結果と最終提出コード
解答中の心境
【A】
- 高校時代に綺麗な公式習った気がするな〜(忘れたけど
【B】
- 105まで問題文に書いているから使わせてもらうぜ!
- 1回目の提出は奇数のみっていう条件忘れてました。ハイ。
【C】
- 「5000兆とかw 1以外の数字出力すれば良いんでしょ」って何も考えずに提出して、1が出てくる例外があるのを忘れてた。2回もWAくらった...笑
【D】
- 1つずつ確かめていく処理自体はシンプルで書きやすかった。
- しかし、提出したコードには
TLE
の文字が。良く見ると条件式の値がでかい。しかし、工夫方法が分からずギブアップ。
解説やコメント
【A】
- 公式はこれだ!
(a − 1)(b − 1)
【B】
- 条件分岐で答えを直接出力する方法は頭によぎった。使ったら負けな気がして使わなかった...けど解説に書かれてた。笑
【C】
- なし
【D】
- まず、こういう2次元座標に直す発想がなかった
- さらに、累積和という方法も知らなかった paiza.hatenablog.com
- さらにさらに、二次元累積和もある(今回は未使用でも可)
得た知識
- 《累積和》というすげー方法が!(私が知らなかっただけ...?)
- 動的に累積和っぽいことをする《しゃくとり法》もある
まとめ
- D問題がサクッとできたときは基本計算回数が爆発して殺される。笑
- 武器《累積和》を手に入れた!