2022-11-20

HHKB プログラミングコンテスト 2020 D - Squares

2年前の問題になりますが HHKB プログラミングコンテスト 2020のD - Squaresについてです。
atcoder.jp

問題としては1辺Nの正方形のグリッド中にA(1辺a),B(1辺b)の２つの正方形を重ならないような配置の総数を求めるというもの。

解説だと余事象から求めている(全体からA,Bが重なる方法を引く)のだけれど、別解で解いたので書いておきます。

包除原理で重ならない方法を直接的に計算する方法です。

2つの正方形が重ならないためには、x軸もしくはy軸に並行に引いた線でA、Bの正方形を分離できる必要があります。

上下に分けることができる配置を $X$ 、左右に分けることができる配置を $Y$ とすると、 $|X \cup Y| = |X|+|Y|-|X \cap Y|$ が答えです。
$|X \cap Y|$ はA,Bが対角の位置となるように十字に線を引くことができる配置です。

上下にABの順に並ぶものを $X_{AB}$ 、同様に左右にABの順に並ぶものを $Y_{AB}$ とします。
対称性から、以下が成り立ちます。

$\displaystyle |X| = |Y| = 2|X_{AB}| \\ |X \cap Y| = 4|X_{AB} \cap Y_{AB}|$

ということで最終的に以下の値を求めます。
$|X \cup Y| = 4|X_{AB}|-4|X_{AB} \cap Y_{AB}|$

Bの左端をx,上端をyとすると $|X_{AB}|, |X_{AB} \cap Y_{AB}|$ はそれぞれ以下の式で求めることができます。

$\displaystyle \begin{eqnarray} |X_{AB}| &=& \sum_{x=a}^{N-b} (N-a+1)(x-a+1)(N-b+1) \\ |X_{AB} \cap Y_{AB}| &=& \sum_{x=a}^{N-b}\sum_{y=a}^{N-b} (x-a+1)(y-a+1) \end{eqnarray}$

展開して整理すると以下のようになります。展開は Wolfram|Alpha: Computational Intelligence を使いました。

$\displaystyle \begin{eqnarray} \begin{split} |X \cup Y| &= 4|X_{AB}|-4|X_{AB} \cap Y_{AB}| \\ &=2(N-a-b+1)(N-a-b+2)(N-a+1)(N-b+1) \\ &\quad\quad-(N-a-b+1)^2(N-a-b+2)^2 \end{split} \end{eqnarray}$

$w=N-a-b+1$ とするとすっきりします。
$|X \cup Y| = 2w(w+1)(w+a)(w+b)-w^2(w+1)^2$

atcoder.jp

2022-07-13

Microsoft Certified: Azure Fundamentals 取得した

5/12,13で予定していた Azure Virtual Training の 2日目がキャンセルとなり、丸１日分無駄になるというアクシデントもありましたが、AZ-900 の認定試験に合格し、Azure Fundamentals 取得しました。

www.credly.com

Foundamental なので初級者向けですが、開発者知識だとうっすらとしか知らないことがおおくて勉強になりました。

あとは最近のオンラインの勉強環境にしっかり触れることができて体験を結構アップデートできました。
埋め込んでいるcredlyもOpen Badge対応。UdemyでAZ-900の過去問もやりました。

2022-04-07

ABC 246 E - Bishop 2

atcoder.jp

解説では拡張ダイクストラや01BFSだけど、ずっとTLEで通すまで時間がかかったので忘れないようメモ。

右上がりのラインと左上がりのラインで到達できる範囲を頂点と考える。すると各マスの右上がりラインと左上がりラインに辺を貼ることで、曲がるときにコスト1と考えることができ、普通のBFSの最短経路で求めることができる。ただ始点/終点はそれぞれ2つあるので、簡便のため、始点/終点の頂点を作成し、それぞれのマスのラインの頂点に辺をはる、この時結果としては+1になるのに注意。

最初に辺をまとめるところはN * N * 2の頂点を用意して一旦UnionFindでまとめてからグラフを構築するか、グラフに頂点を足せるようにしておいて、左上、右上のマスと連結できないときにあたらしく頂点を増やせばよい。

class Graph
  def initialize; @g = []; end
  def add_node; @g << []; @g.size - 1; end
  def add_edge(a,b); ... ; end
  def bfs(s,t); ... ; end
end

提出 : atcoder.jp

2020-05-12

AtCoder ABC 167 F Bracket Sequencing

ABC 167は5完 Eの実装で時間を溶かしてしまってFが解けなかった。

atcoder.jp

問題としては( と )だけの文字列が複数与えられるので、好きな順番で連結して、括弧の対応が取れた文字列にできるかどうかの判定

