ハル研究所プログラミングコンテスト2015
応募最終日では1位と同スコア同実行時間で2位でした。
・方針
ある時間帯に配達する荷物を決めたときの最小コストは明らかに巡回セールスマン問題(TSP)の応用で解ける。
それぞれの荷物をどの時間帯に割り当てるかは愚直に探索するとO(4^n)で間に合わないが(時間帯,残りの荷物集合)を状態として持つDPでbit演算で部分集合を列挙するテクを使うとO(3^n)で解ける。
最適解を求めることは出来たので以降はずっと高速化。
・探索パターンの削減
自明な事実として時間帯0と時間帯1の荷物集合を入れ替えてもコストは変わらないのでこのような重複パターンの探索を避ける。
例として最大ケースである時間帯指定のない荷物が16個ある場合を考える。
未割り当ての荷物が16個の場合、4つの時間帯はどれも荷物が割り当てられていない。荷物集合はどの時間帯に配達してもコストは変わらないので、1つ目の荷物についてはどの時間帯に割り当てるかを探索する必要がなく3^16から3^15に計算を落とせる。
2つ目の荷物についても荷物が割り当てられていない時間帯を複数探索する必要がなく2通りの分岐で済むので2*3^14になる。
さらに1つ目と2つ目の荷物を同じ時間帯に割り当てた場合を考えると3つ目の荷物の割り当ても2通りの分岐で済み、また同じ時間帯に割り当てたときはさらに再帰的に適用できる。
より実装寄りに説明すると、荷物が割り当てられている時間帯が2つ以上の場合はDPで計算して、そうでない場合はそれぞれの1つでも荷物が割り当てられている時間帯と1つも割り当てられていない時間帯のうち1つに、今注目している荷物を割り当て次の荷物について再帰的に計算した場合の最小コストとなるものを返す。
このように処理すると個数14,13,12,...についてDPの計算が行われておよそ3^14+3^13+3^12+...≒1.5*3^14程度の計算で済む。
・DPの高速化
重複パターンの探索が無駄なのはDPの計算においても同じなので、まだ荷物が割り当てられていない時間帯が複数ある場合は、後ろの時間帯に割り当てれば取り返しがつくので今注目している時間帯ではある荷物を絶対に割り当てないという選択が出来る。これによってその時間帯での計算パターン数を半分に出来る。
最小配達コストのテーブルは頻繁にアクセスされるので時間指定のない荷物はあらかじめ下位のindexにくるようソートしておくとキャッシュに乗りやすい。
・その他高速化
配達先や営業所間の距離はサイズ２のリングバッファを使いA*で探索する。
TSPテーブルなどのサイズが大きい配列はshortで宣言してキャッシュに乗りやすくする。
初期化は必要最小限に。
std::fill_nはfor文まわすより速い。
各荷物集合に対する重さはO(n*2^n)ではなくO(2^n)で計算する。
TSPの計算はO(n^2*2^n)でとても重いので別々の時間帯が含まれる荷物集合などの不要な計算は極力抑える。
TSPの計算は配るDPより集めるDPのほうが速い。
最終方針
途中までこんな感じでDP解法を0.4秒近くまで高速化していた。
o0p1qさんが0.2秒だしてやべぇなTSPの計算しかしてないとしても速すぎるなと思ったので、TSPの計算をあまりせず遅延評価しているというのは察しがついた。
方針は枝刈りでナップザックを下界を見積もって枝刈りするという方法を思い出してやった（分枝限定法というらしい）。
最適解をビューアで見てみると荷物は同じ時間帯に配達するもの同士でかたまっているという幾何的な特徴があり、良い解付近には良い解が、悪い解付近には悪い解が集まっていることが推測できるので枝刈りしやすそうと考えられる。
ということで途中からDP解法を枝刈り解法に変更した。
・下界
下界はそれぞれの時間帯ですでに割り当てた荷物集合に対する配達コストと未割り当ての荷物それぞれに対する下界の和として計算する。荷物集合にある荷物を追加するとき大きく2通りの場合がある。荷物集合が空である場合は営業所と配達先の往復分のコストがかかる。荷物集合が空でない場合は追加する荷物の配達先の直前と直後の位置は営業所または別の配達先にいるので、直前、直後の位置をそれぞれa,b,追加する荷物の位置をcとするとa->bをa->c->bに変更したときのコストの考えられる最小増加分を下界とする。
それぞれの荷物について上記のどのパターンになるかわからないが全パターンの増加コストの最小値なら実コストを超える心配はないので下界として使用することが出来る。
・荷物ソート
枝刈り解法の場合どの順番で荷物を追加するかで枝刈り効率が大きく変わる。
営業所からのマンハッタン距離で降順ソートした場合、クラスタ（同じ時間帯に配達する荷物集合）への距離は近く、または遠くなりやすいのでより枝刈りが効率的に行われると考えられる。最終的には荷物の重さも含めた式でソートした。
・時間帯の探索順序
分枝限定法では今まで見つかった解の最小コストを上界として枝刈りするのでなるべく早く最適解を求めたほうが良い。
各時間帯に荷物を追加した際の増加コストの昇順に探索すると早く最適解が見つかるのでより枝刈りすることが出来る。
・フィールド生成にあわせたA*高速化
ここまでくるともう前処理の距離計算がボトルネックになってきたのでこちらも高速化する必要が出てきた。
フィールドの形は明らかに規則的なのでフィールド生成コードを見ると(odd,odd)の座標は壁ではなく、(even,even)の座標は壁になっていることがわかる。つまり(odd,odd)から1歩移動した先の両肩は必ず壁になっておりそのまま直進するしかできないことが出来ないので再び壁の判定をするのは無駄なことがわかる。なので(odd,odd)の座標しかキューに入れず壁判定の回数を抑えることが出来る。
コード https://github.com/hirokazu1020/contest/blob/master/hpc2015/Answer.cpp
Codeforces Round #303 (Div. 2 only)
http://codeforces.com/contest/545
A-Toy Cars
塗りつぶすだけ
B-Equidistant String
概要
長さnの0,1からなる文字列s,tが与えられる。
s,tと編集距離が等しい文字列を出力、存在しないなら"impossible"と出力せよ。
解法
ある位置のsとtの数字が異なる場合だけ変化させたときに編集距離の差が2増減する。
よってsとtの編集距離/2の分だけsの数字をtにあわせればいい。
C-Woodcutters
概要
n本の木のx座標と高さ
が与えられる。木を左に切り倒した場合は
、右に倒した場合は
を占有する。
切り倒す場所に既に木がないときだけ木を切り落とせる。切り落とせる木の最大数を求めよ。
解法
xの昇順に考えたとき、左に倒せる場合は倒したほうが明らかに最適、
左に倒せず右に倒せる場合は右に倒さなかった場合の最適解が倒した場合の最適解を上回ることはないので貪欲に倒していけばいい。
D-Queue
概要
キューに人が並んでいる。それぞれの人に対応するには時間かかることがわかっている。対応開始までに
時間以上待たされるとがっかりする。
人を並び替えて達成できるかっがりしない人の最大数を求めよ。
解法
validな解をとして [tex:b_i > b_j (i
が存在するときswapしても解として成り立つので、ソートされた解だけを考えればいいというよくあるパターン。E-Paths and Trees
概要
始点の頂点番号と重みつき無向グラフが与えられる。
始点からの最短距離を変えないような重みの和が最小となる全域部分グラフの辺を求めよ。
解法
ダイクストラして最短距離を構成するのに明らかに不必要な辺を除くとDAGになる。
あとはDAG上で最小全域有向木を求めればいい。方法は各頂点について始点方向に接続する辺のうち重みが最小のものだけ残して残りは削除すればよい。一般の最小全域有向木ライブラリでも通るらしい。
AtCoder Beginner Contest #017
コンテストページ http://abc017.contest.atcoder.jp/
解説 http://www.slideshare.net/chokudai/abc017
A - プロコン
3つの課題の配点と得点割合が与えられて合計もとめるだけ
B - choku語
choku語は空文字列またはchoku語の末尾に"ch","o","k","u"を連結した文字列と定義されるのでchoku語かどうか判定せよ。
解法は各文字列の先頭文字がすべて異なるので先頭からマッチングするだけ
C - ハイスコア
解説のとおりある宝石を選び方についての最適解を列挙すればいい。Xを覆う区間というのはli<=X∧X<=riとなる区間でありこのままだと2次元の問題となり面倒だが補集合を考えるとX
CODE FESTIVAL 2014 予選B
コンテストページ http://code-festival-2014-qualb.contest.atcoder.jp/
解説 http://www.slideshare.net/chokudai/codefestival2014qual-b
Cが全然わからず38位。Dの方が明らかに簡単だった。
A - あるピアニスト
maxとるだけ
puts gets.split(' ').map(&:to_i).max
B - 歩く人
和をとっていくだけ
C - 錬金術士
本番中に通せたけどたぶん嘘解法。テストケースがガバガバで明らかに間違ってる方法でも通っちゃう。フローでも解けるとの情報を得たので考えてみた。
文字の位置は必要ないので各文字の出現回数だけカウントしておく。
上図のようなグラフを生やしてs-tフローが2*N流れればS1,S2 から S3 が錬金できる。
D - 登山家
本番ではRMQで二分探索してO(n (log n)^2)で通した。segtree内で二分探索するかsparse tableを使えばO(n log n)になる。
stackを使う解法の解説がスライド一枚で済んじゃってるので簡単に解説でもしてみる。
各位置i(i=0,1,..,n-1)について降順にそこからどこまで東の小屋が見えるかを求めることを考える。スライドの操作１のスタックをpopし続ける操作について説明すると、popする条件によりスタックに詰まれているindexは昇順、対応する高さも昇順になっている。
したがってh[i]を超えるスタックに積まれている中での最初のindexを求めるにはスライドの通り操作すればよいことがわかる。ここでpopされたindexは二度と調べられないが、そのようにして問題ない理由はpopされたindexはdp[j](j
コンテスト解説一覧
解説がどこにあるのかわからないことが少なくないので
過去のコンテストの解説 - 秋田大学ICPC対策室@wiki - アットウィキ
TopCoder https://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=archive
Codeforces 問題ページ右の「Tutorial」
CodeChef Editorials
GCJ analysis
FHC 「facebook hacker cup solutions 2012」とかで検索
Yandex Algorithm 2015r1 2015r2
PCK 問題と解説
JOI 問題と解説 解説 IOI系ページまとめ
ICPC 講評 リンク集→
UTPC 解説
KUPC 解説
WUPC 解説
UAPC2009Spring 解説
UAPC2010 解説
OUPC2012(立命合宿day2) 解説 ジャッジデータ
OUPC2013(立命合宿day2) 解説
立命セット(会津,立命合宿)
NPCA#02 解説
NPCA#03 解説
Typical DP Contest 一言解説 togetter
洋菓子店 論文 スライド
ついでにマラソン系コンテスト一覧
MarathonMatch ハル研プロコン CodeVS ICFPC SamurAICoding CEDEC_AI_CHALLENGE
機械学習,データマイニング系
MarathonMatch Kaggle CrowdSolving HackerRank(よく知らない)
ライブラリverify用問題集
典型アルゴリズムそのままの問題はここOnline Programming Lesson
・エラトステネスの篩
アジア地区2002A
・連立合同式(ライツアウト系)
PCK2006
アジア地区2010D 解説
夏合宿2008day2J(mod7,ジャッジ未対応)
・2点を通る半径rの円
国内予選2004D
・円と円の交点
国内予選2012E(線分の交差判定も) 解説
国内予選2013E 解説
・円と円の共通接線
模擬国内2010E
・点と線分の距離
PCK2006
・線分と線分の距離
国内予選2008E
模擬国内2012D
・ccw
PCK2004予選11
・凸包
PCK2004本選41
・ボロノイ図
夏合宿2009day2F 解説
・ローリングハッシュ
Cf166div2D PROBLEMSET271D Editorial
・Z algorithm
Cf246div2D PROBLEMSET432D
・KMP
Cf201div2D PROBLEMSET346B
Cf246div2D PROBLEMSET432D(failure linkでDP,ロリハも必要)
・Aho-Corasick
UTPC2010I 解説
模擬国内2011F 解説
・SuffixArray(+高さ配列)
Cf94D PROBLEMSET128B
夏合宿2014day4F
SPOJ
codemonk
・最大流
国内予選2009E(二部マッチング)
SRM589div1med(二部グラフの最小点カバー) Editorial
夏合宿2007day3D
ABC10D
・最小費用流
RUPC2012day1E 解説
RUPC2014day3G 解説
幾何コンB(実数コスト)
・強連結成分分解
Cf190div2E PROBLEMSET228E(2-SAT)
・トポロジカルソート
PCK2005(|V|<=20,|E|<=100)
JOI 2006(|V|<=5000,|E|<=100000)
模擬国内2006C 解説
・重心分解
Cf190E PROBLEMSET321C
・Heavy-Light Decomposition
TAQTREE
White Falcon And Tree
夏合宿2012day4D 解説
・meldable heap
夏合宿2009day3F(非想定解)
・２次元RMQ(密)
UAPC2011G
・動的segtree 資料
UAPC2012day2I
・範囲代入segtree
Cf207A PROBLEMSET356A
・遅延評価segtree
・平衡二分探索木
PCK2005 (nth_element)
アジア地区2007A (nth_element)
UTPC2013I (prevvalue,nextvalue)
ARC33C (nth_element)
・永続配列
Cf368div2D PROBLEMSET707D
・永続union-find
AGC#002D(半永続)
・永続平衡二分木
コピー＆ペースト
グラフではない
・ウェーブレット行列 最速攻略 ウェーブレット木の世界
CodeChefLong TRIQUERY(rank_less_than)
夏合宿2012day2C(rangefreq)
K-th Number
Coloring Tree(区間内distinct)
Cf267E(Div2only) PROBLEMSET467E(nextvalue)
ACPC2014Day2I
・符号付ウェーブレット行列
L番目の数字 解説
CF326div2E PROBLEMSET587C
・動的ウェーブレット行列
Library Query(insert,erase,quantile)
Cf260div1D PROBLEMSET455D(insert,erase,rank)
G番目の数字(insert,persistent,linesweap)
・サイコロ
AOJ COURSE
JOI2005予選3 解説
国内予選2012C
国内予選2014F
・シンプソン則
模擬地区2006E 解説
立命合宿2013day2I 解説
・FFT
SRM436div1hard Forum
データ構造メモ（平衡二分木&ヒープ）
※自分用メモなので人に見せる体裁にはしてないです。あまり確認してないので間違ったこと書いてるかも
平衡二分木
備考
節点に部分木のサイズを持たせるなどすればrank_less_thanやkth_elementなどの追加の機能も可。
動的な列を扱うことも可能で要素の挿入削除、列の併合分割ができる動的なsegtreeとしても使える。
プログラミングコンテストでのデータ構造 2 http://www.slideshare.net/iwiwi/2-12188757
npca2013 木のはなし http://www.npca.jp/2013/
Algorithms with Python http://www.geocities.jp/m_hiroi/light/index.html#python_algo
AVL tree
赤黒木と比べれば圧倒的に実装しやすい、赤黒木より遅い印象はないけどよく知らない。
赤黒木
場合わけえぐいやつ。実装する気起きない。葉にだけ要素を持たせればmerge/splitもできる
treap
乱数で割り振る優先度に対してヒープになってるやつ期待値O(log n),merge/split可能、融合永続不可
randomized binary search tree(RBST)
どっちを根にするか乱択するやつ、merge/split可能、融合永続可
treapより好きだけど毎回乱数生成するからそれで遅くなったりするのかな？
splay tree
link-cut treeで使うやつ、ならしO(log n)、merge/split可能らしい
scapegoat tree
平衡でなくなったらその部分を壊して再構築。ならしO(log n)
kd treeは最悪O(n)だがこの方法でならしO(log n)にできるらしい
https://topcoder.g.hatena.ne.jp/spaghetti_source/20120901/1346460700
https://topcoder.g.hatena.ne.jp/spaghetti_source/20120908/1347059626
skip list
木ではないけど似たようなことができる。競技では使うことないだろうけど分散処理がしやすいらしい。
van Emde Boas tree
二分木じゃないけど各種操作がO(log log u),(uは普遍集合のサイズ)でできる謎木。
実測でも速いらしい
http://catupper.hatenablog.com/entry/20120830/1346338855
ヒープ
binary heap
pushとpopだけならこれが最強。固定長配列でよければさらに速くなる。
leftist heap
meld を最悪O(log n)で処理できる。永続化するならこれ
skew heap
ならしO(log n)になる代わりにメンバ変数が減ってコードがより短くなる。
http://hos.ac/blog/#blog0001
binomial heap
meld を最悪O(log n)で処理できるけど上2つと比べてそんなに速いわけでもなくて実装面倒。
pairing heap
meldable heapの中で最速らしいけど多分いらない
relaxed heap
insertを最悪O(1)で実行できる。使うことなさそうだし日本語の資料もないし実装する気ない。
http://emoken.net/blog2/item_2137.html
fibonacchi heap
観賞用
interval heap
minとmaxの取得、削除ができる。ビームサーチで使えそう？
https://topcoder.g.hatena.ne.jp/spaghetti_source/20121006/1349491389
