読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

GCJ2013(Google Code Jam 2013 Round 1C)

Round 1Cは練習でponanza戦を観戦しつつ参加してみた。ラウンド中はinputを落とせないので、紙と頭のなかで解いて、後日コーディングしてみた。
Aは問題文を読み間違いして全然見当違いのコードになってた・・・ので後で解く。
([1,0,1,1,1,0,1,0]なる1,0からなる数列aと正数n:givenのとき、sum(a[i..j])>=nとなる(i,j)の個数をカウントせよと勘違い)
Cは問題文めんどくさかったので読んでない。smallは多分簡単なんだろうなあ。

B. Pogo

1,2,3,4,5,...Nと平面上原点から東西南北に自機を動かして(X,Y)に移動できるか、という問題。X,Yを原点に移動すると考えても良いね、N,N-1,...,3,2,1と(X,Y)を移動して原点に行けるか?。Largeは移動回数Nを最小にしなくてはいけない。
まず、smallはX,Yの絶対値が100以下と、最大500回動かしてもいいことからすぐ解ける。というのも、N回目とN+1回目を組み合わせることで必ず一歩前進できるから(365歩のマーチ戦略)、高々400回の移動で目的地へ移動可。ただし、この戦略はLargeでは通用しない。そこで、色々紙の上で考えてみた。問題文を、集合{1,...,N}を2つのグループに分割し、それぞれのグループ内で加減をうまくしてX,Yを生成できるか?と翻訳してみたり。だけどどうもうまくいかない。悩んだ末、Nが十分大ならば365歩のマーチ戦略で任意の点に行けることから、逆にNが与えられた時(X,Y)に到達できるか?という問いにオレはどう答えるのかと考えてみた。すると、X,Yのうち絶対値が大きい方にNを加減し新しいX,Yとし、次にN-1をX,Yのうち絶対値が大きい・・・というようにGreedyに計算し、最終的に原点にいるかどうかで答えられることが直感的に分かった。でも、1から順次調べていくとTLEだよなあということで次に、n回で原点に到達可能ならばn+4でも可能であるっぽいことがわかった。これも365歩のマーチ2回分だから、パリティが合うからかな。すると、ここで、アハ体験。バイナリサーチが使えることに気がついた。ステキすぎる。つまり、(1,2,3,4),(5,6,7,8),(9,10,11,12),...というようにグルーピングして、その中に原点にいける回数が一つでも存在する最小グループを見つければOK。適当に0番目と10^5番目のグループ間でバイナリサーチしたら、Large正解になりました。

#!ruby2.0

$n=0
def write(s)
  $n+=1
  s="Case \#%d: "%($n)+s.to_s
  puts s
  #$stderr.puts(s) 
end

def debug(s)
  $stderr.puts(s)
end

def solve(n,x,y)
  n.step(1,-1){|i|
    if x.abs>y.abs
      if x>0
        x-=i
      else
        x+=i
      end
    else
      if y>0
        y-=i
      else
        y+=i
      end
    end
	}
  x==0&&y==0
end

def solve4(n,x,y)
  (4*n+1).upto(4*n+4){|i|return i if solve(i,x,y)}
  false
end

def ans(n,x,y)
  ret=""
  n.step(1,-1){|i|
    if x.abs>y.abs
      if x>0
        x-=i
        ret<<?E
      else
        x+=i
        ret<<?W
      end
    else
      if y>0
        y-=i
        ret<<?N
      else
        y+=i
        ret<<?S
      end
    end
  }
  ret.reverse
end

#find the smallest group in [4*l+1,4*l+2,4*l+3,4*l+4],...,[4*r+1,4*r+2,4*r+3,4*r+4]
#s.t. at least one of them satisfies solve(n,x,y) 
def b_search(l,r,x,y)
  if l<=r
    m=(l+r)/2
    ret=solve4(m,x,y)
    if ret
      _ret=b_search(l,m-1,x,y)
      ret=_ret if _ret
    else
      ret=b_search(m+1,r,x,y)
    end
    return ret
  else
    false
  end
end

gets.to_i.times{
  x,y=gets.split.map(&:to_i)
  n=b_search(0,10**5,x,y)
  write(ans(n,x,y))
}