それぞれの文字に対し対応する括弧を潰すと、))(((のような形になるので、)の数をr, (の数をlとして、(r, l)で考える。
先頭にできるのはr = 0だけ、末尾にできるのはl = 0だけ、それ以外は中間部

カッコ列は(の数が先行して、)が追い付く形になるので、i個連結して括弧の対応が取れた状態にするには $\sum_{j=1}^{i-1} (l_j - r_j) \ge r_i$ 、ただし $l_1 \ge 0, r_1 = 0$ を満たす順番で、且つ $\sum_{j=1}^{N} (l_j - r_j) = 0$ である必要がある。
先頭部、中間部(r - lで昇順にソート)、後尾部を順次連結して、全部追加できるか + 括弧の数が同じかを確認して終了。

中間部(r - lで昇順にソート)で貪欲にやって通ったけど不安。解説見るとr - l <= 0, r - l > 0に分けてr 昇順, l降順で足していくとよいらしい。なるほどなー。

N = gets.to_i
S = []
T = []
W = []
 
N.times do
  w = gets.chomp
  r = 0; l = 0; 
  (0 ... w.size).each do |i|
    c = w[i]
    if c == '('
      l += 1
    elsif l > 0
      l -= 1
    else
      r += 1
    end
  end
  if l.zero? # terminate
    T << [r, l]
  elsif r.zero?
    S << [r, l] # start
  else
    W << [r, l]
  end
end
 
l_sum = S.inject(0){|s,(r,l)| s + l }
 
W.sort_by!{|r,l| r - l }
W.each do |(r,l)|
  if l_sum >= r
    l_sum = l_sum - r + l
  else
    puts 'No' 
    exit
  end
end
 
T.each do |(r,l)|
  if l_sum >= r
    l_sum = l_sum - r + l
  else
    puts 'No' 
    exit
  end
end
 
puts l_sum.zero? ? 'Yes' : 'No'

atcoder.jp

2020-04-24

簡易 PQueue

バイナリヒープの優先度付きキュー

使い方

pq = PQueue.new
%w/1 12 123 abcd abc/.each do |w|
  pq.enq(w,w.size) # 優先度を指定して追加する。#enq(value, priority)
end
puts pq.deq until pq.empty? # #deqでpriorityの小さいもの取り出せる

1
12
abc
123
abcd

class PQueue
  Node = Struct.new(:value, :priority)
  def initialize
    @heap = []
  end
  def size; @heap.size; end
  def empty?; @heap.empty?; end
  def peek; empty? ? nil : @heap[0].value; end
  def enq(value, priority)
    el = Node.new(value, priority)
    j = @heap.size
    @heap << nil
    while j > 0
      up = (j - 1) / 2
      break if @heap[up].priority < el.priority
      @heap[j] = @heap[up]
      j = up
    end
    @heap[j] = el
    self
  end
  def deq
    return nil if empty?
    return @heap.shift.value if size == 1
    
    ret = @heap[0]
    @heap[0] = nil
    el = @heap.pop
    
    i = 0
    while 2 * i + 1 < @heap.size
      l = 2 * i + 1
      r = 2 * i + 2
      j = (r == @heap.size || @heap[l].priority <= @heap[r].priority) ? l : r
      break if el.priority <= @heap[j].priority
      @heap[i] = @heap[j]
      i = j
    end
    @heap[i] = el
    return ret.value
  end
end

2019-12-09

ABC-147 E

解説通りのO(HW(H + W)M) をRubyで書くとTLEした(コンテストは不参加)のでbetrue12さんのを参考に読み解いてみたら、震えた。

atcoder.jp

取りうる差分をビットで表して、右ビットシフト、左ビットシフトでORを取るDPしてた。すげぇ。

下記は理解後、自分で書いてみたコード

H,W = gets.split.map(&:to_i)
M = (H + W) * 80
A = H.times.map { gets.split.map(&:to_i) }
B = H.times.map { gets.split.map(&:to_i) }

dp = Array.new(H){ Array.new(W, 0)}
dp[0][0] = 1 << M

W.times do |x|
  H.times do |y|
    d = (A[y][x] - B[y][x]).abs
    dp[y][x]  = (dp[y][x] << d | dp[y][x] >> d) if x == 0 && y == 0
    dp[y][x] |= (dp[y][x - 1] << d | dp[y][x - 1] >> d)  if x > 0
    dp[y][x] |= (dp[y - 1][x] << d | dp[y - 1][x] >> d)  if y > 0
  end
end

G = dp[H - 1][W - 1]
puts M.times.find{|i| G[M - i] > 0 || G[M + i] > 0 }

2019-11-26

ABC146-F

時間内にたどり着けなかったけど、たぶん後ろから貪欲にとれば、辞書順最小だな。

j回でたどり着けるとして、j回目の出目を $C_j$ とすると、 $N=\sum_{i=1}^{j}C_j = C_1 + \sum_{i=2}^{j}C_j$ なので、辞書順最小は後ろからとれるだけとるのが最適なはず。
一度、後ろから累積minを取ってやると楽ちん。

def max(a,b); a > b ? a : b; end
  
N, M= gets.split.map(&:to_i)
S = gets.chomp
smin = Array.new(N + 1, N)

(0 .. N).reverse_each.inject(N) do |m,i|
  if i + M < m
    puts -1
    exit
  end
  smin[i] = S[i] == '0' ? i : m
end

ANS = []
N.times.inject(N) do |pos,i|
  break if pos.zero?
  smin[max(pos - M, 0)].tap do |j|
    ANS << pos - j
  end
end
puts ANS.reverse * ' '