解説では，Suffix Array + Range Minimum Queryでの解法が紹介されていましたが，僕はクエリ先読み + Aho-Corasick法で通しました．というか，Suffix Arrayよくわかってない．ある人には，「クエリ先読みするなよ」と言われました． 概要 文字列SとQ個のクエ…

概要 牡牛がN頭いて，M個のコートに1頭ずつ割り当てたい． 牡牛はそれぞれ好むコートが決まっている． 割り当て方は何通りあるか． 解法 bitDPやるだけ． ただし，愚直に実装するとMLEを起こすはずなので，配列の再利用をする． int N, M; int P[30]; int B[…

POJ100問AC記念． 概要 N人の子供が一枚ずつカードを持っていて，輪になって並んでいる． K番目の子供からスタートする．まず，現在選んでいる子供を輪から除外する．除外した子供が持っていたカードに書かれている番号だけずれた子供を選ぶ．これを繰り返す…

概要 N次正方行列があり，初期状態ではすべての成分が0である． T個のクエリが来て，内容は (x1,y1),(x2,y2)で定まる矩形領域に反転操作を行う． (x1,y1)の成分を答える である． 解法 2次元のBITを用意する．これは，(1,1),(x,y)によって定まる矩形領域の値…

概要 2次元格子上においてある黒い石の情報が与えられる． ある格子点において，x方向，y方向共に黒い石に挟まれているならそこにも黒い石を置く． 最終的に格子上においてある黒い石の個数はいくつか？ 解法 扱いやすいように座標圧縮をしておく． 各x座標…

概要 一次元座標x[i]と，値v[i]が与えられる．iとjの間の通信コストはmax(v[i],v[j])*|x[i]-x[j]|である．コストの総和を求めよ 解法 座標でソートしておく． 各iについて，BITを用いてv[i]以下であるiより小さい場所の座標の総和とそのような場所の個数を計…

思いがけないところではまったのでメモ． 概要 線分の上を物体がある方向に向かって動く．2つの物体が衝突すると反対に動く． 一番最後に落ちる物体の名前とその時間を求める． 解法 蟻本の蟻と似た考え方．最後に落ちるものを特定するには，左側にどれだけ…

概要 20個のボウルが一列に並んでいて，あるボウルを選ぶとそのボウルと両側のボウルが一緒にひっくり返る．（端っこのボウルを選ぶと2個だけひっくり返る） 全てのボウルを正しい向きにするには，何回の選択が必要になるか？ 解法 端っこから地道にシミュレ…

ほろ酔いコーディング 概要 5行6列のライトのついたボタンがあって，ボタンを押したらそのボタンと4近傍のボタンが反転する． 与えられた状態からライトを全部消す押し方を求める． 解法 蟻本まんま．幅と高さをいじればそのまま通用する．．．と思う． 僕は…

POJ 2566は，そのままだとしゃくとりできないが，累積和にしてソートするとしゃくとりできるようになる．なぜならば，問題が知りたいのは合計の絶対値であるから，累積和の差だけを考えればよいため．カンニング先→POJ-2566 : Bound Found - komiyamの日記 P…

概要 N個の提灯が下がった糸を垂らす．片方の端点はAとし，他方をBとする． このとき，糸は重力にしたがって垂れ下がる． i番目の提灯の高さをH_iとすると， H_1 = A, H_N = B, H_i = (H_(i-1) + H_(i+1)) - 1 が成り立つ． あるAが与えられたとき，全ての提…