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

/home/cympfh/

数式を $$ で囲んで書いてますが面倒くさいので、いちいち、はてな書式にしたりしません

ABC 032

プロコン

Sun Jan 10 00:19:29 JST 2016

ABC 032

A 問題

n 以上で a,b の公倍数を求める. どの数も小さいので、 n, n+1, n+2, \ldots, n+ab の全部試して一番小さい公倍数探せばいい.

a,b,n = readlines.map(&:to_i)
n.upto(n+a*b).each{|m|
  if m%a == 0 and m%b == 0
    p m
    exit 0
  end
}

B 問題

ありえる部分文字列は、高々 |s| 通り. 実直に試せば良い.

require 'set'
a = Set.new []
ls = readlines
s = ls[0].chomp
n = ls[1].chomp.to_i
 
for i in 0.. s.length - n
  a << s[i ... i+n]
end
 
p a.size

C++substr はちょっと使いにくいので Ruby で書いた.

C 問題

与えられる非負整数の列の連続部分列であって、 積が K (K \geq 0) 以下の最長の部分列を探す.

自明な場合として、

  1. 列に 0 が含まれるならば列全体を部分列としてとることで、積は 0 になって、K は 0 以上の整数だから、いつでも積は K 以下である.
  2. K=0 の場合、列の成分は 0 以上だから、0 を含む部分列を探さなければならない.
    • 列に 0 が含まれるなら、先ほどのように列全体を採用して良いが、
    • 列に 0 が含まれないならば、K=0 以下を満たす部分列は存在しない.

この二通りだけは、先に処理しておいてあげよう.

他の、普通のケースのとき、次の解法がある (らしい).

  1. 成分の \log を取って Range Max Query (RMQ)
  2. 成分がいつも2以上であれば、解となる部分列の長さは高々 \log(K). 連続して出現する1をrun-length圧縮してから、頑張る
  3. 尺取り法

私は尺取り法で解いた.

D 問題

初め、いきなり満点解法を考えようとしていて、諦めて部分点を解こうとして初めて、 独立した3つの部分解法の組み合わせで、問題が構成されてることに気付いた.

3つめは、強引に 2^{N} 通りの探索を素朴な枝刈りつきで探索しただけだけど、解説スライドによると、半分全列挙と呼ばれる方法を使うらしい. いつか一回書いてみよう.

広告を非表示にする