Learning Algorithms

アルゴリズムの勉強メモ

AGC 028 D. Chords

D - Chordsまず円を直線上に展開することに気付くと,区間を $N$ 個とる問題になって区間 $dp$ っぽいことができそうな気持ちになります.連結成分を適当に分けてそれぞれ独立に数え上げることができればよさそうなことから自然に $dp(l, r) :=$ 区間 $[l, r…

AGC 032 E. Modulo Pairing

E - Modulo Pairingまず $mod\ M$ の制約を無視して考えると,数直線状で交差する二つのペアや独立したペアをとっても得することはないのでペアをすべて入れ子状にしたものが最適解の一つになります.元の問題でこれが成り立つのはいずれのペアも $x + y = m…

AGC 031 C. Differ by 1 Bit

C - Differ by 1 Bit動く回数は必ず $2^N - 1$ 回なので $a$ と $b$ の立っている $bit$ の個数の偶奇は異なることが必要です.$0...$ から $1...$ などにはきれいに移動できるので自然に分割統治をしたくなります.頂点 $S$ と $T$ が今見ている部分の半分…

QUPC G. Tapu & Tapi 2

G - Tapu & Tapi 2最終的にたぷちゃんとたぴちゃんの両方が存在するような連結成分が存在しなければOKなのでそれ以外の3つの状態をすべて持つことにします。$dp1[u] :=$ $u$ を含む連結成分にたぷちゃんもたぴちゃんも存在しないもので有効な状態にする最小…

codeFlyer 参加記

参加しました。https://beta.atcoder.jp/contests/bitflyer2018-final開始前、wifiが接続できない感じで不安でしたが、近くにnuipさんがいたおかげで安心してコンテストに臨めました。コンテスト中、ほぼすべての時間を使ってFとGを解こうとしました。Fを解…

ICPC 2018 国内予選参加記

今年も神戸大学のチームとして、アルゴリズムのプロkimiyukiさん、マラソンマッチのプロkurenai3110さん、えんぴつ画を描くのが上手な僕KokiYmgch、の3人で出ました。僕はいま東京に住んでいるので朝7時に出発して神戸大学に向かいます。ワクワク!11時半に…

全方位木dp

全方位木dpについてです。基本的にここにまとまっていて、僕自身もこの記事から学びました。本記事では、これよりもわかりやすく簡潔な実装します。名前が大げさですが、普通の木dpを少し拡張するだけです。上のサイトの例題 $1$ にもありますが、次のような…