hogloidのブログ

へなちょこ

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…

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>…

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のうち一つ…

KUPC 2011

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

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>…

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…

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)…

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 こちらの方…

PKU 2796 Feel Good

PKU

http://poj.org/problem?id=2796 N要素があって、その中の連続した要素の、 もっとも少ない数*その要素の合計 がもっとも大きいものを求める。ヒストグラムのアレです。 幅がありますが累積和でおk。 オーバーフローやすべての要素が0のときに注意。 typede…

PKU 2611 Gas Station Numbers

PKU

http://poj.org/problem?id=2611 今ある数字の札を使った次に大きい価格を求めます。 25、96 は変換可能まぁやるだけ 下の桁からみていって、今の桁の数より大きい数に変更できるなら、 その数に変更 後は残った数を小さくなるように置いていく int main(){ …

PKU 3262 Protecting the Flowers

PKU

TopCoderでこれ+ナップザックな問題と昔当たったので簡単 ある牛A、Bがいて、それ以外の残りの牛の破壊量/minuteをDとおくと、 破壊量はそれぞれ Aー>Bの順に処理すると Aの時間*(D+Bの破壊量)+Bの時間*D Bー>Aの順に処理すると Bの時間*(D+Aの破壊量…

PKU 1850 Code

PKU

昔やってみて集中力が持たなくてやめたのをもう一回やってみたら意外とすっきりかけました 使った文字+残りの文字数 で作ることができるすべての文字列の数を求める関数を作ります。 便宜上文字数0のとき1を返します。 int befsize(int n,int usedword){ if…

PKU 2443 Set Operation

PKU

なんか苦戦したので書きます C(i)( 数はすべて10000以下最初はソートしようかな、とか思ったけどソートすらTLEになりそう 数が1万以下なので普通に配列にもつ O(CN+QN)でいいかな?ー>TLE 数が1万以下だからあらかじめ求めておいた方が良さそう bitset初め…

Supercon予選

予選締切りがきたのでアップします 改行が入ってて読みにくいですがお許しください (はてダの仕様???) 普通のk-最短路的アルゴリズムをちょっと変更しただけです /* SuperCon 2011 予選問題C用テンプレート ・解答プログラムはこのテンプレートに従っ…

Google Code Jam Round2

GCJ

出てました Problem A. 歩道の遅いとこから走って行った方が早くなるから・・・ ソートとかしてやるだけじゃん →なんか合わない 小数の精度とかいろいろ変える →やっぱり合わない 40分も使って4WrongTryしたあげく諦める Problem B. もうなんかすごい焦って…

学園祭でのゲームとか

この前学園祭だったので、それに向けてしばらくゲームを作ったりしていました そのゲームを上げようと思います。http://www1.axfc.net/uploader/File/so/63227 DLはこちらで。 readmeに書いてありますが、細胞がうにょうにょして戦うゲームです。 僕はこうい…

Google Code Jam Qualification Round

GCJ

GCJ出てました。 Problem A Bot Trust 簡単問題 ですが何故かきれいなコードが書けない症候群(時々なる)に陥ってしばらくコードを書いては消しを繰り返し、30分ぐらいでようやく書き終わる(これが時間制限ありのコンテストで起こると焦る) 普通にサンプルとS…

PKU 1548 Robots

PKU

http://poj.org/problem?id=1548 解いてるとき日本語で解説されたソースコードがなくて困ったので書きますまず、最初は0,0の場所にいます。 もし0行目にゴミがあるなら、一番右にあるゴミまで取ります(そこまで行かなければまたそのゴミを取りにいかなけれ…

PKU 1297-supermarket

PKU

苦労したけど割と綺麗なコードも書けたし載せます最初は普通にDPやってMLEー> メモリを2回分だけとるようにしたけどTLEー> cinをscanfにしたけどWAー> printfのフォーマットを直してAC scanfはdouble型を受けとるときlfだけどprintfはfなんですね これで5…