A – White Cells
問題
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
解法
高さH、幅Wの長方形から高さh、幅wだけ除いた残りなので、(H-h)x(W-w)になります。
実装
H,W=gets.chomp.split.map(&:to_i) h,w=gets.chomp.split.map(&:to_i) puts (H-h)*(W-w)
B – Can you solve this?
問題
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
解法
各ソースコードiについて、それぞれ条件を満たすかどうかを判定してカウントしていくだけです。
実装
N,M,C=gets.chomp.split.map(&:to_i)
B=gets.chomp.split.map(&:to_i)
ans = 0
N.times do
a=gets.chomp.split.map(&:to_i)
t=0
a.each_with_index do |v,i|
t += v * B[i]
end
ans +=1 if t + C > 0
end
puts ans
C – Energy Drink Collector
問題
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
解法
「最小で何円あればM本の栄養ドリンクを買い集めることができるでしょうか。」ということなので、安い栄養ドリンクを優先的に買っていき、M本
実装
求めるのは買うのに必要な金額なのでどの店舗でいくらの栄養ドリンクを何本買うかは特に考慮する必要はありません。
なので、
- 各値段の栄養ドリンクが何本存在するかをまとめる（値段のリストは配列、各値段毎の本数はハッシュで管理する）
- 安い値段の栄養ドリンクから優先的に買っていき、M本に到達したらその時点の金額が解となる
という流れで実装します。
n,m=gets.chomp.split.map(&:to_i)
a=[]
b=Hash.new(0)
n.times do
aa,bb=gets.chomp.split.map(&:to_i)
a << aa
b[aa] += bb
end
a.sort!
a.uniq!
ans = 0
a.each do |v|
if m <= b[v]
ans += m * v
puts ans
exit
end
ans += v * b[v]
m -= b[v]
end
puts ans
D – XOR World
問題
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
解法
A、Bの範囲が最大で1012なので、実際に全ての数字を列挙してXORをとるのは時間的に間に合いません。
この問題の考え方として、1bitに着目した場合のXORの特徴として以下の点を知っているかがポイントになります。
- 1の数が偶数の場合に0
- 奇数の場合に1
- 0の数は無関係
つまり、2進数で考えた場合の桁毎の1の数がいくつになるかを考えればよいです。
次のポイントは以下の式に気づくかどうかだと思います。
$$ f(A,B) = f(0,B) \oplus f(0,A-1) $$
図にするとわかりやすいと思いますが、以下のように0〜A-1の部分のビットは同じなので、XORをとると互いに打ち消し合って0になります。よって、A〜BのXORだけが残ります。
次にf(0,A)の求め方です。これが定数時間で求めることが出来れば問題は解決です。
「任意の偶数とその次の奇数のXORは必ず1になる」という性質に着目します。これは偶数とその次の奇数を2進数で表した場合に、1bit目だけが異なることから明らかです。
よって、Aを4で割った余りが
- 0の時：f(0,A)はN
- 1の時：f(0,A)は1
- 2の時：f(0,A)はN^1
- 3の時：f(0,A)は0
となります。
実装
A,B=gets.chomp.split.map(&:to_i)
def f(n)
case n%4
when 0
n
when 1
1
when 2
n^1
when 3
0
end
end
puts f(B) ^ f(A-1)