【AtCoder:12回目】AtCoder Beginner Contest 135の振り返り(Ruby)

f:id:ryoutaku_jo:20190727205725p:plain

【目次】

【本題】

振り返り

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

AtCoder Beginner Contest 135 - AtCoder

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

f:id:ryoutaku_jo:20190729004528p:plain

レーティング微減

f:id:ryoutaku_jo:20190729004440p:plain

A - Harmony

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

| A − K |

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

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

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

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

AとBをそれぞれ1づつ引いていくと、互いが偶数同士(奇数同士)であれば、必ず|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 } を並び替えた数列である。

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

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

2:相違する箇所が2箇所以上なら、NOを返す(並べ換えは1回のみの為)

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

4:3とソートした配列が一致すれば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

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

f:id:ryoutaku_jo:20190729020344p:plain

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

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

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

f:id:ryoutaku_jo:20190729020557p:plain

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

そして、最後に以下の様に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'

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

《今日の学習進捗(3年以内に10000時間に向けて)》

明日の引越しの向けて準備の為、勉強はほぼ進まず・・・

学習開始からの期間 :233日
今日までの合計時間:2235h
一日あたりの平均学習時間:9.6h
今日までに到達すべき目標時間:2128h
目標との解離:107h
「10,000時間」まで、

残り・・・「7765時間!」