PKU 3517 And Then There Was One

PKU

id:kyuridenamidaのところ（http://d.hatena.ne.jp/kyuridenamida/20110724/1311503122）にはシミュレーションでは間に合わないとか書いてありましたが間に合いました（漸化式とか知らない無知）ただ、普通にシミュレーションするんじゃなくて多少工夫しま…

2011-09-25

マクロ・typedefについて

コンテスト系その他

自分のコードを見てみると、マクロやtypedefをさも当然のように使っていてしかもその定義がないのは不親切だなあと思ったので書いておきます #include<stack> #include<queue> #include<deque> #include<numeric> #include<functional> #include<list> #include<cstdio> #include<cstring> #include<set> #include<map> #include<cstdlib> #include<cmath></cmath></cstdlib></map></set></cstring></cstdio></list></functional></numeric></deque></queue></stack>…

2011-09-18

JAG 2011 Day3

コンテスト

感想：すっごい楽しかったです大体自分のレベル〜それより上ぐらいの問題でやるだけ感もなく楽しめました英語問題でしたがいつもより英語の不快感が無かった気がします。 Japanese English??? A N,Mが小さいので全パターン試します int main(){ int n,m;sc…

2011-09-05

3250 BadHairDay

PKU

（id:Respect2Dさんの方が圧倒的に頭がいい解法です）なぜかsegtree解法しか思いつかなかった。最初はO(Nlog^2n)でやろうと思ったけど TLEで死亡しそうだったので多少工夫もし左のノードみてあったらそれをすぐ返してしまえーというだけの話だけど struct …

2011-08-20

JOI　合宿　abduction

JOI

DPでし。まず、証言から、どの向きにどういう順番で進んだかが割り出せる。その後、X成分とY成分に分解。ごにょごにょ int w,h,n; char angle[10005]; int mod=10000000; int main(){ FILE* fp=fopen("out.txt","w"); scanf("%d%d%d",&w,&h,&n); vi yoko,ta…

2011-08-20

JOI　合宿　Pyramid

JOI

DPでし。高い所からゴリゴリやります。 priority_queue使っても面白そうですがlogの分だけTimeLimitが危なそう vvi buf; vector<vp> top; int w,h,n; int main(){ FILE* fp=fopen("out.txt","w"); top.resize(3001); scanf("%d%d%d",&w,&h,&n); buf.resize(h,vi(</vp>…

2011-08-19

PKU3092 Non-divisible 2-3 Power Sums

PKU

数N( 2^a*3^bの和で表せ。ただし2^a*3^bのどれかがどれかで割りきれてはいけない探索します。メモ化しなくてもOKですまず、nが2で割りきれるとき、すべての2^a*3^bのaはa>=1なので、 n/2の場合に帰結できます。 nが2で割りきれないとき、2^a*3^bのうち一つ…

2011-08-06

KUPC 2011

コンテスト

感想：難しい！！！正直5問は解けるだろうとタカをくくっていましたが見事に打ち砕かれました 10位目指すって言ってたのが懐かしいです Problem A やるだけです。KUPCの文字をそれぞれカウント int main(){ char s[305];scanf("%s",s); int len=strlen(s);…

2011-08-05

JOI2009合宿　地域（Regions）

JOI

2分探索→葉っぱからできるだけ大きく切ります分割した数+1が地域の数になります。 int n,m; vector<vp> g; int dived=0,maxlen; int dfs(int v,int p){ //most distant from root int son=g[v].size(); if(p!=-1) --son; if(son==0) return 0; vi dist;dist.res</vp>…

2011-08-04

JOI2009合宿　DNAの合成

JOI

DP テストケース8〜10あたりだとTLEっぽくなるので想定解ではないはず O(20*LlogN) (fprintfになってるのは手動比較のため) char tmp[160000]; int main(){ FILE* fp=fopen("out.txt","w"); int n;scanf("%d",&n); scanf("%s",tmp); string make=tmp; int le…

2011-07-29

PKU 2951 Cake cutting

PKU

w*hのケーキをm個の長方形に分割。 w,h,m まあDPやるだけです 3分探索を入れてかっこつけましたが普通に3分探索しなくても通ると思います（実は毎回計算しててTLEだったので無理やり3探いれましたごめんなさい） int main(){ REP(i,21) REP(j,21) REP(k,21)…

2011-07-25

2831 Can we build this one?

PKU

http://poj.org/problem?id=2831 N村を結ぶM辺があり、最小全域木を作るそのとき、ある辺のコストがCならその辺は最小全域木に選ばれうるか、というクエリを処理する問題 id:semiexpさんの http://d.hatena.ne.jp/semiexp/20110107/1294381308 こちらの方…