hogloidのブログ

へなちょこ

Codeforces Round #FF D. DZY Loves Games

CF

http://codeforces.com/contest/446/problem/D

概要

N頂点M辺の無向連結グラフ(多重辺もたまにある)があり、ある頂点にいるときはつながっている辺を等しい確率で選んでその先に進む。
頂点にはtrapがあるかどうかが決まっている。
初め頂点1にいる。頂点1にはtrapはなく、頂点Nにはtrapがある。
trapのある頂点に進むと体力が1減る。体力が2の状態で頂点Nにたどり着く確率を求めよ。初めの体力はk







































解法

ガウスの消去法+行列累乗
O(N^3+a^3logN) (aはtrap付きの頂点の数)
頂点iからどこかのtrap付き頂点にたどり着くまでのステップを考えると、
j(trapつき)へたどり着く確率P(i,j)は
P(i,j)=ΣP(隣接する頂点,j)/degree[i]
trap付き頂点については、
P(j,j)=1
P(k,j)=0 (j!=k , kにトラップがある)
としておく。

ここで、jがどの頂点でも、trap付きの頂点の式の定数項が変わるだけなので、
trap付き頂点の式の定数項をあたかも変数のように持っておき、その変数に対する係数をもつ。
その情報を含んだn*(2*n)行列でgauss-jordanする。
実際に値を求めるときはjに応じてこの変数を決め、係数を掛ける。

iからtrapのある頂点jに進むとき、
iがtrap付きなら、iの隣接する点たちからjまで進む確率の総和を次数で割る。
iがtrap無しなら、ふつうに。


あとは行列累乗をするだけ。k-1回目のtrapのvisitでNにたどり着けばいい。


http://codeforces.com/contest/446/submission/7145122

ICPC Japan Domestic 2014

ICPC

初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
    • tomek(ICPC WF 2003 TCO 2003 2004 2008 TCCC 2004 TopCoder1位52回 TopCoder max.3611)
  • 2001
  • 2002
    • Petr(TCO 2006 2013, GCJ 2006, TCCC 2006 2007, Yandex.Algorithm 2011, Facebook Hacker Cup 2011 2013, Russian Code Cup 2011 2013, MemSQL start[c]up 2013, TopCoder1位125回 TopCoder max.3923 CF1位16回 CF max.2912)
    • Egor(TCO 2012, GCJ 2012,TopCoder1位21回, TopCode max.3465 CF1位10回, CF max.2763)
  • 2004
    • ACRush(GCJ 2008 2009, TopCoder1位43回, TopCoder max.3902)
  • 2006
    • iwi(TopCoder1位4回 max.3306)
    • wata(TCO 2010 Marathon, TopCoder1位5回 max.3357)
  • 2008
    • UdH-WiNGeR/winger(ICPC WF 2009, TopCoder1位4回 max.3506)
  • 2009
    • rng_58(TCO 2010 2011,GCJ 2011 TopCoder1位6回 TopCoder max.3511 CF1位12回 CF max.3010)
    • lyrically/hos.lyric(TopCoder1位5回 TopCoder max.3395 CF1位4回, CF max.2652)
    • meret(GCJ2012, TopCoder1位2回,TopCoder max.3424 CF 1位2回, CF max.2655)
    • peter50216/0O0o00OO0Oo0o0Oo(Bayan 2013 TopCoder max.3341 CF1位6回 CF max.2823)
  • 2012
    • tourist(IOI 2009 2010 2011, Yandex.Algorithm 2013,2014 GCJ 2014 ICPC WF 2013, Facebook Hacker Cup 2014, TopCoder1位31回 TopCoder max.3734 CF1位42回 CF max.3250)
    • yeputons(ICPC WF 2014, TopCoder1位2回, CF1位4回, TopCoder max.3158, CF max.2773)
    • semiexp(TopCoder1位2回, TopCoder max.3261)
  • 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://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.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://cms.ioi-jp.org/
    • JOIのCMSのページ。過去問のジャッジはできませんが問題文とテストデータがおいてあります。
  • http://www.acmicpc.net/category/
    • 韓国のOJで、カテゴリ「Olympiad」からいろんなコンテストの問題が解ける（「삭제」となっているものは解けないっぽい）　問題文は韓国語だけど、APIOのジャッジ、COCIのジャッジとしても使えそう

他にオススメなどあったらコメントしてください

今年の目標

雑記

そういえば作ってなかったので。

必須目標

  • CF Rating で2350をつける
  • TC Rating で2550をつける
  • 進級

これぐらいは

  • 上の状態で年越し
  • 上+100ぐらいはつける（どっちも）
  • （あれば）国内コンテストで5位以内 ex.天プロ
  • 不可を出さない

やりたいなあ

  • 国際オンサイト（TCO,GCJ,Yandex.Algo etc..）に出る
  • 言葉遊びでｳｪｲwする

XIX OI Festival

POI

問題分はこちら
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;
}