マツシタのお勉強

ビット操作

空間計算量O(1)で配列内のユニークな数字を見つけるBit Manipulation: Lonely Integer

問題 n個の要素(整数)の配列が与えらる。配列内の要素はただ1つを除いて、全て2回ずつ現れる。1回のみ出現するユニークな数字を求める問題。 www.hackerrank.com 解法 この問題は、XORを用いることで空間計算量O(1)で解くことができる。 上記のように配列…

ビット操作を用いて順列を求める

どの部分の要素を既に使用したかをbitを用いて管理する

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

問題 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となる。 よってダブリングによって計算量を小さくする。 ダブリングとは ダブリングを使ったべき乗計算はこちら…

トポロジカルソートの組合せを数え上げる

問題 D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder 与えられたDAGをトポロジカルソートしてできる列の通り数を数え上げる問題。普通にトポロジカルソートすると1つの列しか作成されない。 また、全列挙(全てのノードの順列をだし、全ての有効辺を満…

フェルマーの小定理による組み合わせ計算によって経路数を数え上げる

問題 D: いろはちゃんとマス目 / Iroha and a Grid - AtCoder Beginner Contest 042 | AtCoder 解法 まず、この問題のポイントを抑える 問題のポイント 右と下にのみ移動可能なマス目の経路数の数え上げ 縦マスH, 横マスWはそれぞれ、1≦H,W≦100,000 (105) AB…

フェルマーの小定理を用いてコンビネーションを計算する

背景 nCk nCkを計算したい。(n個の中からkこ取り出す組み合わせ) nCkはnCk = n! / k! * (n - k)!となる。これを計算すれば求まる。しかし、分母のk! * (n - k)!の部分に着目した時に、nの値が大きいと値が大きすぎて計算できない。 そこで、プロコンの世界で…

繰り返し2乗法を使ったべき乗計算

繰り返し2乗法とは 繰り返し2乗法とは、べき乗計算する際に通常なら計算量O(N)かかる所をビット操作を用いてO(logN)にする手法である。 例 ば3^10を計算することを考える。 通常なら以下のようにループを10回繰り返す。 よってx^nの計算量はO(n)となる。 …

バレンタインデーの幸福度を最も高くするためにやるべき5つのステップ

問題 D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoder 解法 グループにどの女子を含ませるか決まれば、どの男子を含めるべきかは貪欲に決定される。よって以下のステップで解くことができる。 グループに含める女子を固定 幸福度が最も高くな…

動的計画法が困難なナップザック問題

問題 D: ナップサック問題 - AtCoder Beginner Contest 032 | AtCoder 解法 この問題はナップザック問題を応用したものである。入力値は以下の3つの条件のどれかが当てはまる N <= 30 のケース それぞれの荷物の価値Viが1000以下のケース それぞれの荷物の…

bit操作と深さ優先探索の全列挙を比較する

問題 http://abc045.contest.atcoder.jp/tasks/arc061_a 解き方 全列挙できるか 全ての数字と数字の間に対して、「+」を入れる場合と入れない場合で全列挙。文字列の長さがNの場合、「+」を入れることができる箇所は全部で(N - 1)個。それぞれの箇所に「+」…

初めてのビット操作を使った全探索

問題 (AtCoder ABC002 D) abc002.contest.atcoder.jp ソースコード 解説 ビット操作により全探索をする。この問題はNの数が最大でも12なので、最大でも212 = 4096通り。 候補に対して、その要素を含むか否かの2パターンを12要素分行う。 その際、その要素を…