AtCoder Beginner Contest 050 やった

雑な振り返り。

A: Addition and Subtraction Easy

joisinoお姉ちゃんは、A op B という式の値を計算したいと思っています。ここで、A,B は整数で、op は、+ または - の記号です。あなたの仕事は、joisinoお姉ちゃんの代わりにこれを求めるプログラムを作ることです。

文字列で計算式が渡されるので、その計算結果を出力すればいい。まじめにやるなら、渡された文字列を gets.chomp.split してから演算子を見て条件分岐…って感じでやればよさそう。

…なんだけど、式が渡されるならそれをそのまま計算すればよくね？と思ってしまったので、以下のようなコードでやった。

puts(eval gets.chomp)

Ruby, JS, PHP とかだと同じような方法で行けそう。

B: Contest with Drinks Easy

joisinoお姉ちゃんは、あるプログラミングコンテストの決勝を控えています。このコンテストでは、N 問の問題が用意されており、それらには 1~N の番号がついています。 joisinoお姉ちゃんは、問題 i(1≦i≦N) を解くのにかかる時間が Ti 秒であることを知っています。

また、このコンテストでは、M 種類のドリンクが提供されており、1~M の番号がついています。そして、ドリンク i(1≦i≦M) を飲むと、脳が刺激され、問題 Pi を解くのにかかる時間が Xi 秒になります。他の問題を解くのにかかる時間に変化はありません。

コンテスタントは、コンテスト開始前にいずれかのドリンクを 1 本だけ飲むことができます。 joisinoお姉ちゃんは、それぞれのドリンクについて、それを飲んだ際に、全ての問題を解くのに何秒必要なのかを知りたくなりました。全ての問題を解くのに必要な時間とは、それぞれの問題を解くのにかかる時間の合計です。あなたの仕事は、joisinoお姉ちゃんの代わりにこれを求めるプログラムを作成することです。

問題文を読み解くのと入力（の行数）が多いのとで若干めんどくささが… 「1つのドリンクを試すごとに配列を書き換え、全部足し合わせる」のが一番単純な方法。

だけど毎回総和計算するのも無駄が多いので、あらかじめ全問題の解答時間の総和を計算しておいて、ドリンク飲んだ問題に対する差分を後から加味してやる方式でやりました。

n = gets.chomp.to_i
times = gets.chomp.split.map {|i| i.to_i}
base_total_time = times.inject(:+)
m = gets.chomp.to_i
 
m.times do |i|
  p, x = gets.chomp.split.map {|item| item.to_i}
  diff = times[p-1] - x
  puts base_total_time - diff
end

Array#inject(:+) は覚えておこう…

C: Lining Up

1~N までの番号がついた、N 人の人がいます。彼らは昨日、ある順番で左右一列に並んでいましたが、今日になってその並び方が分からなくなってしまいました。しかし、彼らは全員、「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」を覚えています。彼らの報告によると、人 i の、「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」は Ai です。

彼らの報告を元に、元の並び方が何通りあり得るかを求めてください。ただし、答えは非常に大きくなることがあるので、109+7 で割った余りを出力してください。また、彼らの報告が間違っており、ありうる並び方がないこともありえます。その際は 0 を出力してください。

~~問題文が頭に入ってこない~~ 問題を理解するのに時間がかかりました。あとWAを1回出してしまって悔しい。

パターン数自体は

$\displaystyle 2^{N / 2}$

で求められます。が、問題は報告が間違っている時。

最初、0の数が間違ってたら明らかに報告が間違ってるのわかるよな…と思い、偶数と奇数の時に場合分けして0の数をチェックしたりしました。これ自体は正しかったのですが、0以外の数値が異常な時を判別できていませんでした。それでWAに…

最終的に通ったコードは以下のようなもの。

n = gets.chomp.to_i
arr = gets.chomp.split.map { |i| i.to_i }
 
if n.odd? && (arr.count(0) != 1)
  puts 0
  exit
end
 
if n.even? && (arr.count(0) >= 1 )
  puts 0
  exit
end
 
unless arr.uniq.count == (n.to_f / 2).ceil
  puts 0
  exit
end
 
puts (2 ** (n / 2)) % (10 ** 9 + 7)

報告された数値の種類を数え、それが想定されている種類の数と一致しなかったら0にする、というのを後から追加。これでACになりました。

D: Xor Sum

~~なるほどわからん~~

全く解き方が浮かんでこなかったので諦めました。はい。解説を見たらDPで解くよ！って書いてありました。

ちなみにABC全参加者の結果を見たら、今回誰もD問題をやっていませんでした。そんなこともあるのね…

雑感

そろそろDPとかアルゴリズムの話をちゃんと勉強しないとだめかもしれない。 ~~今回のDはDP知ってても解けたか怪しいけど~~

はのちゃ爆発

はのちゃが技術ネタとか日常のこととかを書いてます。

AtCoder Beginner Contest 050 やった

A: Addition and Subtraction Easy

B: Contest with Drinks Easy

C: Lining Up

D: Xor Sum

雑感