マツシタのお勉強

ダブリング

AtCoder ABC050 C - Lining Up

問題 C: Lining Up - AtCoder Beginner Contest 050 | AtCoder 解法 「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」の並びを見てみる。 N = 5 の時 4, 2, 0, 2, 4 N = 8 の時 7, 5, 3, 1, 1, 3, 5, 7 という並びになり、同じ数字が2…

重複組合せを用いた多重ループ

問題 D: 多重ループ - AtCoder Beginner Contest 021 | AtCoder 解法 問題文の以下に注目 このプログラムの出力する答えは 1≦a1≦a2≦…≦ak≦n であるような整数の組 (a1,a2,…,ak) の個数に等しい 公式の解説に則ってこの文章を以下のように変換して考える。 「…

計算量O(N)をダブリングによってO(logN)にする D: 阿弥陀

問題 D: 阿弥陀 - AtCoder Beginner Contest 013 | AtCoder 満点解法 D回だけループさせ阿弥陀をシュミレーションするという実装もできるがTLEとなる。 よってダブリングによって計算量を小さくする。 ダブリングとは ダブリングを使ったべき乗計算はこちら…