蟻本には再帰で書かれた Segment Tree が載っているが，うまく書けば再帰を使わず書くこともできる．再帰あり gist9219b197f2a177931e54627003b51c6f再帰なし gistfe04fcefcc5581d60da6150a621d549e それぞれの方法で長さ 200000 でランダムな 1000000 クエ…
問題: K: SOULBLOCK - 京都大学プログラミングコンテスト2015 | AtCoder
特に考察は必要なく，そこそこライブラリを貼って実装するだけで解ける．http://mars.kmc.gr.jp/~asi1024/kurukuru_door/
運営が翌年のWFの選抜方法を明らかにしたみたい．たぶんこんな感じ・([順位] - 1) / [大会に割り当てられているスコア] が小さい順にKチーム選ぶ例えば，Asia PP subregion の今年のスコア (Daejeon:1.9, Hanoi:1.3, Jakarta:1.3, Phuket:0.9, Singapore:1, …
台湾大会でスロットを取れたみたい．やったぜ．
線分アレンジメントして列挙するだけ． O(N^4 * T) (Tはテストケース数) だが，幾何なので間に合う． ジャッジケースをビジュアライザに入れた結果はこんな感じ http://mars.kmc.gr.jp/~asi1024/shore_erosion/
全自動円形掃除機™ をACしたのはもう1年近く前だけど，いまさら解説記事を書きます． いろんな実装方法はあるけど，自分の実装はこんな感じ．多角形の各線分からR内側に平行移動した線分を列挙する 各頂点からの半径 R の円周を列挙する これらの線分や円周…
LCAと遅延伝播SegmentTreeと重軽分解のライブラリを貼った
異なる a, b について，a が b の倍数になるときに a から b に辺を張るような N 頂点のグラフを考える．このグラフは推移的グラフであるので，最大独立集合 = 最小パス被覆 である (Dilworth の定理)．DAG の最小パス被覆は二部グラフの最大マッチングで解…
[l, r) 区間に a_l ... a_r-1 のソート列を持つ Segment Tree を持つ． 各クエリについて O(logN) 回二分探索をすればいい．O(Q log^2 N) くらい．
原案に関わったやつだけ
A*の問題，他にないのかね
問題概要 略解法 DPっぽいやりかたで解いた．計算量が危うい気がしたけど何故か通った．幾何やからな
問題概要 略解法 N字以内で書けるものをvectorでもってDPする．のだが，10までやるとTLEする(MLEもしてそう)．ここで，N
なんかよく理解しないまま解けてしまった
問題概要 3行3N+1列のマップがあり，同じアルファベットについて，大文字と小文字の一方は全て壁であり，もう一方は通れる床である．左から右まで通れるようにしたいとき，壁にする大文字を全て出力せよ．解が複数あればどれか1つを出力せよ．解がない場合は…
問題概要 略解法 O(N^3)のDPは容易に思いつく． 実はmonge性を満たすため，monge-dp にできる． https://gist.github.com/asi1024/5751b073d3f422206e5a/revisions な感じで高速化．
問題概要 1つのチョコボールのスタックを使って2人ゲームを行う． それぞれのチョコボールに栄養価r_iと美味しさs_iが定められており， 2人は食べたチョコボールの美味しさを最大化したいと考えている．2人にはそれぞれ体力値が定められており，それぞれ初期…
問題概要 略解法 とにかく入力ケース数が多い．呑気に二分探索なんてしてたらTLEする・・・ k_1 を見ると B-A が3通りに絞れる．B-A が決まれば，k_n から順に見ていけば，(A,B) の組み合わせは高々1通りに絞れることがわかる．
問題概要 sum_i (P_i * x^O_i) = 0 かつ sum_i (P_i * O_i * x^(O_i - 1) = 0 となるような最小の正整数 x を求めよ解法 最小次数の係数の約数が解の候補となるので，それで全部試す．O(√(NP)) だけど，AOJ鯖は速いので間に合う． これって f(x) = f'(x) = 0…
問題概要 カエルとカッパとイタチがカードゲームをしているこのゲームでは，ギロチンカード1枚，貴族カード12枚，アクションカード6枚を使う．貴族カードとアクションカードの表には，それぞれ整数値が書かれている．まず，ゲームを始める前に，プレイヤーは…
問題概要 略解法 循環操作は全体の和を変えないみたいなので，なんとなく累積和をとってみる． すると，循環操作は値のswapに相当することがわかる．後はノリで解ける．
問題概要 問題文から明らかな最小費用流を感じる何か解法 右手が左手より右側になければならない，という条件は無視できる． 最小費用流で解くにしても，如何せんグラフのサイズが大きい． きっちり辺を張ると辺の数は O(N^2) くらいになってしまう． ここで…
問題概要 2次元マップが与えられる．マスとマスの間にいい感じに壁を配置することで平路がないようにしたい．早い話が特徴的なグラフが与えられるからその全域木を作りたいということ．作り方は何通りあるか．解法 行列木定理を使って求めようにも，ナイーブ…
無事院試にも受かって生活に余裕が出てきたので，そろそろAOJ-ICPCでも埋めていくことにした． 今日から毎日1問ずつ解いた問題をブログに書いていこうと思う．単純に計算すると夏休みのうちに40問くらい解くことになりそう． まずは今日は簡単な問題から．問…
結構実装が大変と言われているこの問題。想定解法は指数オーダーの探索だが、これにも割と良さげな解法がある。例えばこういうケースを例に考えてみる。ロープの上側がロープが結ばれている杭、左下側がスタート地点、右下の緑色の点がゴール地点である。 ST…
高難度の場合分けゲーとして名高いこの問題だが、最近割と良さげな解法を思いついたので実装してみた。STEP 1 原点から引数で与えられる点Pまでの建物の内部を通らない最短の道のりを求めるような関数を作る 原点とその点を結ぶ線分が建物の内部を通らないと…
東京大会は17位でした． 台湾大会は14位でした．
全体で5位，大学別順位で4位でした．
最近はすっかり競技プログラミングをやらなくなってしまい，レートも大学入学時から伸びてないので，ちょっとは練習しようかなあと思う．大学の単位も揃えて時間に余裕ができたし．
