C - Peaks（ABC166復習）

AtCoder

5月3日に開催されたAtCoder Beginner Contest 166。

本番ではACできなかったC問題にチャレンジ。

各問題の制約や入力・出力例はリンク先（AtCoderのサイト）へ。

C - Peaks

問題文
AtCoder丘陵には N 個の展望台があり、展望台 i の標高は Hi です。 また、異なる展望台どうしを結ぶ M 本の道があり、道 j は展望台 Aj と展望台 Bj を結んでいます。
展望台 i が良い展望台であるとは、展望台 i から一本の道を使って辿り着けるどの展望台よりも展望台 i の方が標高が高いことをいいます。 展望台 i から一本の道を使って辿り着ける展望台が存在しない場合も、展望台 i は良い展望台であるといいます。
良い展望台がいくつあるか求めてください。

入力
入力は以下の形式で標準入力から与えられる。
N M
H1 H2 ... HN
A1 B1
A2 B2
:
AM BM

C - Peaks

ACコード

正解者の方々のコードをいくつか見た後に自分なりに書いたコード。

n, m = gets.to_s.split.map(&:to_i)
h = [0] + gets.to_s.split.map(&:to_i)
ans = [0] + [1] * n

m.times do
  a, b = gets.split.map(&:to_i)
  if h[a] < h[b]
    ans[a] = 0
  elsif h[a] > h[b]
    ans[b] = 0
  else
    ans[a] = 0
    ans[b] = 0
  end
end
puts ans.sum

実行時間：153 ms

考えたことを言語化してみる

1行目：標準入力値を取得して多重代入

2行目：配列hに、標準入力値（標高）を代入（インデックス番号が合うように頭に[0]を入れておく）

3行目：配列ansを作る（最終的にans.sumで答えが求められるよう、あらかじめ 1 を n 個分入れ、インデックス番号が合うように頭に[0]を入れておく）

5行目〜（繰り返し処理）
（5行目）do 〜 endを m回繰り返す （6行目）標準入力値を整数にして a, b それぞれに代入
（7行目）h[a] より h[b] が大きかったら、ans[a] に 0 を代入
（9行目）h[a] より h[b] が小さかったら、ans[b] に 0 を代入
（11行目）h[a] とh[b] が等しかったら、ans[a] とans[b] に 0 を代入
（最終行）ans.sum を出力

コードを書きながら、「結局何を出力するんだっけ？」となることがたまにある。

一つの入力に対して一つの答えを出力するものや、条件を満たすものの番号を答えるものなどいろいろな問題がある。

今回は、個数を回答する問題の解き方を一つ学んだ。

あらかじめ変数（今回の例ではans）を作っておいて、それが求める数になるようにコードを書いていくというやり方。

感想

アルゴリズム実技検定ができなかったのが悔しくて、やっぱりもう一段階ぐらいは上がりたいので、これまで挑戦してできなかった問題からつぶしていく。