org-mode 8.2 導入メモ
インストール
最新版はhttp://orgmode.org/ja/で確認する
wget http://orgmode.org/org-8.2.tar.gz tar -zxf org-8.2.tar.gz
http://d.hatena.ne.jp/buzztaiki/20100201/1265031994を参考にしてorg-table.elを修正する
*** lisp/org-table.el 2013-10-01 11:04:28.896031328 +0900 --- lisp/org-table.el.bak 2013-10-01 11:04:43.088031931 +0900 *************** *** 965,971 **** (progn (setq s (match-string 1) o (match-string 0) ! l (max 1 (- (string-width o) 3)) e (not (= (match-beginning 2) (match-end 2)))) (setq f (format (if num " %%%ds %s" " %%-%ds %s") l (if e "|" (setq org-table-may-need-update t) "")) --- 965,971 ---- (progn (setq s (match-string 1) o (match-string 0) ! l (max 1 (- (match-end 0) (match-beginning 0) 3)) e (not (= (match-beginning 2) (match-end 2)))) (setq f (format (if num " %%%ds %s" " %%-%ds %s") l (if e "|" (setq org-table-may-need-update t) ""))
orgフォルダでmakeする
.emacs
(setq load-path (cons "path/to/org/lisp" load-path)) (setq load-path (cons "path/to/org/contrib/lisp" load-path))
M-x org-version
で今回入れたバージョンが表示されるか確認する
org-modeで適当に日本語を含むテーブルを作ってみて、レイアウトが崩れないか確認する
フォントが等幅でない場合や半角の幅と全角の幅が1:2でない場合は崩れるの注意
org-export
C-c C-e
でorgファイルをhtmlやtexに変換することができる
このorg-exportに関するコマンド名がバージョン8で変わっているらしいので古い情報を見る場合は注意が必要
pdfに変換しようとするとpdflatexを呼び出すが、pdflatexは日本語に対応できない
そこでhttp://skalldan.wordpress.com/2011/06/10/%E5%9F%B7%E7%AD%86%E7%92%B0%E5%A2%83/等を参考にしてmypdflatexとかシェルスクリプトを作る
(setq org-latex-pdf-process '("~/.emacs.d/mypdflatex %f"))
タイトルの一部を変えるbotについて
[twitter:@titleReplaceBot]
概要
「○○のタイトルの一部を△△に変えると××」という形式のハッシュタグに対して、
データベースに保存された○○のタイトルの一部を△△に変えて15分おきにつぶやく。
詳細
タイトルデータベース
現在、{アニメ,小説,ゲーム,映画}のタイトルを利用している。
データの収集元は、ニコニコ大百科（アニメ作品一覧とは (アニメサクヒンイチランとは) [単語記事] - ニコニコ大百科等）。
Wikipediaでなくニコニコ大百科を選んだ理由はWikipediaよりもニコニコ大百科の方がネットユーザーが好きそうな作品に限定されていると思ったから。
ハッシュタグデータベース
取り敢えず日本語ハッシュタグのツイワンから基本となるハッシュタグを収集しておく。
また、次項の方法でハッシュタグデータベースに含まれていないハッシュタグを用いてつぶやいた場合、それをデータベースに加える。
ハッシュタグの選び方
第1候補（リプライ）
ツイートをする際、
自分へのリプライとして「○○のタイトルの一部を△△に変えると××」という形式（実際にはもう少しゆるい）のハッシュタグを含むツイートがあった場合、
そのようなもので最新なもののハッシュタグを利用する。
（15分以内に２つのリプライがあった場合、古いものは捨てているので若干問題がある）
第2候補（検索）
ツイートをする際、
「タイトルの一部を」とツイート検索して、今回対応している形式をしたハッシュタグを見つけた場合、
そのようなもので最新なもののハッシュタグを利用する。
第3候補（データベース）
ハッシュタグデータベースからランダムにハッシュタグを選ぶ。
タイトルの変え方
△△を置換語と呼ぶ。
取り敢えず置換語は名詞であると仮定している。
タイトルを形態素解析し、名詞の１つを被置換語として置換語に変える。
生成されたタイトルのペナルティ
置換語をローマ字表記したものと、被置換語をローマ字表記したものとの編集距離を計算し、生成されたタイトルのペナルティとする。
通常の編集距離は、挿入、削除、変換が全てコスト1だが、今回は直感的によりよい尺度にするため少し調整した。
また、有名なタイトルのほうが良いと考え、Web検索のヒット数が少ないほどペナルティが大きくなるようにした。
つぶやくもの
生成されたタイトルをペナルティが小さい順に並べた時、上位30件からランダムに選びつぶやく。
ただし、生成されたタイトルが元のタイトルと同一なものは除外する。
Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013
http://acm.timus.ru/contest.aspx?id=153
ロシアの怖い合宿で出題されたセットらしい。チームで解いたが10問あって2完という怖いセットだった。
本番ではC,Iを解いて後でA,Fを解いた。
A - Complex Root
問題
x^n = a+bi
x^m = c+di
を満たすような複素数xの個数を求めよ。
制約
| a | , | b | , | c | , | d | <= 10^18 |
1 <= n,m <= 100
a^2+b^2 > 0
c^2+b^2 > 0
解法
x^n = a+bi … (i)
だけを考えると、
xの候補の１つは絶対値が|a+bi|^(1/n)、偏角がa+biの偏角を1/nしたものであり、
他はそれに1のn乗根をかけたもの（すなわちk/n回転したもの）の計n個解が存在する。
x^m = c+di … (ii)
も同様である。
(i)と(ii)を同時に満たすようなxの偏角θはa+biの偏角をθ1、c+diの偏角をθ2とすると
θ = θ1/n + 2πk/n = θ2/m + 2πk'/m (mod 2π)… (iii)
となる。
よって、gcd(n,m)=g, lcm(n,m)=lとしたとき、
θ1/n = θ2/m (mod 2π/l) … (iv)
であれば、
θ = θ1/n + 2πk/g (k = 0, 1, ..., g-1)
は全てこの場合に限り(iii)を満たす。
ここで、(θ1/n)*l = (θ2/m)*l (mod 2π) ならば (iv)を満たす。
よって、(i)から求めたx^lと、(ii)から求めたx^lが等しければ、(i)と(ii)を同時に満たす
xがg個ある事がわかる。
以上より、(a+bi)^(m/g) = (c+di)^(n/g)を満たすかどうか多倍長で判定し、
満たすならg、満たさないなら0が答えとなる。
F - Fire Signals
問題
2次元座標上のn個の点が与えられる。
このとき直線を引いて、各点からその直線までの距離の和を求めるとき、
その最小を求めよ。
制約
2 <= n <= 1000
| 座標 | <= 10^6 |
解法
証明はよく分からないが、答えを満たす直線は2点を通るような直線として良い。
1次元の場合だと1点を通るような直線（点）としてよいし、それと同じようなものだと直感的には感じる。
そこで、1点を固定して直線を回す。直線の上側（反時計回り方向）と下側（時計回り方向）にある点を分けて直線がx軸と重なるように回転すると、そのときの答えは
上側の点のy座標 - 下側の点のy座標
となる。
これをO(1)で計算するために、両側それぞれに対するx座標のsumとy座標のsumを保持しておく。
すると回転行列から回転後のy座標のsumが一発で求まる。
２点以上が同じ座標にある場合に注意。
O(n^2log n)
I - GOV-internship 3
問題
文字列sとパターン文字列pが与えられる。
アルファベットは0から100000の整数である。
ここで、アルファベット0は1から100000のいずれにも変える事ができる。
このとき文字列sと文字列pの距離を最小にせよ。
ここでsとpの距離とは、pとsの全ての長さ|p|な部分文字列とのハミング距離の和である。
長さが等しい文字列同士のハミング距離とは、２つの文字列において文字が違うような位置の数である。
制約
1 <= |s| <= 100000
1 <= |p| < |s|
0はどちらか一方の文字列にしか現れない。
解法
w = |s|-|p|+1
としたとき、長さ|p|なsの部分文字列はw個ある。
mode_s[i] = s[i-w+1:i]における最頻値、
mode_p[i] = p[i-w+1:i]における最頻値とする。
ただし区間が文字列の外にはみ出るときははみ出ないように区間を縮めるものとする。
s[i]=0の場合、s[i]はmode_p[i]にすれば良く、
p[i]=0の場合、p[i]はmode_s[i+w-1]にすれば良い。
残る問題はどのようにスライド最頻値を求めるかだが、
ヒープと配列をうまく用いると出来る。
窓をスライドさせるとき、ある値が１つ追加され、ある値が１つ削除される。
このような更新のあった値を、そのときのタイムスタンプとともにヒープに入れる。
ヒープは頻度が大きいものから取り出されるようにする。
その窓での最頻値を求めるとき、ヒープから取り出した情報が最新のものかどうかを判断して古いものなら捨てるという処理を行えば良い。
幾何修行
japljさんが幾何の問題集をVirtual Arenaでセットしていたので、最近ちょこちょこやっている。
まだ途中だけど、とりあえずまとめる。
http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=1178&active=status
AOJ 2045 - Turn Polygons
多角形の中にある多角形を、外側の多角形にぶつからないようにどこまで回転できるか。
全ての線分対に対して可能な回転角度を計算し、minをとる。
線分と円の交点が使える。
AOJ 2029 - Light The Room
多角形の中に光源がある。光は壁で1回まで反射で
きる。
このとき光が当たらない壁の長さはいくらか。
- ある頂点を通る、
- ある頂点を通って1回反射、
- 1回反射してある頂点を通る、
- 頂点で反射、
というパターンについて壁のどこと当たるかを計算し、壁を細分する。
細分された壁それぞれについて、光が当たるか当たらないかを計算する。
AOJ 2038 - The Extreme Slalom
線分がn本与えられるので線分1から線分nまで順番に線分に触れながら進むときの移動距離の最小はいくらか。
- 最初と最後は、端点に接するか、垂直に接する
- 途中は通過するか、端点で曲がるか、鏡のように反射する
dp[i][左/右] = i番目の線分の、左/右の端点にいくまでにかかる距離の最小
としてdp
i番目の線分からj番目の線分に行くとき、鏡面反射は2^{j-i-1}通り試す。
ここで、k番目の鏡面反射するならl(l>k)の線分をk番目の線分を対称軸として反転する。
AOJ 2062 - Hide-and-seek
線分によって表される廊下がある。
ある線分上にある点(sx,sy)から最も遠い廊下上の点はどれほど遠いか。
線分アレンジメント＋ダイクストラ
線分の中のほうが答えかもしれないのでそこは適当に。
AOJ 2029 - Walk under a Scorching Sun
2次元多角形、高さで与えられるビルと、線分で与えられる道が与えられる。
太陽は向きθ、仰角Φに位置する。
このとき、道上の点(SX,SY)から(TX,TY)に行くときに、ビルの影になってる部分ではなく、太陽の下を歩かなければならない距離の最小はいくらか。
道は線分アレンジメントする。
ビルの上面の頂点を地面に射影し、ビルの下面の頂点と合わせて凸包を取る。
道の線分を凸包の線分でカットして、細分された線分ごとに太陽に当たるか当たらないかを計算する。そしてグラフの辺のコストを太陽に当たる距離に設定する。
あとはダイクストラ。
AOJ 2023 - Princess, a Strategist
弾丸iは長さliで(xi,0)から時間tiのとき(vxi,vyi)で発射される。
自分は多角形で表されてコマンド列（時間と速度ベクトル）によって平行移動する。
このとき弾丸に当たる回数とそのときの時間は何か。
コマンド列の各速度ベクトルが効いてる時間ごとに分けて考える。
速度v1で動く初期状態s1な線分と，速度v2で動く初期状態s2な線分が交差する時間を求める部分が肝心。
一方を固定して相対距離を考えれば、線分と線分の交点を用いることが出来る。
AOJ 2125 - Land Mark
N個の点が与えられる。ある点にいる人が反時計回り順に見えた点を順に報告する。
このときその人いる場所として考えられる場所の面積はいくらか。
ある2点A,Bに対して、A→Bの場合、視点のスタートする場所は、A-Bに対して反時計回り方向の領域と時計回り方向の領域に分けられる。
そこで、全ての点対に対して領域を2つに分ける処理を凸カットによって行い、最大2^N個の領域が生成される。
このとき最初の領域としては十分大きな正方形を設定する。
細分された各領域に対して、重心に人がいたら報告通りの見え方がありえるかを求め、ありえるなら答えに面積を足し込む。
答えが一定以上大きい場合はInfinity。
AOJ 2226 - Psychic Accelerator
超能力を用いることで物体に加速度をかけることができる。
条件は
- 加速度の大きの最大 <= amax
- 動いている物体に対しては、進行方向・進行方向逆・進行方向と垂直な方向に加速度をかけられる
- 静止している物体には自由な方向に加速度をかけられる
n個の線分が与えられる。線分iと線分i+1は円弧によって結ばれている（i<=n-1)。
このコース上に沿って物体を超能力を用いて移動させるとき最小時間はいくらか。
微妙な方向に加速度をかけられないので、円弧を進めるときは円弧の中心方向に加速度をかけることになる。
a=v^2/rより、v<=sqrt(ra)でなければならない。
ということで、各線分の各端点に対して、速度の上限が決まる。
その上限を超えないように最速で動かせば良い。
線分の途中ではその上限を超えても良いことに注意（出来るだけ超えないと最速にならない）。
幾何というより高校物理な感じだけど、面白い問題だった。
Regionals 2010 :: Asia - ChengDu
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=381
A - Balanced Number
問題
[x,y]に含まれるbalanced numberの数を求めよ。
Balanced Numberとは、ある桁を中心として他の桁の値を重さと見たときのモーメントが吊り合っている数である。
制約
0<=x<=y<=10^18
解法
もちろんsolve(y)-solve(x-1)として解く。
桁DP。
dp[桁][中心の桁][合計][less][zero]
0が少し曲者で、00000とかのとき、どこを中心としても吊り合ってしまうことからどうにかしなければならない。
dpのときzeroフラグを利用して全て0みたいなのはカウントしないようにした。
ただ、普通に桁の数だけ引けばよかったような気もする。
ここで合計は多くとも2000くらいで抑えられるはずなので状態数は18*18*2000*2*2くらい。
B - Battle over Cities
C - Binary Number
やるだけ
D - Detector Placement
問題
レーザーの発信源、レーザーが通る他の場所、三角形のプリズムの頂点、プリズムの屈折率が与えられる。
このとき、レーザーがx軸にぶつかるならそのときのx座標、ぶつからないならErrorをチュス直せよ。
ただし、レーザーの発信源、プリズムはy>0に位置し、発信源はプリズムの外に位置する。
またプリズムの頂点にレーザーが当たることはなく、全反射も起こらない。
また、空気の屈折率は1.0とする。
制約
座標は1000とか
解法
実装するだけ。
屈折は入ってくる角度に注意して場合分けする。
レーザーの半直線を表現するのに、INFに飛ばして線分として扱うとかしてたら誤差で死亡した。
ここで半直線ライブラリを作った。
E - Double Maze
問題
6*6の迷路があり、スタート、ゴール、穴、壁がある。
最初ボールがスタートにあり、ゴールに持っていくことが目標。
ボールに上下左右いずれかのコマンドを送ると、その方向に動く。
ただし、壁があったら動かず、穴に落ちたり外側に出たりしたら駄目。
２つの迷路が与えられるので、両方を同時に解く最短コマンド列を求めよ。
コマンドは２つの迷路に同時に送られ、ボールはそのコマンドに沿って独立に動く。
複数あれば辞書順最小。
制約
解法
BFSするだけ。
辞書順はDLRUの順に動かせば良いだけ。
注意点
- 壁の判定をしてから穴の判定や外側に出る判定を行う
- スタートとゴールが同じ場所にあることがある
F - Error Curves
問題
二次関数がn個与えられる。
それらのmaxをとった関数をFとするとき、
Fの最小値を求めよ。
制約
T<=100
n<=10000
解法
f,gが凸関数のときmax{f,g}が凸関数であることから三分探索。
立命合宿阪大セットの曲線の長さ求めるやつが頭から離れず思いつかなかった。
CF#82Eが関連っぽい。
http://codeforces.com/blog/entry/2493?locale=en
G - Go Deeper
問題
要素数mの数列a,b,cが与えられる
a[i],b[i]∈{0,1,...n-1}
c[i]∈{0,1,2}
であり、要素数nの{0,1}数列xをうまく決めて、以下を満たすz(<=m)を最大にしたい。
x[a[d]] + x[b[d]] != c[d] (for all d < z)
このときzの最大値を求めよ。
制約
0 < n ≤ 200, 0 < m ≤ 10000
解法
二分探索＋2SAT。
二分探索でzを決めて、
0~z-1の制約を用いて2SATを構築し、充足可能かどうかで分岐していく。
2SATの変数はn個でx[i]に対応する。
各制約はc[i]によって形が変わる。
- c[i]=0
- x[a[i]] or x[b[i]]
- c[i]=1
- not (x[a[i]] xor x[b[i]])
- c[i]=2
- ~x[a[i]] or ~x[b[i]]
H - Jenga
I - Rescue
制約
魔力がm1,...,mnな石が１列に並んでいる。
あるiを選んでスキルを発動すると、m1~miの石にダメージを与えることが出来る。
石j(j<=i)に与えられるダメージはmax(0, (j-i)*(j-i)*p)である。
与えられたダメージがmiを超えると石は破壊される。
k回のスキル発動で全ての石を壊したい。
このときpとして必要な値の最小値を求めよ。
解法
1 ≤ n ≤ 50000, 1 ≤ k ≤ 100000
制約
二分探索+貪欲+差分処理
二分探索でpを決め打ちする。
ここで、残っている石で最も右のものをiとすると、スキル発動ではiを選ぶべきである。
なぜなら、iより小さければ石が残ってしまうし、iより大きければダメージが弱くなるから。
そこで右から石についてループを回していき、現在与えられたダメージが魔力以下なら
その石を破壊できるまでスキル発動を繰り返すという処理を行う。
ここで、現在与えられたダメージの計算は普通にやるとO(n)かかってしまうが、
差分処理を行うとO(1)で行うことが出来る。
これはKUPCのAcceralation of SNSと似ている。
二次関数なので差分の差分は定数であることを利用する。
J - Similarity
問題
大文字アルファベットからなる要素数nの列Aがある。
同様の列Bがm個与えられる。
このとき、Bのアルファベットを適切に入れ替える（例えばXをYに変えたならYは別のアルファベットに変えなければならない）ことにより、AとBのsimilarityを最小にしたい。
ただし、AとBのsimilarityはsum(Ai==Bi)/nで定義される。
このときsimilarityの最小値を求めよ。
制約
0 < n < 10000
0 < m < 30
解法
アルファベットの変換は、アルファベットをアルファベットにマッチングさせるイメージ。
そしてあるアルファベットをあるアルファベットに変換させることによって類似度がどれだけ大きくなるかは事前に求めることができる。
よって最大重み最大二部マッチングで解ける。
K - Snooker Referee
Regionals 2011 :: Asia - Chengdu
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=520
A - Alice and Bob
B - Break the Chocolate
問題
N*M*Kの板？チョコレートがある。
これを1*1*1のピースに分けたい。
分け方には手を使う方法とナイフを使う方法がある。
手を使う方法はピースを１個ずつ折るしか無い。
ナイフを使う方法は何個でもピースを１回で切る事ができる。
ナイフを使える場合と使えない場合でチョコを分けるための最小回数を求めよ。
制約
1 ≤ N,M,K ≤ 1000
解法
ナイフを使えない場合は、N*M*K-1。
使える場合は、。
C - Construct the Great Wall
D - Disney's Fastpass
問題
ディズニーランドで、ファストパスをうまく使って興味のあるアトラクション全てに乗るのにかかる時間の最小を求めよ。
パークは頂点数N,変数Mのグラフで与えられる。
興味のあるアトラクションはK個。
i番目の興味のあるアトラクションはPiに位置し、普通はTi分、ファストパスがある場合はFTi分の時間がかかる。
ファストパスがある位置はNi個であり、それはFi1,...,FiNに位置する。
複数のアトラクションが同じ位置にある場合もある。
グラフは連結である。
制約
1 ≤ N ≤ 50
0 ≤ K ≤ 8
E - Eliminate the Conflict
問題
アリスとボブがN回じゃんけんする。
アリスはボブが何を出すか知っている。
アリスはA回目とB回目について
- K=0 : 一緒の手を出さなければならない
- K=1 : 違う手を出さなければならない
という制約をM個課せられる。
アリスは一回でも負けるか、制約を満たせなければ負けとなる。
このときアリスに勝つ見込みがあるか判定せよ。
制約
1 ≤ N,M ≤ 1000
解法
ボブの手から、アリスがi回目のじゃんけんで出すことが可能な手がどれか（２個）分かる。
そこでPiが真なら１個目の手を出し、~Piが真なら２個目の手を出すとみなすことで2SATを用いることが出来る。
M個の制約について、
- K=0 : Piで出す手とPjで出す手が違う → ~Pi∨~Pj （他の組み合わせ(Piと~Pjとか)も同様）
- K=0 : Piで出す手とPjで出す手が同じ → ~Pi∨~Pj （上と同じ）
という項を考えて2SATを解けば良い。
F - Fruit Ninja
問題
円がN個ある。
直線を引いたとき交差する円の数の最大値を求めよ。
制約
1 ≤ N ≤ 1000
解法
答えとなるような直線は、交差する円の数を変えないままある円に接するように移動することが出来る。
そこで各円について接線の角度で平面走査する。
G - GRE Words
問題
N個のワードが入った順序付き単語リストがある。
単語リストから単語をいくつか消して、全ての連続する単語について、1つ前の単語が次の単語の部分文字列になっているようにしたい。
また、各単語には価値w[i]が割り当てられているので合計価値の最大値を求めよ。
制約
1 ≤ N ≤ 2*10^4
文字列の長さの合計 ≤ 3*10^5
解法
dp[i] = max{ dp[j] + w[i] | (s[j]はs[i]の部分文字列) }
でmax{dp[i]}が答え。
部分文字列となるワードを見つけてくるのはAho-Corasickを使う。
初めに全部のワードでTrieを構成しておく。
現在のワードをマッチさせて、なんかの文字列とマッチしたらそのDPの値を見るという感じ。
計算量は多分O(N^2+sum_of_length)
あとcin使うとWAするっぽい？
H - Holiday's Accommodatio
問題
木があり、各頂点にひとりずつ住んでいる。
各人は、自分以外の頂点に移動する。
ここで、2人以上の人が同じ頂点に移動することは許されない。
このとき、全員の移動距離（最短距離）の合計の最大値を求めよ。
制約
2 ≤ N ≤ 10^5
解法
各辺に対して、一方の側にいる人の数をA,もう一方の側にいる人の数をBとすると、
min(A,B)人をスワップすることが出来る。
そこで、sum{min(A,B)*2*辺の長さ}が答え。
I - Isabella's Message
ただの実装問題
