tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

JOI合宿

2011 Dragon

二度とこんな問題は解きたくないです。 #include<stdio.h> #include<algorithm> using namespace std; pair<int,int>dat[100000]; int tx[100000]; int ty[100000]; int x[100000]; int y[100000]; int n; int p,q; pair<int,int>N[100000]; pair<int,int>M[100000]; long long segtree[3][262144]; void set</int,int></int,int></int,int></algorithm></stdio.h>…

2011 Shiritori

今いる頂点の強連結成分に入ってくる辺がなくなるまで同じ強連結成分で単語を回していって、なくなったら次の強連結成分にすすめていくだけ。 O(V^2)の強連結成分分解をO(V^2)回繰り返すこととO(E)回次どこに進めるかO(V)で調べるのでO(V^4+EV)になります。…

2008 Ruins

O(N^3)が想定だとずっと信じていたので必死に考えるも解けなかったのですが、どうやら他の人たちがみんなO(N^4)で解いていて時間的にもかなり余裕だという話を聞いたので、O(N^4)でときました。こっちは簡単。 解法としては、このコードでやったのが 左端の…

2009 Territory

みんなO(N log N)で解いているらしいですが工夫してひたすら実装してメモリ削るとBFSするだけで解けます。 基本的な方針は、まず盤面(だいたい100000*100000くらいだと思っておく)を100*100のセルたちに分割して、その中に叙位君の歩いた軌跡があるかどうか…

2009 Starry Sky

同じ記事を前に書いたらしいです。以前適当に書いて64点しか取れなかったので、本気で定数倍改善することにしました。やったことは、・イベントを毎回ソートするのをやめる ・座標圧縮の座標を毎回ソートしてきめるのをやめる ・座標でどこに配置されるかを…

2008 Belt

まわすたいぷの平面走査であることはわかりましたが、どうやってその平面走査処理するのがいいかな〜と。 各頂点を中心にしたものに対し適当に二回やったやつだとなんか処理いみふになったので、冷静に考えた結果1回ぐるぐる回せば何とかなるだろうと書いた…

2011 Apples

みんなこの問題を動的にStarry Sky木を組んでやるとか言ってますが、そんなに動的っぽくは無いと思います。とはいってもこんな特殊なSegmentTreeはじめて書いた。配列からついに逸脱した。あと、mapを使って逃げることに成功しました。 map::iterator m=M.up…

2009 Contest

不思議なGreedyがたくさん必要です。 まあ、問い合わせの国以外でなるべく沢山詰め込むときには、努力して詰め込もうとする範囲を上からおさえてやります。するとうまーい具合に通ります。本当こういうの怖い。 #include<stdio.h> #include<algorithm> using namespace std; int </algorithm></stdio.h>…

2008 Nightman

まず警備員、不審物、建物の四隅を全列挙して純粋な幾何をしてやってからWarshall-Floyd。幾何がたるいだけ。意外と内外判定に苦労する問題です。 #include<stdio.h> #include<algorithm> #include<math.h> using namespace std; double g[220][220]; int px[10]; int py[10]; int ax[50]</math.h></algorithm></stdio.h>…

2009 Chopsticks

ずいぶんと短いソースになるんですね、それから区間DPなんですが意外な形の区間DPであった。 この制約はオーダーが複数の候補になって考えるのに多少時間がかかる。 #include<stdio.h> #include<algorithm> using namespace std; int dp[301][301]; char str[301]; int main(){ i</algorithm></stdio.h>…

まとめ

とりあえず、ジャッジで正解を確認したものが増えました。なので適当にソースと解法の概要を上げておきます。2011 Bookshelf いろいろ考えると重みつき最長増加部分列になります。適当にSegtreeに入れて処理。 #include<stdio.h> #include<algorithm> using namespace std; int b</algorithm></stdio.h>…

2010 SimRoad

適当にDijkstraするプログラムをつくって実行してみたらそれなりでした。適当に乱数でも追加して沢山実行するだけの頭の悪いことをして点数をかせいでみましたが、なかなかBest組やsnukeに勝てません。残念。記録としては 1:127 2:37 3:373 4:967 5:633 当時…

2009 Starry Sky

Starry Sky木のもとになった問題なので当然Starry Sky木を使いますが、自明にO(N^2log N)が出てくるとして、問題はこれを定数倍改善しないと通らないということです。 このO(N^2 log N)は座標圧縮のところあたりが悪いのか、50点分しか取れないのでSegmentTr…

2009 Pyramid

BFSするだけ。定数が重い?(-O2を書けないとTLE(TLは5sec)する。まあ合宿はデフォで-O2がかかっているが、それでも1.5secかかる)。多分定数8をかけているところが問題。 #include<stdio.h> #include<queue> #include<algorithm> using namespace std; pair<int,pair<int,int> > dat[10000]; int bfs[3000][</int,pair<int,int></algorithm></queue></stdio.h>…