解きました 以下ネタバレ

なんかぱっとわかんないのでメモ 条件A,B,C..があって,AUBUCを求めたい時に使うというのが基本 何が嬉しいかというと計算すべきものが全て何個かのcapになるということで,逆にcapが計算しにくいようなものだと意味が無い逆にAcapBcapCみたいなのを求めたい時…

去年と同じICPCのチームSleep(18000000);で参加していました. 13:00 微妙に遅れたら開始遅延してイェイ. 13:30 開始 前から適当に割り振って読む.A,B,C,Dあたりを読んでも解けそうなのがなかったので順位表を見ると,Lを通してるチームが合ったので読む.自明…

ARC31D 買い物上手 典型フロー.診断人さんのスライドとかを見れば良い. 割り算の最小→にぶたんは最小比全域木とかでも出てきた. {a,b,c}を全て選んだらボーナス,みたいなのは,各a,b,c..の他に{a,b,c}という頂点を作って,aやbやcからinfをそこに生やす.

New Year Contest2015 解けそうな奴を解き直した. A:やるだけ B:やるだけ C☆:直前と異なるものを挿入→初め以外割りと何でもできる D:対称位置にジャンプ→xと-xからdijkstra E: "次数がd1～dnの木 (Σdi=2*(n-1),di>0) の総数は(n-2)!/Π(di-1)! だから終わり" …

ARC埋めたら増えていくはずARC17D 区間addと区間gcd. 横との差をとっとくとaddが来ても更新が2箇所で済む.gcdは合成できるのであとは余裕. 実際のgcdはgcd(a-b,b-c,c-d...)とaのgcdなので,もういっこ実際の値を持っておくsegtreeをつくる(区間add対応の).ARC…

やっと全部通した satashunとsatosさんと自分(sigma425)で出ていました."頭文字が全員sだ""というか全員satじゃん""じゃあチーム名は3-SATで"みたいな会話があったがsatは僕のprefixではなかったことに終わってから(hogloidに言われて)気づいた. 300が解けな…

part1→baby-step giant-step - sigma425のブログ一般的な話をします. さっきの議論でこのアルゴリズムを使える条件は, ・なんか演算gがあって,元の値aからg(a)がとれる(さっきのだと,g(a)=a*x%mod z) ・その演算gは結合法則が成り立つ(g^nとか書ける) ・gを0…

はい。 PKUです3243 -- Clever Y なるmin kを(あるなら)求めよ、という問題解き方: とりあえずzを素数とします. 自然数Hを適当に取り、kをaH-bと書く(1 の両辺にをかけ、 今zが素数なのでが存在して、上と下は同値になる.よって下のようなaとbを求めれば良い…

writerをやってました。実質3問でd2は劣化版ですd2 easy: やるだけd2 med: d1 hardの劣化で、再帰O(N)で解けるのではじめN>=10000とかに設定しようとしていたが,O(N!*ちょい)になった.d1 easy: あるsubstringが条件を満たす確率を、適切な前計算をすればO(N^…

スライドk番値 - sigma425のブログでsegtreeでやる方法を書いたが,kが一定の時はもっと簡単にできる. small:小さい方からk-1個を持つ large:それ以外を持つ とすると,適当に増やしたり消したり移したりすればlogNで操作できる 中央値も同様にできるし1:2とか…

永続データ構造っていうのは"クエリとかが来て状態が変更された後も,変更される前の構造にアクセスできる"みたいな感じのやつ. 永続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>