hogloidのブログ

へなちょこ

AOJ 2374 RabbitLunch

概要

日本語なので読んでね
RabbitLunch | Aizu Online Judge


































































解法

O(NlogN),O(Nlog^2N) のやり方もいくつかありますが、O(N) で解くことをオススメします
ヒントはフロー(僕はこれをsnukeに教えてもらった)
かなり面白いので、すぐに見ないほうがいいかも。
見たい人は下までスクロール




















































与えられた条件を二部グラフのフローの形にしてみると、
source-人参(流量は人参の個数)
人参-キウイ(m*n の辺を張る。流量はすべて1)
キウイ-sink(流量はキウイの個数)
の辺を張る。

求める値はこのグラフでの最大フロー
これは最小カットに等しい。

source-人参の辺からK本、キウイ-sinkの辺からL本カットに入れると、
人参-キウイの(M-K)*(N-L)本を切ればよい。

よって、source-人参の辺・キウイ-sinkの辺 を切るときは、流量の小さいものから切っていけばいい。

source-人参の辺の切る数をiとして0...Nまで動かす。
人参-キウイ、キウイ-sink での最小カットは、
X軸にキウイ-sinkの切る辺の数を取ると、
f:id:hogloid:20141115234413p:plain

この2つのグラフを合わせたような感じになる。

キウイ-sinkのグラフは、切る辺は小さい順に並んでいるので、下に凸
人参-キウイのグラフはそもそも直線

となり、和を取ったグラフも下に凸
なので、局所解が大域解になってる

ところで、iを1つ大きくした時、キウイ-sinkのグラフは変わらず、
人参-キウイのグラフは傾きが小さくなる。
このとき、キウイ-sinkの切る数の解は少なくなる方向にのみ動くことがわかる。

よって、iを増やしながら、しゃくとり法をすればいいことが分かる。
ソートをバケツソートで行うと、すべてO(N)

ソースコード
AIZU ONLINE JUDGE: Code Review

g++拡張・tree

g++拡張にpb_ds(policy based data structure)というのがあって、その中に便利なtreeというのがあります。
細かい使い方まとめみたいなページは見つかりませんでしたが、コンテストでの主な用法をまとめておきます。c++のsetの上位互換みたいな感じで使えます。
CF・TopCoderでは使えます。

用意:
g++の新しそうなやつを使う
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;


宣言:
tree<key,null_type,less<key>,rb_tree_tag,tree_order_statistics_node_update> var_name;
いきなり長いです。さすがにtypedefするべき
keyに順序関係の定義された好きな型を入れてね

使えること:
setでできるものは大体できます。insert,erase,iterator関連・swapなど。
その他に使えるのが、いずれもO(logN)で

  • find_by_order 関数
    • var_name.find_by_order(k) でk番目(0-indexed)のiteratorを返します。
  • order_of_key 関数
    • var_name.order_of_key(key) でkey以上の最初の要素が、treeの中で何番目か返します。

が使えます。
このおかげで自前で何かを書く手間が省けるときもあるかも?

実は

  • split 関数
    • var_name.split(key,tree) でkey以降の要素をtreeに移す
  • join 関数
    • var_name.join(tree) でtreeを後ろにくっつける

という関数もありますが、どうやら変な実装のせいでO(N)かかるそうです。(少しテストしてみたところメチャクチャ遅かった)

同じkeyは複数保持できません。
null_type を別の型にすると、keyに紐付けされた別の要素を保存できます。

tree_order_statistics_node_updateのところを自前で欲しい要素を付け足した関数オブジェクトを書くと、例えば平衡二分探索木を使ったRMQなどが実現できますが、やっぱりsplitとjoinのせいで使え無さそう。

参考ページ
Implicit cartesian tree in GNU C++ STL. - Codeforces
C++ STL: Policy based data structures - Codeforces

Codeforces Round #230 (Div. 1) E. Deleting Substrings

暗黒時代のCFなのはわかるがEditorialぐらい復活させてくれ :@
http://codeforces.com/contest/392/problem/E

概要

