6/8-6/14

月曜日から金曜日 記憶がない ラブライブ!The School Idol Movie 尊い。 μ's Fan Meeting Tour 2015〜あなたの街でラブライブ!〜 ライブビューイング てっきりライブパートをやるのかと思っていたがトークパートのみであった あと映画を見た(2回目) 尊い。…

天下一2012 予選B D問題 大爆発

ちょくだいさんにオススメされた問題 難しいのでビームサーチをする。キーは普通に残りのマスの個数でやった。large/00_doubleslash_large_00.txt というケースが強い ビーム幅は100では通らず200では通ったhttp://tenka1-2012-qualb.contest.atcoder.jp/sub…

6/1-6/7

月曜日 英語3 遅刻した気がする。来週中間とかなんとか、死。再履修という逃げ道があるため何もやる気がない。 離散構造とアルゴリズム 難しくなってきた。そろそろまじめに受けよう。 基礎集積回路 死。 火曜日 計算機アーキテクチャ 今週はちゃんと出た。…

5/25-5/29

月曜日 この日は寝不足だったため全授業が崩壊した 英語3 ちょっと遅刻した記憶がある。相も変わらずあまり面白くはない。 離散構造とアルゴリズム 正直あまり聞いていなかった、教科書を読んでいた。7割ぐらいは知っているないようだが残りの3割がなかなか…

ぽコン 感想

http://comp.yosupo.com/index.html で1.5時間のwebゲームを行いました プレイヤーが適当な数字を言って、下半分が言った数字分の点数を貰える。 多少のノイズがある(うさぎ)という感じ。詳しくはページ見てください。 サーバーは落ちずにバグも無かったです…

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で開催します!!!!各位奮ってご参加ください!!!!

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

与えられたデータの文字列についてTrie木を構築しますそのTrie木をEuler-TourしてBITを構築します Trie木の頂点ごとに、BITで対応する範囲[l, r]がどこなのかも一緒に計算しておきますその後、文字列ごとに、もう一度Trie木を潜ってその文字列の最後の頂点が…

今日の典型データ構造②

今日の典型データ構造です。N個のpairが与えられます ただしstringの長さは合計して10^6以下ですQ個の以下のクエリが与えられる k(int), x(int) が与えられる k番目のデータのintを+xする s(string) が与えられる s をprefixに持つ文字列を持つデータのintの…

最小カットについて

わっけわかんねえほど沢山の制約ドパァな問題を解く一般的なテクとして、なんかいい感じのグラフを作ったらなんかそれの最小カットが答えというのがあります最小カットで解ける問題はどんなのなのか考えてみました 頂点がたくさんあって、それを赤と青に塗り…

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

今日の典型データ構造 - よすぽの日記yosupo.hatenablog.com長さNの、bool列(全部の要素が0 or 1)に対して以下のクエリがQ個飛んでくるl, rが与えられるから, l番目~r番目の数列を切り出した時、それの転倒数を求める l, rが与えられるから, l番目~r番目の要…

今日の典型データ構造(上級編)

uwiさんから 長さNの、整数列(全部の要素が1 ~ N, 全部の要素はdistinct)に対して以下のクエリがQ個飛んでくる l, rが与えられるから, l番目~r番目の数列を切り出した時、それの転倒数を求める N = Q = 100,000 TLE2s 重要事項 僕はまだ解法を考えてないです…

今日の典型データ構造

長さNの、bool列(全部の要素が0 or 1)に対して以下のクエリがQ個飛んでくる l, rが与えられるから, l番目~r番目の数列を切り出した時、それの転倒数を求める l, rが与えられるから, l番目~r番目の要素を全部反転させる(0だったら1に, 1だったら0に) N = Q = …

RBST(Randomize Binary Search Tree)の計算量について考えてみた

RBSTは万能かつ簡潔な平衡二分木として有名ですね Q.でもこれって計算量どうなんやろ A.なんかいい感じやねんのままだとよくないかなぁと思ってちょっと考えてみました注意点として今回の記事では全部i番目というのは0-indexedです あと、スピリチュアルです…

きたまさ法メモ

T: フィボナッチ - Typical DP Contest | AtCoder僕はこれの解法の理解に非常に時間がかかりました。なので他の人もきっと時間がかかるよね?ということでメモを残しますまず数列 について となるが与えられているここでf(n) = {}となる関数f(x)を定義する(…

子から異なる2つを選ぶ感じの木DPを解くアレ

子から異なる2つを選ぶ感じの木DPを解くアレを解くテクニックを紹介します。D: Longest Path - Indeedなう(オープンコンテスト) | AtCoderとかが簡単に解けたりします頂点0を根とする根付き木について 頂点iはa[i]を持つ(a[i] >= 0) 頂点iそれぞれについて…

RUPC参加記1日目

RUPCに参加しました。1日目は立命館セットで、evimaさんとNOxさんと出ましたがーっと時系列で書くとBをevimaさんがコーディング AはNOxさんがコーディング Aが♨️したためDをevimaさんがコーディング 僕とNOxさんでAをデバッグしたら日本語読解に失敗している…

Yosupo Wettbewerb 解説

総評 お疲れ様でした。 問題タイトルが全部英語なのはデレマスの影響です 問題解説 C,D,Eの想定解は長いので後ろにまとめます A問題 Trouble Busters (面倒)100なA問題もいいかなって思った。 next_permutationを使うのが多分一番楽です。 一人ぐらい六重ル…

AA Tree

一気に書くのは面倒なのでチマチマ追加していきたい。AA Treeとは平衡二分木の一種で、赤黒木の亜種。赤黒木より実装が楽で速度はあまり変わらないらしい。http://web.eecs.umich.edu/~sugih/courses/eecs281/f11/lectures/12-AAtrees+Treaps.pdf図がわかり…

JOIOIの塔

嘘解法かも。 まず考察する。 とにかく2パターンの使い方ができるIが面倒。 仮に、IOIが爆破されたら(使用できるのがJOIだけだったら)ハジから貪欲にほいほいつくればいい。 なので、文字列中のIを何文字かJに変換し、貪欲に取るという事を考える。 Iの何文…

CF #286 Div2C/Div1A & Div2E/Div1C解説

CF #286のDiv2C/Div1AとDiv2E/Div1Cのwriterをしていました せっかくなのでこの2問について解説を書きます Div2C/Div1A 想定より難しかったようです。ごめんなさい。M=島の数=30001とします。 O(M^2)解 dp[i][j]: 今番号iの島にいて、前回距離jジャンプを行…

2015年の目標

競技プログラミングTCのレート2600CFのレート2400正直厳しいけど、1年間での†圧倒的成長†に期待なんらかの(無限人行けるものでは無い)オンサイトに行くなんらかの海外オンサイトに行く一番希望があるのは天下一かなぁ海外はまあリクのルートに期待だよね賞金…

CF284 Div1 E Stairs and Lines

Problem - E - Codeforces 本質は定数倍改善。 7個の行列をそれぞれ行列累乗して掛けるだけ

CF #284 Div1 D. Traffic Jams in the Land

lcm(2,3,4,5,6) = 60なので60個SegTreeを作れば良い seg[l][r][k] = l~rを通るのにかかる時間、ただしlに突入した時点での時刻%60はk CFはこういうのをTLE2sN=100000で出してくるの怖い