問題概要 : 略解法 : SuffixArray + LCP + RMQ で頑張った与えられた２つの文字列を結合する その際に間には大きな文字を入れる S = S + "$" + T' + "$" この S の SuffixArray, LCP を作成する LCP 内の区間[a,b)の最小値を求めるRMQを用意する左から１つず…

問題リンク : Manhattan Wiring | Aizu Online Judge問題概要 : h * w の表に'2'と'3'がそれぞれ２つずつ存在する その他は'0'か'1'である '2'と'2'を、'3'と'3'を線で繋ぎたい ただし、それらの線同士が交差してはいけない 線の長さの和が最小となるように…

問題リンク : Blame Game | Aizu Online Judge問題概要 : Alice と Bob は互いを攻め合いたい Alice は n 個の欠点があり、 Bob は m 個の欠点がある ある欠点は 0 個以上の相手の欠点と関係があり、その関係は双方向に成り立つ Alice と Bob は交互に相手の…

問題リンク : http://uva.onlinejudge.org/external/114/11401.pdf問題概要 : 3以上の整数 n が与えられたとき、 長さが1からnまでの棒がそれぞれ1本ずつあるものとして それらのうち3本を選んで作れる三角形の個数を出力せよ n が3未満ならばプログラムを終…

問題リンク : Railroad II | Aizu Online Judge問題概要 : 略解法 : 累積和駅は円状になっているが切り離して直線にし、同じものをもう一つくっつける 例えば 7駅あって0と2と6に訪れる必要があるなら、切り離してもう一つ繋げて 0 2 6 0 2 6 とする それに…

問題リンク:Scone | Aizu Online Judge問題概要: 0以上の整数からなる数列と正の整数mが与えられる 数列の連続する部分列の総和%mの最大値を求めよ解法: BIT + 二分探索した（一時期は全探索で通った) 数列の累積和を求め、それらをmで割った余りがそれぞれ…

問題リンク : Ant Nest | Aizu Online Judge問題概要 : 略解法 : 重心求めてくるくるしながら二分探索して計算するまず最初に、連続した３点以上が平行であるようなものが入力として与えられるので、それらを圧縮して１つの線分にする各辺について、そこをケ…

問題リンク : Graph Automata Player | Aizu Online Judge問題概要 : 有向グラフが与えられる ( 多重辺なし、自己ループあり ) 有向グラフの各ノードには０か１が書かれている １秒毎に各ノードの数値を更新する 更新の手順は以下のとおり現在の時刻をtとす…