【AtCoder:12回目】AtCoder Beginner Contest 135の振り返り（Ruby）

【目次】

振り返り
A - Harmony
B - 0 or 1 Swap

【本題】

振り返り

今回は 7/28(土)に開催されたAtCoder Beginner Contest 135の振り返りを行います。

AtCoder Beginner Contest 135 - AtCoder

今回１問しか回答できませんでした・・・まるで成長していない・・・

レーティング微減

A - Harmony

問題文相違なる整数 A , B があります。

| A − K |

= | B − K | となるような整数 K を出力してください。

そのような整数が存在しなければ、代わりに IMPOSSIBLE を出力してください。

制約入力は全て整数である。 0 ≤ A ,

B ≤ 10 9 A と B は相違なる。

AとBをそれぞれ１づつ引いていくと、互いが偶数同士（奇数同士）であれば、必ず|A−K|=|B−K|になるのですが、偶数と奇数（奇数と偶数）になると、交わる事はありません。

なので、両方とも偶数（奇数）か？という条件で、出力を制御しました。

その結果が、以下のコードです。

a,b = gets.split.map(&:to_i)

if (a.even? && b.even?) || (a.odd? && b.odd?)
  puts (a + b) / 2
else
  puts 'IMPOSSIBLE'
end

三項演算子にした方が、スマートかもしれません。

A,B = gets.split.map(&:to_i)
c = A + B
puts c.odd? ? 'IMPOSSIBLE' : c / 2

B - 0 or 1 Swap

問題文 { 1 ,

2 ,

. . . ,

N } を並び替えた数列 p = { p 1 ,

p 2 ,

. . . ,

p N } があります。

あなたは一度だけ、整数

i ,

j

( 1 ≤ i < j ≤ N ) を選んで

p i

と

p j

を入れ替える操作を行うことができます。操作を行わないことも可能です。

p を昇順にすることができるなら YES を、できないならば NO を出力してください。

制約入力は全て整数である。 2 ≤ N ≤ 50 p は { 1 ,

2 ,

. . . ,

N } を並び替えた数列である。

一回目は、以下の様なロジックでコードを実装しました。

１：昇順でソートした配列と、そのままの配列を比較して、相違する箇所を抽出します。

２：相違する箇所が２箇所以上なら、NOを返す（並べ換えは１回のみの為）

３：相違する箇所を、ソートした箇所と置換する

４：３とソートした配列が一致すればYESを返し、一致しなければNOを返す

n=gets.to_i

while p1 = $stdin.gets do
  p = p1.chomp.split(" ")
end

cange = []
p.zip(p.sort) do |p, p_sort|
  cange << p if p != p_sort
end

return puts 'NO' if cange.size > 2

canged = p.map do |p|
  case p
  when cange[0]
    cange[1]
  when cange[1]
    cange[0]
  else
    p
  end
end

if canged == p.sort
  puts 'YES'
else
  puts 'NO'
end

しかし、これでは一部のサンプルで実行時エラーになってしまいました。

次に思い付いたのは、わざわざ置換せずとも、相違する箇所が２箇所以内であれば、どの様な数値の並びであっても昇順になるだろうという仮説の基、以下の様にコードを実装しました。

n=gets.to_i

while p1 = $stdin.gets do
  p = p1.chomp.split(" ")
end

cange = []
p.zip(p.sort) do |p, p_sort|
  cange << p if p != p_sort
end

if cange.size > 2
  puts 'NO'
else
  puts 'YES'
end

しかし、これは一部のサンプルが通りませんでした。

もうこうなると、取っ掛かりが無くて、回答できる気がしなくなってしまう・・・

そして、最後に以下の様にzipメソッドを使わない方法を試したりなどしましたけど、テストケースが通らず、終了となりました。

n=gets.to_i

while p1 = $stdin.gets do
  p = p1.chomp.split(" ")
end

p_sort = p.sort
cange = p.map.with_index { |p, index| p if p != p_sort[index] }
cange.compact!

if cange.size != 2 ||  p != p_sort
  puts 'NO'
else
  puts 'YES'
end

相違が二つ以内ならYESで出力する以下のコードで最終的に通りました。

N = gets.to_i
p = gets.split(' ').map(&:to_i)
p_sorted = p.sort
count = 0
 
N.times do |i|
  count += 1 if p[i] != p_sorted[i]
end
 
puts count <= 2 ? 'YES' : 'NO'

煮詰まるとおかしな方法に走ってしまう・・・