PCK2013 予選 9
幾何ライブラリなくて焦ったけど大丈Vだった。
左端の取る点を固定して、反時計回りに取っていく。
dp[今までの頂点数][二つ前の頂点][一つ前の頂点]=面積最小値
とすると頑張って更新できる。O(N^5)
この値から、すべての答えをあらかじめ求めておく。
出力の順番を勘違いしてたので、ちょっと終盤頭悪いことになってます
#include<algorithm> #include<iostream> #include<cmath> #include<vector> #include<cstring> #include<cstdio> #include<complex> #define REP(i,m) for(int i=0;i<m;++i) #define REPN(i,m,in) for(int i=in;i<m;++i) #define ALL(t) (t).begin(),(t).end() #define fr first #define sc second #define pb push_back #define mp make_pair #define prl cerr<<__LINE__<<" is called"<<endl #define dump(x) cerr<<#x<<" = "<<x<<endl using namespace std; template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} typedef pair<int,int> pi; typedef long long lint; typedef complex<lint> P; const lint INF2=1e18; P p[50],q[50]; int n; bool cmp(const P& a,const P& b){ if(a.real()!=b.real()) return a.real()<b.real(); return a.imag()<b.imag(); } lint cross(P a,P b){ return a.real()*b.imag()-a.imag()*b.real(); } int ccw(P a,P b,P c){ b-=a;c-=a; if(cross(b,c)<0) return -1;//clockwise if(cross(b,c)>0) return 1;//counter-clockwise return 0; } lint getarea(P a,P b,P c){ return abs(cross(b-a,c-a)); } int id[55],rev[55]; lint minarea[55]; vector<int> vs[55]; lint dp[55][55][55]; int back[55][55][55]; void solve(int n,int add){ REP(i,n+1) REP(j,n+1) REP(k,n+1) dp[i][j][k]=INF2; REPN(i,n,1) { dp[2][0][i]=0; } REP(i,n+1) REP(j,n) REP(k,n) if(dp[i][j][k]<INF2){ REPN(l,n,1) if(j!=l && k!=l){ if(ccw(q[j],q[k],q[l])==1 && ccw(q[k],q[l],q[0])>=0){ lint nval=dp[i][j][k]+getarea(q[0],q[k],q[l]); if(dp[i+1][k][l]>nval){ dp[i+1][k][l]=nval; back[i+1][k][l]=j; } } } if(minarea[i]>dp[i][j][k]){ vector<int> tmp; tmp.pb(rev[k+add]); tmp.pb(rev[j+add]); int k2=k,j2=j,i2=i; while(j2!=0){ int last=back[i2][j2][k2]; k2=j2; j2=last; tmp.pb(rev[j2+add]); --i2; } minarea[i]=dp[i][j][k]; reverse(ALL(tmp)); vs[i]=tmp; } } } P prev[55]; int main(){ cin>>n; REP(i,n) cin>>p[i].real()>>p[i].imag(),q[i]=prev[i]=p[i]; REP(i,n+1) minarea[i]=INF2; sort(p,p+n,cmp); REP(i,n){ REP(j,n) if(q[i]==p[j]) id[i]=j; } REP(i,n) rev[id[i]]=i; REP(i,n){ REPN(j,n,i) q[j-i]=p[j]-p[i]; solve(n-i,i); } REPN(s,n+1,3) if(minarea[s]!=INF2){ REP(i,s){ int fail=0; REP(j,s) if(prev[vs[s][i]].imag()>prev[vs[s][j]].imag() || (prev[vs[s][i]].imag()==prev[vs[s][j]].imag() && prev[vs[s][i]].real()>prev[vs[s][j]].real())){ fail=1; } if(!fail){ rotate(vs[s].begin(),vs[s].begin()+i,vs[s].end()); break; } } } int q;cin>>q; REP(hoge,q){ int m;cin>>m; if(minarea[m]==INF2){ puts("NA"); }else{ REP(j,m) printf("%d%c",vs[m][j]+1,j==m-1?'\n':' '); } } return 0; }
個人的良問リスト
少し前から始めていた、良問だなーと思った問題をひたすらリストしていったものを上げます
良問、というより解く価値のある問題、といった方が正確かもしれません
2ヶ月ごとぐらいにアップデートする予定です
問題のリンクが貼ってあり、右に白い文字で解法の要素が単語で書いて有ります(マウスで囲うと見えます)
解法の要素は自分にわかるように作ったので不明な点があるかもしれません
☆は僕が初見では解けなかった問題たちです
一部、キーワードが変なひらがなになってるのがありますが、それははてなのキーワードに引っ掛けないためです
キーワードのみではわからないのも多いと思うのでなんか気になったら聞いてください(僕は全部解いているはずです)
問題たちには偏りがあります。今のところCF,USACO,Polish OIがほとんどです
誤解を招きそうな表現-> O(N)は問題の本質部分がO(N)で解けるということを言ってて、全体の計算量がO(N)というのを示すわけではないです
http://www.codeforces.com/contest/258/problem/D 確率 DP 数学 ☆
http://www.codeforces.com/contest/193/problem/D segment木 クエリ ☆
http://www.codeforces.com/contest/121/problem/E 平方分割・クエリ
http://www.codeforces.com/contest/191/problem/D サボテングラフ ☆
http://www.codeforces.com/contest/183/problem/D DP 確率 ☆
http://community.topcoder.com/stat?c=problem_statement&pm=12378&rd=15487 貪欲 文字列 辞書順
http://community.topcoder.com/stat?c=problem_statement&pm=12379&rd=15487 DP 指数時間 ☆
http://www.usaco.org/index.php?page=viewproblem2&cpid=225 UnionFind
http://www.usaco.org/index.php?page=viewproblem2&cpid=229 O(N) しゃくとり法
http://www.usaco.org/index.php?page=viewproblem2&cpid=231 セグメント木 set クエリ
http://www.codeforces.com/contest/264/problem/D 数学 文字列 数え上げ O(N) ☆
http://www.codeforces.com/contest/264/problem/E セグメント木 LIS ☆
http://www.codeforces.com/contest/261/problem/C DP ふらくたる
http://www.codeforces.com/contest/261/problem/D LIS DP ☆
http://www.codeforces.com/contest/261/problem/E 素数 DP しゃくとり ☆
http://www.codeforces.com/contest/266/problem/E セグメント木 ☆
http://www.codeforces.com/contest/269/problem/D セグメント木 区間 DP
http://www.codeforces.com/contest/269/problem/C グラフ
http://main.edu.pl/en/archive/oi/19/fes 牛ゲー 不等式 最短路
http://main.edu.pl/en/archive/oi/19/lit 文字列 交換 BIT
http://main.edu.pl/en/archive/oi/19/odl 素数 グラフ 幅優先
http://main.edu.pl/en/archive/oi/19/tou グラフ lowlink 貪欲 O(N) ☆
http://main.edu.pl/en/archive/oi/19/bon 調和級すう 素数
http://main.edu.pl/en/archive/oi/19/sza DP 走査 クエリー 先読み
http://main.edu.pl/en/archive/oi/19/squ 貪欲 ☆
http://main.edu.pl/en/archive/oi/19/wyr 貪欲 数学 階差 ☆
http://joi2013ho.contest.atcoder.jp/tasks/joi2013ho4 二分探索 文字列 ☆
http://joi2013ho.contest.atcoder.jp/tasks/joi2013ho5 セグメント木 平面 ☆
http://main.edu.pl/en/archive/oi/19/hur 貪欲 セグメント木
http://community.topcoder.com/stat?c=problem_statement&pm=12364&rd=15488 DFS 数え上げ ☆
http://www.codeforces.com/contest/273/problem/C グラフ 貪欲 ☆
http://www.codeforces.com/contest/273/problem/D 数え上げ DP imos法 ☆
http://www.codeforces.com/contest/273/problem/E DP ゲーム Nim 埋め込み
http://www.usaco.org/index.php?page=viewproblem2&cpid=248 imos法
http://www.usaco.org/index.php?page=viewproblem2&cpid=249 DP 実装注意
http://main.edu.pl/en/archive/oi/19/pre 貪欲 しゃくとり 文字列 ハッシュ☆
http://main.edu.pl/en/archive/oi/18/kon 貪欲 グラフ 数え上げ ☆
http://main.edu.pl/en/archive/oi/18/pio スタック 二分探索 ☆
http://main.edu.pl/en/archive/oi/15/pod 高速化 指数時間 省メモリ
http://main.edu.pl/en/archive/oi/15/tro 幾何 数学
http://main.edu.pl/en/archive/oi/15/kup グリッド スタック ☆
http://main.edu.pl/en/archive/oi/18/prz 貪欲
http://main.edu.pl/en/archive/oi/18/sej 素因数ぶんかい imos法?
http://www.codeforces.com/contest/280/status/D セグメント木 ☆
http://main.edu.pl/en/archive/oi/18/rot 木 logマージ BIT ☆
- 追加 5/5
http://www.codeforces.com/contest/280/problem/C 木 確率
http://main.edu.pl/en/archive/oi/18/imp 貪欲 ☆
http://main.edu.pl/en/archive/oi/18/met BIT 二分探索
http://main.edu.pl/en/archive/oi/18/pro フロー 貪欲 X最小費用流 ☆
http://main.edu.pl/en/archive/oi/17/kor 調和きゅうすう ローリングハッシュ
http://www.codeforces.com/contest/283/problem/C DP
http://www.codeforces.com/contest/283/problem/E セグメント木 数え上げ ☆
http://joisc2013-day3.contest.atcoder.jp/tasks/joisc2013_cake 分割統治 実はO(NlogN) or セグメント木 ☆
http://joisc2013-day1.contest.atcoder.jp/tasks/joisc2013_communication グラフ 木 Union-find 隣り合ったものがすべて繋がっていればOK ☆
http://joisc2013-day1.contest.atcoder.jp/tasks/joisc2013_collecting セグメント木 包除 数え上げ
http://joisc2013-day2.contest.atcoder.jp/tasks/joisc2013_mascots DP 数え上げ 縦に伸ばす・横に伸ばす のみで十分
http://main.edu.pl/en/archive/oi/17/klo O(N) ☆ 取りうるものは階段上になる一部のみ
http://www.codeforces.com/contest/277/problem/E 最小費用流 O(N^3logN)
http://main.edu.pl/en/archive/oi/17/owc 円環 しゃくとり DP O(N^3)
http://main.edu.pl/en/archive/oi/17/tel 貪欲 グラフ O(N+M) ☆
http://www.codeforces.com/contest/286/problem/A 実験 O(N)
http://www.codeforces.com/contest/286/problem/B 調和きゅうすう ほとんどの場所は動かない O(NlogN)
http://www.codeforces.com/contest/286/problem/D 区間 重複を取り除く->イベント O*1
http://main.edu.pl/en/archive/oi/16/gas 木 貪欲 葉から貪欲に切り離す O(NK)
http://main.edu.pl/en/archive/oi/16/baj 回文の中心を決めて、幅優先。2ステップ一気にやろうとするとTLE O(NM+DM)
http://main.edu.pl/en/archive/oi/16/kon DP 1ステップに複数の移動候補がある方が、却ってメモリ面で優秀 O(N^2K)
http://main.edu.pl/en/archive/oi/16/arc リスト 省メモリ STD::リスト使える (広義)減少列に分割して、それぞれのステップで消すのは最初の減少列の最後 いれれーたで頑張る ☆
http://main.edu.pl/en/archive/oi/16/lyz セグメント木 ある区間の和が、区間の長さをD増やしても入らないならOUT と言い換えられる O((n+m)log n) ☆
http://main.edu.pl/en/archive/oi/16/slw 文字列 検索 貪欲? f^k(0)に含まれるなら、f^(k-1)(0)で 求められる文字列も定まる これをk=0になるまで繰り返す。途中で0が挟まったりするとアウト ☆
http://main.edu.pl/en/archive/oi/16/wsp 幾何 貪欲 スタック ある街からは、そこから一番首都側にいける辺以外は使う必要がない 最初は円環状に回るのをどんどんショートカットしていく感じ O(n+mlogm) ☆
http://main.edu.pl/en/archive/oi/15/blo dfs lowlink 関節点のみ、自明コスト以外に足す必要がある low[dst]>=pre[v] のとき、dstの先は上に戻れないので、通る必要のある組み合わせをたす O(E)
http://main.edu.pl/en/archive/oi/15/rob BFS imos法 タコ型状なので、上と下に分割する。上に凸な三角形っぽいものに分割すると、上から平面走査していき、一番後まで邪魔になるのは一番下にあるX これを利用してimos法などを使い、どこに入れないかを求める。 あとはBFSだけ O(N^2) ☆
http://main.edu.pl/en/archive/oi/15/bbb デック スライド最小値 累積和 k回revolveした時を考えると、その時預金額が最も少ないときから、いくつ変更するかが分かる O(N)
http://www.codeforces.com/contest/295/problem/D 数え上げ DP imos法 dp[高さ][幅] で、ピラミッド状の形をいくつ作れるかを数える 遷移で、一次関数状に値が増える感じの足し方をするが、imos法を2回やればOK caveの形は、最後の膨らんだところで分割して、ここでも多重imos法を使ってがんばる O(NM)
http://www.codeforces.com/contest/295/problem/E DP セグメント木 座標圧縮 列で持たずに、どこの場所がONになってるかを考える 更新も、(左ノードのコスト)+(左ノードが左の右端まで行く値)*(左ノードの数)+(左ノードの数)(右ノードの数)(左と右の間隙) ... のようにすればいける O(MlogN)
http://www.codeforces.com/contest/150/problem/E 木 セグメント木 重心分解 二分探索 定数倍 中央値k以上にできるか、という二分探索をする。 パスの中で、上方に寄与する辺が半分以上ならよい。 重心分解をして、重心からの距離がある範囲の中で最大に上方に寄与する頂点を求めたくなる。これはセグメント木で実現できる O(Nlog^3n) logはひとつ外れる。
http://main.edu.pl/en/archive/oi/14/drz セグメント木 コスト付けで問題になるのは それ自体の値、左、右の値 交換先の木の高さをxとして隣接する2つのコストの和のグラフを作ると、3つのパートから成る。 木の高さでソートし、 常に、交換相手にとって交換する木が、3つのパートのどこに位置するかを持っておく。 また、交換する木にとって相手が3つのどのパートにあるかも場合分けして求める。 これらをセグメント木を使って行う。 端の場合・隣接する2つを交換する場合に注意。 O(NlogN)
http://main.edu.pl/en/archive/oi/14/grz φ関数 整数 φ(k)*(a/k)*(b/k) の合計を求めることになる。 kを1...√b まで調べ、そのあとはb/kの値別に、kが√b以上のものを調べる。 O(N*B^0.5)
http://main.edu.pl/en/archive/oi/14/grz 素因数ぶんかい 文字列 クエリ 長さLの範囲のとき、Lの素因数について独立に切れるかどうか考えればよい また、Kの長さでに切れるかどうかは、 [0,L-K)==[K,L)を調べればよい O(NloglogN+QlogN)
POIとかむっちゃ難しいのでちゅうい
良問の基準も人によって違うので注意しましょう 僕は比較的甘いほうだと思うのでそこまで良くないのも混ざってるかもしれません
*1:Q+N)*log(Q+N
Codeforces #165 div1-D Maximum Waterfall
http://www.codeforces.com/contest/269/problem/D
問題概要
高さ、左端、右端の決まった棚がN個ある。
i番目の棚の高さ、左端、右端をそれぞれhi,li,riとおく。
ある棚iから、ある棚jに水を流せる時、
- max(li,lj)<min(ri,rj) つまり棚iと棚jが上から見た時重なっていて、
- hj<hi で
- 棚iから棚kに水を流せて、棚kから棚jへ水を流せるようなkが存在しない
という3つが満たされている。
ある棚iからある棚jに水を流すとき、流せる量は、min(ri,rj)-max(li,lj)
最も上の長さが無限の棚から、最も下の長さが無限の棚に、なるべく多く一本の水を流したい
水を流す経路の流量は、棚から棚へ流せる水の量の最小値
流せる水の最大値を求めよ
N<=10^5
|li,ri|<=10^9
hi<=10^9
方針
左右の座標の値をまずは圧縮
棚を下から順番に見ていく
dp[i]:=棚iから水を流すときの流せる水の最大値
棚iの範囲で、棚iより下の棚たちを見下ろした時に見える棚(棚jとおく)すべてについて、
棚jに棚iから水を下ろせるか考える。
棚jに水を下ろせるのは、棚iの範囲とかぶっている棚jの範囲がすべて見えるとき
この時、dp[i]=max(dp[i],min(dp[j],(iとjの被っている部分の長さ)))
と更新できる。
更新が終わったら、上から見た時に見える棚に棚iを追加する
上から見た時に見える棚の管理には、set<pair<int,int> >などを使えばできる
dp[最も上の棚の番号] が答え
棚iから下へ見える棚は最大N個有りそうなので、O(N^2)かO(N^2logN)のような気がするが、
もしある区間を見下ろせたなら、その区間はiによって覆われるので棚iによってしか見下ろされない
更新が終わると、棚iの区間、棚iの両側にもともとあり、途切れることとなった区間 の3つが追加される
区間は1回しか見下ろされないので、O(N * logN)ぐらいで終了する。
下のコードのdoitは、上の方針と少し違い、
[l,r)の範囲で最も上にある区間をセグメント木により探し、その区間で更新できるか調べ、
最も上にある区間以外の残りの範囲について再帰的に調べています
実装量は多いですが挿入削除の面倒なことが少ないかと思います
using namespace std; static const int INF =1000000005; template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} typedef long long int lint; typedef pair<int,int> pi; struct segtree{ int val[800005],all[800005]; int n; void init(int n_){ n=1; while(n<n_) n<<=1; for(int i=0;i<n*2;++i) val[i]=-1,all[i]=-1; } int query(int a,int b,int i,int l,int r){ if(a<=l && r<=b) return val[i]; if(b<=l || r<=a) return -1; int md=(l+r)>>1; if(all[i]!=-1){ all[i*2+1]=all[i*2+2]=val[i*2+1]=val[i*2+2]=all[i]; all[i]=-1; } return max(query(a,b,i*2+1,l,md),query(a,b,i*2+2,md,r)); } void set(int a,int b,int i,int l,int r,int v){ if(a<=l && r<=b){ val[i]=v; all[i]=v; return; } if(b<=l || r<=a) return; int md=(l+r)>>1; if(all[i]!=-1){ all[i*2+1]=all[i*2+2]=val[i*2+1]=val[i*2+2]=all[i]; all[i]=-1; } set(a,b,i*2+1,l,md,v); set(a,b,i*2+2,md,r,v); val[i]=max(val[i*2+1],val[i*2+2]); } }; segtree seg; pair<int,pi> wall[100005]; int zip[200005]; int n,t; int dp[100005]; void doit(int l,int r,int who,int excL=1,int excR=1){ //excL/excR 左/右に伸びていてよいかどうか(1ならOK) int id=seg.query(l,r,0,0,seg.n); if(id==-1){//最も下の棚専用 seg.set(l,r,0,0,seg.n,who); dp[who]=zip[r]-zip[l]; return; } int l2=wall[id].second.first,r2=wall[id].second.second; if(!(l2<l && excL==0) && !(r<r2 && excR==0)){ dp[who]=max(dp[who],min(dp[id],min(zip[r],zip[r2])-max(zip[l],zip[l2]))); } if(l<l2) doit(l,l2,who,excL,0); if(r2<r) doit(r2,r,who,0,excR); } int main(){ scanf("%d%d",&n,&t); for(int i=0;i<n;++i){ int a,b,h;scanf("%d%d%d",&h,&a,&b); zip[i*2]=a; zip[i*2+1]=b; wall[i]=make_pair(h,make_pair(a,b)); } zip[n*2]=-INF; zip[n*2+1]=INF; sort(zip,zip+n*2+2); int zn=unique(zip,zip+n*2+2)-zip; wall[n++]=make_pair(0,make_pair(-INF,INF)); wall[n++]=make_pair(t,make_pair(-INF,INF)); for(int i=0;i<n;++i){ wall[i].second.first=lower_bound(zip,zip+zn,wall[i].second.first)-zip; wall[i].second.second=lower_bound(zip,zip+zn,wall[i].second.second)-zip; } sort(wall,wall+n); seg.init(zn); for(int i=0;i<n;++i){ int h=wall[i].first,l=wall[i].second.first,r=wall[i].second.second; doit(l,r,i); seg.set(l,r,0,0,seg.n,i); } printf("%d\n",dp[n-1]); return 0; }
Codeforces #165 div1-C,div2-E Flawed Flow
http://www.codeforces.com/contest/269/problem/C
問題概要
N頂点、M辺のグラフが与えられ、頂点1がソース、Nがシンクである
ソースからシンクへの最大フローを流した時の、辺に流れた流量が辺ごとに与えられる(向きは与えられない)
フローが成り立つようにそれぞれの辺について向きを決めよ
ただし、得られるフローはサイクルを含んではいけない
グラフは連結で、答えは必ず存在する
N,M<=2*10^5
1<=流量<=10^4
方針
サイクルを含まないので、得られるフローのグラフは、トポロジカル順序をつけることが出来る。
ソースは最も順序の早い点で、そこから出る辺はすべてソースと逆向きに流れている
ここで、ソースに隣接する点のうち、どれかはトポロジカル順序がソースの次に小さいはずである
トポロジカル順序がソースの次に小さい頂点をvと置くと、vにはソース以外からフローが流れこまないので、
ソースから向かう辺の流量と、それ以外のつながれた辺の流量が等しいはず
逆に、ソース->vの辺以外はvから流れださなければフローが成立しないので、
ソースの時と同様にvから流す
残った頂点の中でトポロジカル順序が最も早いものが必ず見つかるはずなので、これを繰り返せば答えが求まる。
ソース、シンクの扱いに注意
O(N+M)
using namespace std; static const int INF =500000000; template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} typedef long long int lint; typedef pair<int,int> pi; int n,m; vector<pair<pi,pi> > g[200005]; int in[200005],flow[200005]; int vis[200005]; int ans[200005]; int main(){ scanf("%d%d",&n,&m); for(int i=0;i<m;++i){ int a,b,c;scanf("%d%d%d",&a,&b,&c);--a;--b; g[a].push_back(make_pair(make_pair(b,c),make_pair(0,i))); g[b].push_back(make_pair(make_pair(a,c),make_pair(1,i))); flow[a]+=c; flow[b]+=c; } memset(ans,-1,sizeof(ans)); queue<int> q;q.push(0); while(!q.empty()){ int v=q.front();q.pop(); vis[v]=1; for(int i=0;i<g[v].size();++i){ pair<pi,pi>& e=g[v][i]; if(vis[e.first.first]) continue; in[e.first.first]+=e.first.second; ans[e.second.second]=e.second.first; if(in[e.first.first]==flow[e.first.first]/2 && e.first.first!=n-1) q.push(e.first.first); } } for(int i=0;i<m;++i) printf("%d\n",ans[i]); return 0; }
Codeforces #165 div1-A,div2-C Magical Boxes
http://www.codeforces.com/contest/269/problem/A
問題概要
N種類の大きさの箱がある。
i番目の箱の大きさは2^k(i)で、a(i)個ある。
新しく2^pの大きさの箱を作って、それにすべての元の箱を詰めたい。
ある箱には、それより小さい大きさの箱を、半分の大きさなら4個、1/4の大きさなら16個、というように詰めることができ、入れ子状に詰めることも出来る。
ある箱に、サイズの異なる箱を詰めることも出来る(半分の大きさの箱1つ、1/4の大きさの箱12個 のように)
pの最小値を求めよ
N<=10^5 a,k<=10^9
方針
ある箱が入れ子状に詰められているとしても、
サイズごとに、互いに干渉しない箱を別々に新しい箱に詰めている、とみなすことができる
なので、それぞれのサイズについて、箱を詰めることが出来る最小のサイズを求め、maxを取る。
サイズ2^k(i)のa(i)個の箱が詰まる最小のサイズは、2^(p-k(i))>=a(i)を満たす最小のp
ただし、p>k(i)
O(N*log a)
int n; pair<int,int> box[100005]; int main(){ cin>>n; int res=0; for(int i=0;i<n;++i){ scanf("%d%d",&box[i].first,&box[i].second); if(box[i].second==1) res=max(res,box[i].first+1); else{ while(box[i].second>1){ box[i].second=(box[i].second+3)/4; ++box[i].first; } res=max(res,box[i].first); } } printf("%d\n",res); return 0; }
POJ Solved Graph
PKUのアカウントのsolvedを横軸時間、縦軸solvedのグラフにして表示します。
複数アカウントに対応しています。名前を入れるところに、コロン(',')区切りで空白などを入れずに複数のアカウントを入力してください
ボタンを押すと、その時のウィンドウのサイズに合わせてグラフを作ります
ページ読み込みに結構時間がかかるので、マッタリ待ちましょう。合計solvedが4000とか行くようだと1分弱かかります
同じディレクトリに、page.htmlというファイルを作りますが気にしなくていいです。プログラムを終了したら削除しても問題無いです
サイズを変更すると勝手に大きさを変えてくれます
Windows用です また、.NET Framework 4が必要です
リンク:
https://docs.google.com/open?id=0B4bMtJgy4TSHZzR2RU5BWGNTQzQ
グラフの例:
Last updated:2013/1/9
制作言語はC#です
セグメント木 問題集
https://twitter.com/hogloid/status/284225774142251008
こんなことを言ったので
書きます
問題は、セグメント木を使う解法がおそらく楽で、セグメント木が問題の重要な部分で、JOIとかPCKでない問題、とします(JOIの問題とかみんな知ってる&解いてるだろうし)
あと、明確に悪問と分かる問題は載せません。
解説が欲しい場合は、(一応僕は全部解いたので)僕になにか言ってくれると解説ページを開設すると思います。下のコメント欄とかにどうぞ。
記事を出してからも、ボチボチ更新していく予定です。
☆の数は、主観的な難易度です。
書き終わって気づきましたがかなりグロイ問題ばかりなのでやばいですが頑張ってください
似たような記事 http://d.hatena.ne.jp/tozangezan/20111111/1320993464
(こっちのほうが、おそらく簡単な問題が多いです 問題はかぶってないはずです)
☆
- Sliding Window http://poj.org/problem?id=2823
☆☆
- タコヤキオイシクナール http://arc008.contest.atcoder.jp/tasks/arc008_4
☆☆☆
- Lucky Arrays http://www.codeforces.com/problemset/problem/256/E
- XOR on Segment http://www.codeforces.com/problemset/problem/242/E
- Running Away From the Barn http://www.usaco.org/index.php?page=viewproblem2&cpid=213
- Mars Map http://www.spoj.com/OI/problems/NKMARS/
- Mushroom Gnomes -2 http://www.codeforces.com/problemset/problem/138/C
- Flying Right http://poj.org/problem?id=3038
- Dungeon (I) http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1505
- Thwarting Demonstrations http://www.codeforces.com/problemset/problem/191/E
☆☆☆☆
- Little Elephant And Tree http://www.codeforces.com/problemset/problem/258/E
- TorCoder http://www.codeforces.com/problemset/problem/240/F
- Little Elephant and Inversions http://www.codeforces.com/problemset/problem/220/E
- PrimeCompositeGame http://community.topcoder.com/stat?c=problem_statement&pm=11506
- Team Selection http://www.spoj.com/OI/problems/NKTEAM/
- Cartesian Tree http://poj.org/problem?id=2201
- Quadrant Queries https://www.interviewstreet.com/challenges/dashboard/#problem/4e48b9cb8917f
- Differece is Beautiful http://poj.org/problem?id=3419
- Two Permutations http://www.codeforces.com/problemset/problem/213/E
- Donkey and Stars http://www.codeforces.com/problemset/problem/249/D (Math含む)
- Dividing Kingdom http://www.codeforces.com/contest/260/problem/E(面倒 セグメント木使わなくてもできる)
- Cubes http://www.codeforces.com/contest/243/problem/D
- Camping Groups http://www.codeforces.com/problemset/problem/173/E
☆☆☆☆☆
- Fence http://www.codeforces.com/problemset/problem/232/D (セグメント木分少なめ)
- Alien DNA http://www.codeforces.com/problemset/problem/217/E
- FoxSearchingRuins http://community.topcoder.com/stat?c=problem_statement&pm=11286
- Mountains https://www.spoj.com/OI/problems/NKMOU/
- Do Use Segment Tree http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2450
- Cutting Cake http://poj.org/problem?id=2843
- Two Segments http://www.codeforces.com/contest/193/problem/E