永続データ構造っていうのは"クエリとかが来て状態が変更された後も,変更される前の構造にアクセスできる"みたいな感じのやつ. 永続segtreeの例としては,まず普通のsegtreeとしてRMQがあるわけだけど,そのクエリとして, 1:"クエリxの直前の状態での"[l,r)のm…

RBSTの実装をした. struct RBSTとするとよくわからんバグが起こるし,カプセル化する意味も特にないと思ったのでグローバルにした. struct node{ //node of RBST int val,mn,size; node *lch,*rch; node(int v){ val=mn=v; size=1; lch=0,rch=0; } }; typedef…

年内に解くぞとか言ってたら普通に通ってしまった. やるだけ. 以下ネタバレ. x=y=z=0の時以外はfもgも全単射じゃないとダメ.そうすると写像(置換)の合成が群になるので,条件は,左に乗る写像をf,右をgとすると, これを, こうして, こうじゃ bijなのでhをきめ…

前日: CODE FESTIVAL 上海ツアー 3日目 - sigma425のブログちゃんと10:00に起きて飯を食う.夜更かししていた他の人たちも起きているのを確認する.でもyosupoがいないな・・・?→ちょっと遅れて来た.もっと寝坊したら面白かったのになあ.今日は帰るだけだった.…

前日:CODE FESTIVAL 上海ツアー 2日目 - sigma425のブログ10:00に起きる.本屋に行くタイミングどころか朝飯を食うタイミングも失う.かなC.昼飯.結構美味しかった.上海市内観光.レーザーを射出してきて「レーザーレーザー」と騒いでくる客引きがいっぱいいる.…

1日目 CODE FESTIVAL 上海ツアー 0~1日目 - sigma425のブログ10:00 起きる,飯.パインジュースが美味かった 10:30 バス出発予定.よすぽが遅れる.パンチ. 11:30 飯.中華料理.昨日よりは美味しかったがやはり見た目と味が一致しない(見た目より甘いものが多い).…

0日目(12/19) 金曜日の授業に出た後,中高の数研の忘年会に参加する.相変わらずの害活っぷりだった.久々の人に会えて楽しかった.22時位に帰宅.月曜提出のレポートの存在を教えてもらう.スルーして寝る.1日目(12/20) 4:40に起きる.旅行の準備をしてレポート問…

Misere(正しくはMisère) Game とは,(多分)"最後の一個をとったら負け"みたいなゲームの事で,例えばNimに対して Misere Nimというものが考えられる. Nimの勝利条件がNimber(Grundy number)であることはwell known factだが,Misere Nimの勝利条件を知らなかっ…

n( 回復薬がP(dp[i][j]="i回攻撃受けた時点での回復薬使用状況(bit)がjの時の体力のmax"を持てば良さそう.それぞれの状態からどの回復薬のsubsetを使うか、を考えるとO(n*P*3^P)となり死亡. よく考えると、回復薬aとbを使いたいときはaを使った状態を(その回…

上から,反省もこめて Merry Christmas(2251)☆ transitiveDAGの二部マッチングのアレReverse Sort(2443) 半分探索,知らなかったので勉強になった ちなみに始め単にdfsという解法に固執しまくっていて2443という数字を覚えてしまい、後日(Code Formula?)snuke…

自前構造体のsetとかにcompareを入れたい時 struct a{ int x; bool operator <(const a& st) const { return x

不参加 A:やるだけ B:過去のある範囲maxのDP→segtree C:{0,-1,+2,-3}(mod 4)とかで部分和で全種類出てくる C気づかないのが幼稚園児 A.cpp #include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional></functional></cstring></algorithm></stack></deque></queue></map></set></vector></cstdio></iostream>…

別解を友人に教えてもらった 1.逆からunionfind 2.Euler tour + BIT + doubling については http://sigma425.hatenablog.com/entry/2014/08/05/232421の通り.3.(new) Euler tour + segtree それぞれのノードは"marked ancestorの候補"を持っている. 更新クエ…

タイトルが長いK4PC( http://k4pc.contest.atcoder.jp/ )に参加しました,問題が割と面白かった. 開始直前にパソコンが再起動を始めてしまい5分位遅れてスタート.A~Eの5完で21位でした(5500点最下位).A:差の和/2 #include <iostream> #include <cstdio> #include <vector> #include <set> #in</set></vector></cstdio></iostream>…

楽しかった(小並感)予選:最近CODEなんとか多いなあ,くらいの認識本選:何日か前から書道とかDDRとか太鼓とかいろいろ発表されててやばさを感じる1日目: 7:00起き,眠い 会場につく,でかい,すごそう コンテスト 自明担当のA～Eを通した後、Fをすごくゆっくり通…

building blocks(15th POI) 別にスライドじゃなくても、集合からN個くらい数が入ったり消えたりするときのk番目の値を答えられる 1.まず座標圧縮 2.segtreeでカウントする 3.にぶたんだが,毎回sumを使うとlogが2回かかる.segtreeなんだから配列の値を足して…

蟻本での最小費用流の扱い方としては, 1.毎回Bellman-Fordで残余グラフ上を見る 2.ポテンシャルhを考えるとdijkstraで出来る 3.(column)負辺ののぞき方紹介(使う本数が必ず等しい場合,負辺を流しきったと考えた時の変形,あとはBellman-Fordを使おうとも書い…

問題:CombinationLockDiv1 概要:0~9からなる長さn(解答 +++++ .--.. は +..++ に, +++.. .---- は +..-- にできるので、overlapしなくてよいことがわかる.(styleがずれるのでなにもないところに.を入れた) よって、dp[i][j][k]で、i個目で,k==0なら+を,1なら…

SRM 629: o-- +0/-0 +217.48 (140th)Med 全然間に合わんかった…実装がむずい でもよく考えるとn #include <iostream> #include <vector> #include <algorithm> #define rep(i,n) for(int i=0;i</algorithm></vector></iostream>

全然駄目でした(A,Cの2完) A:ついこないだTo_string関数を自分で書いた(ostringstreamを使う)ので覚えていた、多言語だとより簡単?B:問題文読解が激ムズ、ここまで悪意のある問題文は普通書けない.明らかにこのセットの中で一番むずい.かぶりん死ね(かぶりん…

つらい・・・ミス: A:ループ終える地点をミスる B:根付き木のdfsだからメモ化してなかったけど辺が重複していた C:純粋に解くのが遅いメモ: A:適当に手元でテスト B: Trie木の実装としては、通し番号を付けるのは同じだが struct trieの中でstruct nodeの配…

問題:RandomGCD 概要 low以上high以下の整数をn個並べてできる(high-low+1)^n個の数列のうち,gcdがkであるものの個数をmod1e9+7で求めよ 1自分の解法: さすがに包除原理やるだけ…。まず全体をkで割るみたいなことをしておく.後は包除原理をするだけだが、全…

問題:PieOrDolphin 概要:n(解説:editorial参照ミス: edge e=G[i][j]; e.to=x; みたいなことをしていたが、&eにしなきゃだめsegmentation faultは範囲外アクセス,深すぎるdfsなど。 後者はloopが起こりうるときにvisitedなどで対策してない場合に起こる単にザ…

問題: N頂点の根付き木,Q個のクエリ クエリM v:頂点vを塗る クエリQ v:頂点v以上で塗られている最も近いindexを答える はじめは頂点1(root)だけが塗られている N,Q文句: 問題文が意味不明(説明が足りなすぎる) クエリQの原文は Q v: (Query) Print the index…

http://codeforces.com/contest/453 A:やるだけ STLのpow使うという発想が無かった(雑魚) B:bitDP.dp[i][j]=i番目までで2~53の16個の素数を素因数に持つものを既に使った時のそこまでのsumの最小 計算量的に辛いため先にseni[i][j]=bit状態iから数字jを選ん…

問題:GoodCompanyDivOne 概要: n ある条件:どの頂点を選んでも、その頂点とその直接の子たち(departmentと呼ぶ)からそれぞれ1つ仕事を選んで、それらが全て異なるようにできる.(頂点を選んだ後に仕事を選んで良いことに注意)解法: departmentの最大の大きさ…

問題:NegativeGraphDiv1 概要: 頂点数n( 解法: chargesがでかいので、上手く割り振ったりするのはむずそう,ダブリング?重みを負に出来る回数k回とj回のデータからk+j回のデータがほしい. a->bに1回以下使って行くときのコスト最小を行列で持つ 合成演算は掛…

Class:getMinimumInversions 問題概要:n( 解答: dfs適当にやって良い,InversionはBITでできる(Vの値の方で持つ)のだが、dfsの引数にvectorint bitとかを持って中でbit2を宣言してコピーして再帰とかするとコピーコストが大量にかかって死にます(死にました) …

SRM[200π] Easy:DivisorsPower 問題概要: 2以上1e18以下の整数xが与えられるので、nの(nの正の約数の個数)乗=xになるnを返せ ない場合は-1解法: i乗根とってやるだけ…と思っていたら落ちた 原因はdoubleがlong long intを表現しきれないことで、doubleは64bi…

問題概要:頂点数N( 解答:にぶたん+01dijkstra "重さwまでの辺を使っていいことにした時、1からNへ残りK本付け加えて辿り着けるなら答えはw以下"なので、wでにぶたん実は01dijkstra書いたことなかった どちらかというとdijkstraというよりかbfsだが、 if(d[e.…