ICPC Japan Domestic 2014
初ICPC&実質初チームコンテスト！！！
藤原さん、phiさんと出た。UTouto@Kyoto（京都でウトウト、生成メソッド式ダジャレ）
始まる前
- 東大結構チームがあっていろんな人がいる
- wakabaが直前になっても1人しかいない（tozanは間に合ったけどevimaさんは本当に開始と同時にやってきた感じ）
- 印刷キューの先頭に立つべく教室の前で並んでいた
開始
- 印刷。Aを藤原さんが書く
- Bを僕が読み、Cをphiさんが読む。
- 通す。Bを僕が書き始める。
- 1WA。つらい・・・即交代も考えたが少し考えてバグ見つかったので治す。手とかめっちゃ震えた
- 通す。おそらくこの時25分程度。
- Cをphiさんが書く。幾何だがうまいやり方をやると全く難しくないらしい。
- しかしサンプルに詰まる。ここは印刷して交代しDを藤原さんがやることにする。
- Dを通す前にCのバグが見つかり通す。この辺り結構penaltyがたまっており辛い感じだった。
- Dバグる。D印刷している間にDが通る。
- Eはもう解法が詰まっているのでやるだけなので僕が通す。
- Fをphiさんが考えていたので書き始める。
- Gを藤原さんが同時に考える。多角形に点が内包されているかのライブラリを僕が偶然持っておりこれが役に立ちGのメドが立つ。
- Fはバグでつまり、解法にも反例が見つかる。Gをやることにする。
- Gをやっている間にFの解法をphiさんと僕が一緒に考える。実は解に到達できる条件はとても簡単に求まることが分かる。となれば辞書順最小は「いつものアレ」
- Gバグってるなら交代しようカナ～とか思ってる間に藤原さんが通してくれた。強すぎる
- Fはもう書くだけ。
- 15分ほどを残して全完！！！！！
まとめ
- チーム戦思っていたより遥かに楽しかった。3人のうちどの1人が出たときの成績よりも3人でやって真に完答数が増えるのがすごい楽しい。Regionalとか楽しみです。
トップ競技プログラマー年代まとめ
世界の競技プログラマーの中でもトップに入る人々を年ごとにまとめます。資格のある最後のIOIの年を基準にしています（僕にとって分かりやすいから） もちろん出ているとは限りません。
かなりcontroversialなトピックだと思うのでまあ誰が入ってて誰が入ってないとかはコメントして欲しいですが基準の整合性については多めに見てください・・・CFで公開することもないと思います。
間違っていたらバシバシコメントしてください。
基準は大体：世界的なコンテストで優勝、TopCoder/CFで10傑に有意な期間入る
若い人は基準緩めです。書いてある大会は優勝のみ載せています。
2014/6/30に作ってます。あんまり完成とか考えずに気が向いたら追加しようと思います
- 1996
- SnapDragon(TopCoder1位52回 max.3402)
- 2000
- 2001
- bmerry(TopCoder 1位11回 max.3449)
- 2002
- 2008
- UdH-WiNGeR/winger(ICPC WF 2009, TopCoder1位4回 max.3506)
- 2009
- 2012
- 2013
- WJMZBMR(IOI 2013, TopCoder1位1回, TopCoder max.3091, CF1位7回, CF max.2757)
- 2014-
- scott_wu(IOI2014, TopCoder1位1回, TopCoder max.3164, CF max.2728)
ジャッジシェルスクリプト
ジャッジできるサーバーがないときでも、手元にテストデータさえあればWA/TLE/ACを判定してくれるシェルスクリプトを書きました。
テストしたいコードと同じフォルダに以下のスクリプトを書いた hoge.sh 、inフォルダ、 outフォルダ、 tmp フォルダを作って、inフォルダにinput,outフォルダにoutputを入れてください。tmpフォルダにはプログラムの出力が入ります。
MLE/REは判定してくれません。REなら勝手に segmentation fault するので分かると思いますが、その場合は(出力が偶然一致していない限り)WAと判定されます。
TLEに対する打ち切りとかいうのもないです。
また、TimeLimitは秒単位でしかいじれません。また、実行時間が1分を超えるとおかしくなります(経過秒 mod 60しか見ていない)
テストデータは、対応するinput/outputで拡張子までの文字列が同じ場合にのみ対応しています。inputフォルダには関係のないファイルを入れないでください（隠しファイルにも注意）
コンパイルオプションやら、テストデータの拡張子は自由に変えてください。
元は.in,.outになっています。拡張子なしにもできます。
テストケース数が拡張子になってるやつには対応してません。
二重拡張子にもおそらく対応してません。
WA/TLEになるとそこで実行が打ち切られ、テストケースの数とともにWA/TLEとなったことが表示されます。
すべて通るとACと出ます。
Ubuntu12.04で動作しました。
cygwinとかだと動くのかなあ？
#!/bin/bash g++ ./tmp.cpp -std=c++0x -Wno-sign-compare -O2 -Wno-unused-result -Wall cd ./in TIMELIMIT=2 ACCEPT=1 for INPUT in `ls *` do INPUT=`echo $INPUT | cut -d "." -f 1-1` START=`date '+%S'` ../a.out <./$INPUT.in >../tmp/$INPUT.out END=`date '+%S'` TIME=`expr $END - $START` TIME=`expr $TIME + 60` TIME=`expr $TIME % 60` if [ $TIME -gt $TIMELIMIT ] then echo $INPUT"TLE" ACCEPT=0 break fi DIF=`diff ../out/$INPUT.out ../tmp/$INPUT.out` if [ -n "$DIF" ] then echo $INPUT"WA" ACCEPT=0 break fi done if [ $ACCEPT -eq 1 ] then echo "AC" fi
IOI系ページまとめ
- OI系の問題はなかなかジャッジに搭載されてくれないので、探すのは意外と大変です。そこでIOI対策に役に立つページたちをまとめます。
- 情報オリンピック日本委員会（http://www.ioi-jp.org/）
- 言わずと知れたJOIのサイト。これがないと予選に出れません。
- http://www.ioinformatics.org/history.shtml
- IOIの問題、ランキング、テストデータ、そして年によっては解法が載っています。
- http://stats.ioinformatics.org/olympiads/
- 昔の結果などを詳しく知りたい人に便利
- http://www.tani.cs.chs.nihon-u.ac.jp/ioi/
- 谷先生のページで、昔のIOIの問題の日本語訳、解説の日本語訳、データセットがあります（最近のはJOIのサイトにあります）
- http://atcoder.jp/
- JOI春合宿のオンラインジャッジ（JOIOJ）,JOI春合宿2013、2012年のオープンコンテスト、APIO2012、IOIer Japan Programming Contest などがまだジャッジできます
- https://wcipeg.com/problems/cat%3Dioi%2Cshow%3D50
- 入るときにブラウザが騒ぎますが多分大丈夫です。Categoryから、IOI,COCI,NOI(中国のOIっぽい),USACO の問題の英語とジャッジがあります。IOIとUSACOはちゃんと更新されている模様。
- http://www.hsin.hr/coci/announcement.html
- クロアチアのOIで、毎年7回ぐらいオープンコンテストを開いています。
- http://acm.tongji.edu.cn/contestproblems?pid=&title=&source=CEOI&setter=
- SourceにCEOI,BOIと入れるとそこそこの数の少し古い問題が出てきます。BOIはBalkanかBalticかどっちかは知りません。あとページを読み込むたびにブラウザが騒ぐのが難点。
- http://www.spoj.com/OI/problems/main/
- SPOJのOI系問題が集まったページ。ジャッジが遅いのとレスポンスがおかしい（WAとかREとかじゃなくて、点数だけが帰ってくる）のが難点。
- http://www.codechef.com/
- ChefのLunchtime系コンテストはIOI形式で開かれています。
- http://www.usaco.org/
- USACOの最近のページ。たまに代表選抜コンテストなどをやってたりします。教育的良問も多いし、ソースコード付きのEditorialも充実していて、さらに幅広いレベルの問題があります。また、最近の問題はジャッジしてくれます。
- http://poj.org/problemlist
- Search in Sourceにして、SourceにUSACO,IOI,Romania OI, Croatia OI,CEOIと入れると問題が出てきます。
- http://main.edu.pl/en
- 最近少し有名になってきた（？）Main.edu.pl Task archiveの中に大量にレベルの高い問題があります。比較的数学ゲー系が多い印象？ですがPOIは木やDPがとても多いです（それでも少し新鮮な感じがするかも）
- http://wikiwiki.jp/poiwiki/?FrontPage
- 早速放置されかけてるけど。POIの邦訳と解説を目指したサイト
- http://cms.ioi-jp.org/
- JOIのCMSのページ。過去問のジャッジはできませんが問題文とテストデータがおいてあります。
- http://www.acmicpc.net/category/
- 韓国のOJで、カテゴリ「Olympiad」からいろんなコンテストの問題が解ける（「삭제」となっているものは解けないっぽい） 問題文は韓国語だけど、APIOのジャッジ、COCIのジャッジとしても使えそう
他にオススメなどあったらコメントしてください
XIX OI Festival
問題分はこちら
http://wikiwiki.jp/poiwiki/?%CC%E4%C2%EA%B0%EC%CD%F7%2F%C2%E819%B2%F3%2FFestival%20%CC%E4%C2%EA
人iの到着時刻をCiとおくと、
aはbより1秒早い、という条件は
Ca=Cb-1
つまり、
Ca-Cb<=-1
Cb-Ca<=1
と表せる。
cはdより早い、という条件は、
Cc-Cd<=0
と表せる。
上の条件を、牛ゲー風にグラフにする。
(Ca-Cb<=-1 なら、b->aにコスト-1の辺を張る)
強連結成分ごとにグラフを分けて、それぞれの成分ごとの答えの和を求めればよい。
(別の強連結成分の人間の到着時刻は、自由に引き離せる)
上の条件を満たす中で、到着時刻の最大の差が強連結成分ごとの答え。
(強連結成分内での到着時刻に差があるとき、その間の整数の到着時刻を取る人間は常にいる)
これは、グラフの2点間の最短経路の長さの最大値。(蟻本Layoutみたいな感じで)
条件を満たせないときは、負閉路ができている。
強連結成分分解、負閉路検出、最短経路はすべてWarshall Floyd風にO(N^3)でできる。
#include<iostream> #include<algorithm> #include<cstdio> #include<string> #include<cstring> #include<vector> #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 CLR(a) memset((a),0,sizeof(a)) #define pb push_back #define mp make_pair #define fr first #define sc second #define dump(x) cerr << #x << " = " << (x) << endl #define prl cerr<<"called:"<< __LINE__<<endl 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;} template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; } template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; } typedef long long int lint; typedef pair<int,int> pi; int g[605][605]; bool reach[605][605];//到着可能か int n,m1,m2; int done[605],mark[605]; int main(){ cin>>n>>m1>>m2; REP(i,n) REP(j,n) g[i][j]=INF; REP(i,n) REP(j,n) g[i][i]=0; REP(i,m1){ int a,b;cin>>a>>b;--a;--b; chmin(g[a][b],1); chmin(g[b][a],-1); reach[a][b]=reach[b][a]=true; } REP(i,m2){ int a,b;cin>>a>>b;--a;--b; chmin(g[b][a],0); reach[b][a]=true; } REP(i,n) REP(j,n) REP(k,n){ reach[j][k]|=(reach[j][i]&reach[i][k]); chmin(g[j][k],g[j][i]+g[i][k]); } REP(i,n) if(g[i][i]<0){ puts("NIE"); return 0; } int res=0; REP(i,n) if(!done[i]){ memset(mark,0,sizeof(mark)); REP(j,n) if(reach[i][j] && reach[j][i]) done[j]=mark[j]=1; //相互に到着可能<->同じ強連結成分 int tmp=0; REP(j,n) if(mark[j]) REP(k,n) if(mark[k]) chmax(tmp,g[j][k]); //最大の最短経路の距離 res+=tmp+1; } printf("%d\n",res); return 0; }
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; }