N要素からなる数列{w}がある。以下の操作を繰り返して、スコアを最大化せよ

  • 数列の連続する部分を取り除き、その長さをLとすると、v[L]点稼げる。ただし、取り除く部分は隣接する項が絶対値で1ずつ異なっていて、山型でなければならない。(➚→➘)(操作が終わると、取り除かれた部分の左と右はくっつく。また、全部消さなくて途中で終わっても良い)


N<=400 , |v[i]|<=2000 w[i]<=10^9
















































解法

DP


con[i][j]:=w[i],w[j-1]を公差1,-1の等差数列で結ぶとき、{w}の[i...j)で余ってしまうものを先に使うことになる。先に使うもののスコアの最大値
dp[i][j]:=w[i],w[j-1] を両端とする山型の形を作るときの、その範囲のスコアの最大値。{w}の[i...j)での山型の形の数列に入らないものは先にすべて使うことになる。
dp2[i][j]:={w}の[i...j)をすべて使うときのスコアの最大値。


このDPができると、
res[i]:=[0...i)までのスコアの最大値
をdp[i][j]を使って更新できる。

上のDPは、j-iが短い順にやると実はできる.
con[i][j]は、iの次のくるものを[i+1,j)の中で全部調べる。
dp[i][j]は、山のてっぺんになるものを[i,j)の中で全部調べる。
dp2[i][j]は、dp[i][j]を代入したあと、分割される場所を全部調べる。
時間O(n^3),空間O(n^2)
http://codeforces.com/contest/392/submission/7438155

Codeforces Round #259 E. Little Pony and Lord Tirek

http://codeforces.com/contest/453/problem/E

問題概要:

ポニーがN匹一列に並んでいる。ポニーiは最初siのManaを持っており、毎時間riのペースでManaを増やすが、Manaはmiまでしか持てない(それ以上になるとmiで止まる)

クエリがM回ある。それぞれのクエリで、時刻tiに[l,r]の範囲のポニーのManaを全部刈り取り、その合計を答える。刈り取られると彼らのManaは0になる。

クエリーはtiが狭義単調増加になるよう与えられる。





















































解法

初期条件siは面倒なのでとりあえず無視。


セグメント木上の区間で、その区間に属するポニーを「刈り取られてからManaが増加する時間」の長さでソート。(mi/ri)
この並びのポニーで、miの累積和、riの累積和を取る。

これで、あるセグメント木上の区間が時刻Tに刈り取られ、その後時間difが経った時にまた刈り取られるとすると、増加時間が dif以上、以下でポニーを分割し、増加時間がdifより少ないポニーたちについてはmiの総和、大きいポニーたちについてはriの総和*difで刈り取る合計が求まる。①


クエリーごとに、刈り取る範囲のポニーの列を、いつ最後に刈り取られたかの区間で分割する。


いつ最後に刈り取られたかの区間について、セグメント木でlogN個の区間に分割できる。
区間K個と重なる範囲を刈り取るとすると、それぞれlogN個に分割し、①の方針でやると二分探索を含むのでO(Klog^2N)の時間がかかるが、刈り取る範囲に完全に含まれる区間は刈り取りの後全部一緒になる。ここから考えるとならしでO(Mlog^2N)になることが分かる。


いつ最後に刈り取られたかの区間はsetで持って重なるものをイテレーションしてもできるが、
以下の方法でもできる:
セグメント木上のあるノードに含まれるポニーが全員同じ時刻に刈り取られたなら、そこで①の感じで処理。
そうでないなら、刈り取る範囲に完全に含まれているとしても、さらに分割。

この方針で、刈り取られた時刻が同じ区間それぞれについて処理している事になる。

あるノードの刈り取られた時刻が一緒かどうかは、刈り取った時にそのノードにフラグを建てておき、下のノードへは使うときに伝播させる。あるノードを更新したら、それらの上のノードで刈り取られた時刻が同じかどうかを確認する、という一般的な処理。




初期条件siがあるので、最後に刈り取られたのが時刻0の場合は、何があってもノードがひとつになるまで分割。

時間O(Mlog^2N)
空間O(NlogN)



http://codeforces.com/contest/453/submission/7324878

Codeforces Round #FF D. DZY Loves Games

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&実質初チームコンテスト!!!
藤原さん、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)