yukicoder No.151 セグメントフィッシング

問題

No.151 セグメントフィッシング - yukicoder

左右の長さ$N$の釣堀がある。
釣堀内の魚は、左右の端につくまで速度１で動いていて、端では時間１かけて方向転換する。
最初釣堀には魚はいない。
時間$Q$まで時間１毎に以下のクエリが与えられるので順次処理する。

1. 釣堀内の位置$y$に$z$匹の魚を右向きに放す
2. 釣堀内の位置$y$に$z$匹の魚を左向きに放す
3. 釣堀内の位置$[y,z)$にいる魚の数を求める

出力は、クエリ３毎に求めた魚の数。

解法

単純に考えると、釣堀内の各位置にいる魚の数と向きを記憶しておき、時間$Q$の経過をシミュレーションして魚の位置を時間ごとに移動させ、クエリ３が来たら指定位置の魚の数の和を計算することで$O(Q*N)$となる。

• 処理ごとのオーダー
  • シミュレーション（魚の移動）$O(N)$
  • 魚の追加 $O(1)$
  • 魚の数を数える $O(N)$
• 全体で $O(Q*N)$

$Q,N \le 2*10^4$ なので、$O(Q*N) = O(4*10^8)$となり、C++ならこれを実装すれば通るようだ。

Rubyの場合はこれだと厳しいので、２つのポイントで効率化する。

• 時間経過をシミュレーション・・・毎時間魚の位置を移動させるのではなく、時間ごとに参照するインデックスをずらせばよい
• 指定位置の魚の数の和を求める・・・問題名にある通りセグメントツリー（BITでよい）で数を保持して和を求める

これにより、以下のようにオーダーが変わり、全体で$O(Q*\log(N))$とできる。

• 処理ごとのオーダー
  • シミュレーション（魚の移動）$O(1)$（処理不要）
  • 魚の追加 $O(\log(N))$
  • 魚の数を数える $O(\log(N))$
• 全体で $O(Q*\log(N))$

図解

魚は以下のように釣堀の中を一周すると考えると、保持するデータ構造は配列1本で行ける。
時間１経過すると、魚は配列上右に１進む。末尾の魚は先頭に来る。

これを、解法のポイント１のように、時間とともに魚が進むのではなくインデックスがずれると考えると、魚の移動処理がいらず以下のようになる。

そしてこの配列の要素をBITで管理すれば、$(z-1$までの$sum)-(y-1$までの$sum)$で区間の和が$O(\log(N))$で計算できる。
インデックスをずらす考え方の場合、以下のように端をまたぐ区間の合計を求めることになり得るので注意して実装する。

#12946 No.151 セグメントフィッシング - yukicoder
※記事書いてからコード見直したら、上記解説とは逆に魚が配列を左に進む想定にしてた。

N,Q=gets.split.map(&:to_i)
NN=N*2
BIT=[0]*(NN+1)
def add x,v;(BIT[x]+=v;x+=x&-x)while BIT[x];end
def sum x;s=0;(s+=BIT[x];x&=x-1)while x>0;s;end
Q.times{|t|
  x,*v=gets.split
  y,z=v.map(&:to_i)
  case x
  when ?L
    add (y+t)%NN+1,z
  when ?R
    add (-y-1+t)%NN+1,z
  when ?C
    ty,tz=(y+t)%NN,(z-1+t)%NN
    uz,uy=(-z+t)%NN,(-y-1+t)%NN
    p sum(tz+1)-sum(ty)+(ty<=tz ?0:sum(NN))+
      sum(uy+1)-sum(uz)+(uz<=uy ?0:sum(NN))
  end
}

AOJ 0092: Square Searching

問題

Square Searching | Aizu Online Judge
0,1（.,*）でできたn*nのマス目が与えらえるので、0で作れる最大の正方形のサイズを求める
$1 \le n \le 1000$

解法

愚直にやると$O(n^3)$でTLE。
以下のようなDPを考えることで$O(n^2)$になる。

あるマス（図中の赤文字の0）について、以下３要素（図中の青枠）のうち一番小さい数が、そのマスを右下として作れる最大の正方形のサイズ（図中の赤枠）である。

• マスから上に0が続く数
• マスから左に0が続く数
• 一つ左上のマスでできる最大の正方形サイズ+1

よって、上記３要素をそれぞれDP配列（n*n）に左上から埋めていけばよい。

DP配列を左上から右下に埋めていくとすると1行上（上に0が続く数、左上の最大サイズ）と1マス左（左に0が続く数）しか参照しないので、
実装では1行上＋1マス左しか保持しなくてすむ。

