2015-04-01から1ヶ月間の記事一覧

2015/4/20 - 2015/4/26

月曜日 英語2を寝坊した (非意図的な)寝坊は今学期初 悲しい 離散構造とアルゴリズムは2彩色をやった 火曜日 計算機アーキテクチャーはアセンブリをやった PIC32MXってMIPSだったんですね(要出典) 計算基礎論 これは面白い プロ1 forとかwhileとか 中身の記…

GCJ Round1A

A問題英語力検定。B問題1時間を(美容師の人数)分割して、i人目の美容師は(X+i/美容師の人数)時間目で切り始められるように考えればそれで二分探索が出来て終了なんか危なそうなのでBigint使ったC問題適当に尺取り

よすぽコン2解説

よすぽコン2 解説 お疲れ様でした。 A 数列swap 最初の数列の反転数をXとすると答えは max(X-K, 0) です 隣り合う要素を交換する時 左のほうが大きい -> 反転数は-1 要素の大きさは同じ -> 反転数は変化なし 右のほうが大きい -> 反転数は+1 となります また…

今日の典型データ構造5

よすぽコンテスト2

ダイクストラ高速化(RadixHeap紹介)

色々なダイクストラ高速化 from yosupo 真面目なスライド製作って実はほとんどしたことが無かったのですが、これっぽっちの分量でも疲れるものですねRadixHeapという高速なHeapの紹介スライドです結構ソースコードは文字が潰れてしまったのでslideshareの…

今日の典型データ構造4(解答編)

クエリ1で(x0, y0) ~ (x1, y1)に+1ではなく(x0, y0), (x1, y1)に+1 (x0, y1), (x1, y0)に-1にすればクエリ2は"自分より左上の点の値のsum"というのを求めるクエリに変換できますここでこれを求めるためには動的SegmentTreeに範囲sumができる平衡二分木を載せ…

今日の典型データ構造4

2次元平面に以下のクエリがQ個飛んでくる平面は格子点ごとに値を持っていて、全部最初は0 四隅の座標は全部整数のx軸y軸に平行な長方形が与えられるからその中の格子点の値を全部+1 座標が整数の点(つまり格子点)が与えられるからそこの値を求める 座標の範…

今日の典型データ構造③

今日の典型データ構造は!!!!なんと!!!!April Fool Contest 2015 on HackerRankwww.hackerrank.comで開催します!!!!各位奮ってご参加ください!!!!