ゴミ箱

豊かな人生を歩みたい

Introduction to Contemporary Algorithms

www.youtube.com 岩間先生の講義が京都大学のOCWで公開されていた.この先生の「アルゴリズム・サイエンス:出口からの超入門」が大好きなのでとても嬉しい. アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ 2―超入門編)作者:…

黒魔術

Bit Twiddling Hacks Bit Twiddling Hacks 色々ある基本的な操作を少ない命令数で実行できるような黒魔術を紹介しているページ. 面白そうなので少し読んでみる. Compute the sign of an integer vはint(32bit)で,vが正なら0,vが負なら-1の値を返すような…

AGC023B

メモ ナイーブに考えると,どれだけ盤面をずらすかでO(N^2),ずらした盤面が対称的か判定するのにO(N^2)で,合計O(N^4)だけ計算する必要がある. 右にA,下にBだけずらした盤面をT(A,B)と書くことにする. よく考えれば「T(A,B)が対称的⇔T(A+i,B+i)が対称的…

AGC031B

メモ 左からi番目の石の色をc[i],左からi番目までの石で色ぬりした場合の数をdp[i]とする. iからi+1の遷移を考えると,dp[i+1]は「jとi+1の間にある石を色c[i+1]で塗る(ただしc[j] = c[i+1], j < i+1)場合」と「何もしない場合」の和とわかる.前者の求め…