while(n=gets.to_i)>0
  dp=[[0,0]]*n
  r=0...n
  p r.map{
    s=gets
    w=0
    (dp=r.map{|j|
      h,w=s[j]<?.?[0,0]:[d[j][0]+1,w+1]
      [h,[h,w,dp[j-1][1]+1].min]
    }).map{|h,s|s}.max
  }.max
end

yukicoder No.14 最小公倍数ソート

問題

No.14 最小公倍数ソート - yukicoder

サイズNの数列が与えられるので、最左の値との最小公倍数順に最左より右の数列をソートする。
ソートした数列に対してさらに同様の基準でソートする。
これを一番右まで繰り返したときの数列を求める。

解法

単純に考えると、最小公倍数を求めてソートをN回繰り返すので
$O(N*N\log(N))$程度。
少し考えると、毎回ソートする必要はなく、最小値を一番左に持ってきさえすればよいとわかるので
$O(N*N)$となる。
$1 \le N \le 10000$なので、$O(N^2)$なら間に合うらしいのだが、Rubyで愚直にやってみたら全然間に合わなかった。

高速にするため、約数により最小値の選択を効率化する。
一番左の基準値と同じ約数を持つ数のうち、約数で割った値が一番小さい数が、最小公倍数が一番小さい数である。
$最小公倍数=基準値*約数で割った値$ となるため。
また、同じ約数を持つ数字は小さい順にソートしておくことで、約数毎にその約数をもつ一番小さい値を考えるだけで済む。
1も約数として考えるので、全ての数が考慮対象になり、漏れはない。
これで$O(N*\sqrt N)$になる。（約数の個数のオーダーって詳しくは知らないけど、$O(\sqrt N)$以下だよね。）

#7961 No.14 最小公倍数ソート - yukicoder

require'prime'
N=gets.to_i
a=gets.split.map(&:to_i)
div=Hash.new{|h,x|
  h[x]=x.prime_division.inject([1]){|s,(p,k)|
    s+s.flat_map{|i|(1..k).map{|j|i*p**j}}
  }
}
mul=(0..a.max).map{[]}
a.sort.each{|i|
  div[i].each{|d|
    mul[d] << i
  }
}
puts ([i=a[0]]+(2..N).map{
  i=div[i].map{|d|
    mul[d].delete_at(mul[d].index i)
    (t=mul[d][0])?[t/d,t]:[1e9]
  }.min[1]
})*" "

yukicoder No.17 2つの地点に泊まりたい

問題

No.17 2つの地点に泊まりたい - yukicoder
N個のノードとM個の枝の無向グラフが与えられる。
枝の移動コストとノードの滞在コストが設定されているので
ノード0からスタートし、2つのノードに滞在したうえでノードN-1に向かう最小コストを求める。
ノードは滞在せずに通ることもできる。

解法

ワーシャルフロイド

まずワーシャルフロイドで各ノード間の距離を求める。
滞在する2つのノードの順序を全探索し、最短距離を求める。
これが想定解だった。$O(N^3)$

ダイクストラ

ノード×これまで滞在したノード　を頂点にしたダイクストラ。
自分はこれで書いてしまったが、オーダーいくつになるのかよくわからない。
ダイクストラは$O( (頂点数+枝数)\log(頂点数) )$らしいので
$O( N\times _nC_2\times \log(N\times _nC_2))\simeq O(N^3\times \log(N^3))$?ってことかな。
わざわざ複雑なことをして遅い解法にしてしまったようだ。

#7962 No.17 2つの地点に泊まりたい - yukicoder

s=(1..n=gets.to_i).map{gets.to_i}
c=(1..n).map{{}}
gets.to_i.times{
  a,b,d=gets.split.map(&:to_i)
  c[a][b]=c[b][a]=d
}
q=[[0,0,[0,n-1]],[1e9]]
gone={}
while q[0]&&(q[0][1]<n-1||q[0][2].size<4)
  cost,current,stayed=q.shift
  next if gone[[current,stayed]]
  gone[[current,stayed]]=true
  next_list=[]
  if stayed.size<4 && !stayed.include?(current)
    next_list<<[cost+s[current],current,(stayed+[current]).sort]
  end
  c[current].each{|k,v|
    next_list<<[cost+v,k,stayed]
  }
  next_list.each{|i|
    q.insert((0..q.size).bsearch{|j|q[j][0]>=i[0]},i) unless gone[[i[1],i[2]]]
  }
end
p q[0][0]