[Ruby] AtCoder過去問 C - Count Order

はじめに

AtCoder過去問のC問題を解いてみました。
よろしくお願いします。

問題はこちらから確認してください↓

C - Count Order

とりあえず入力を受け取ります。

n = gets.to_i
p_ary = gets.split.map(&:to_i)
q_ary = gets.split.map(&:to_i) 

さて、どうしたもんかと、組み合わせの配列をどうやって作ろうかめちゃめちゃ悩みました。
しかし、しっかりrubyには便利なメソッドが準備されていました。
それがpermutationメソッドです。

配列の組み合わせを返してくれます。array.permutation(n).to_aという形で記述すると配列の中にそれぞれのパターンが配列として出来上がります。
例[[1, 2, 3], [1, 3, 2], [2, 1, 3]...]
こんな感じです。

引数に対象とする数を指定します。今回の場合は全てなのでnでオッケーです。

ここで気をつけたいことで、問題では辞書順にしなければなりません。
例えば、入力例1のpをpermutationにかけても全てのパターンを返してくれますが、辞書順になりません。

私は偶然気付いたのですが、これ、sortで昇順に並び替えてからpermutationをかけると辞書順に並んで返ってくるのです。

ここまでをコードにおこしてみます。

n = gets.to_i
p_ary = gets.split.map(&:to_i)
q_ary = gets.split.map(&:to_i) 

p_permu = p_ary.sort.permutation(n).to_a

q_permu = p_ary.sort.permutation(n).to_a

これでpとqそれぞれの全てのパターンが入った配列が完成しました。
p_permuとq_permuと名前にしています。相変わらず命名下手くそです。

さて、次はp_aryとq_aryが辞書順の何番目にあるかを知りたいです。
つまりp_permuとq_permuの何番目かわかれば良いです。

indexメソッドを使いましょう。これめちゃめちゃ便利。
indexはインデックス番号で返してくるので+1してあげます。

n = gets.to_i
p_ary = gets.split.map(&:to_i)
q_ary = gets.split.map(&:to_i) 

p_permu = p_ary.sort.permutation(n).to_a

q_permu = p_ary.sort.permutation(n).to_a

a = p_permu.index(p_ary) + 1

b = q_permu.index(q_ary) + 1

あとはa-bをして、absメソッドで絶対値にして出力で完成です。

n = gets.to_i
p_ary = gets.split.map(&:to_i)
q_ary = gets.split.map(&:to_i) 

p_permu = p_ary.sort.permutation(n).to_a

q_permu = p_ary.sort.permutation(n).to_a

a = p_permu.index(p_ary) + 1

b = q_permu.index(q_ary) + 1

puts (a-b).abs