hogloidのブログ

へなちょこ

トップ競技プログラマー年代まとめ

世界の競技プログラマーの中でもトップに入る人々を年ごとにまとめます。資格のある最後の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

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

個人的良問リスト

少し前から始めていた、良問だなーと思った問題をひたすらリストしていったものを上げます
良問、というより解く価値のある問題、といった方が正確かもしれません
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