【AtCoder:16回目】第一回日本最強プログラマー学生選手権-予選-の振り返り（Ruby）

【目次】

【本題】

振り返り

今回は 8/24(土)に開催された第一回日本最強プログラマー学生選手権-予選-の振り返りを行います。

Japanese Student Championship 2019 Qualification - AtCoder

今回は1問しか回答出来ませんでした・・・

レーティング微増

A - Takahashi Calendar

問題文 今日は 8 月 24 日、年に 5 日しかない積の日です。

d が 2 桁の整数で、 d の 1 の位を d 1 、 10 の位を d 10 としたときに m , d 1 , d 10 が次の条件をすべて満たす場合、 m 月 d 日を積の日と呼びます。

d 1 ≥ 2 d 10 ≥ 2 d 1 × d

10

m 高橋くんはこの日をもっと増やしたいと考え、 1 年が 1 月から M 月までの合計 M ヶ月、どの月も 1 日から D 日までの合計 D 日からなる高橋暦を誕生させました。

高橋暦において、積の日は年に何日あるでしょうか。

制約 入力は全て整数である。 1 ≤ M ≤ 100 1 ≤ D ≤ 99

最大で100*99通りなので、全探索でも行けそうですね

１から順に繰り返す場合はuptoメソッドが最適です。

各桁の数値は、to_sで文字列に変換すれば、str[n]という形式で求めることが出来ます。

私の回答は以下の通りです。

m,d = gets.split.map(&:to_i)

count = 0``
1.upto(m) do |mm|
  1.upto(d) do |dd|
    next if dd < 11
    d10,d1 = dd.to_s.split('')
    next if d10.to_i < 2 || d1.to_i < 2
    count += 1 if mm == d10.to_i * d1.to_i
  end
end

puts count

なお、各桁の数値は、その位の剰余で求めることも出来ます（10の位であれば%10の様に）

なので、以下の様に書くことも出来ます。

m,d=gets.split.map(&:to_i)
count = 0
1.upto(m) do |i|
  1.upto(d) do |j|
    count += 1 if j % 10 >= 2 && j / 10 >= 2 && i == (j % 10) * (j / 10)
  end
end
p count

B - Kleene Inversion

問題文 長さ N の整数列 A

=

A 0 ,

A 1 ,

. . . ,

A N − 1 があります。

A を K 回繰り返した長さ K × N の整数列を B とします。たとえば A

=

1 ,

3 ,

2 、 K

=

2 のとき、 B

=

1 ,

3 ,

2 ,

1 ,

3 ,

2 です。

B の転倒数を 10 9 + 7 で割った余りを求めてください。

ここで B の転倒数は、整数の順序対 ( i ,

j )

( 0 ≤ i < j ≤ K × N − 1 ) であって B i

B j を満たすものの個数として定義されます。

制約 入力は全て整数である。 1 ≤ N ≤ 2000 1 ≤ K ≤ 10 9 1 ≤ A i ≤ 2000

最大で2*10の12乗パターンがあるので、全探索は厳しそうです・・・

Aの各要素だけに絞れば2000通りなので、これは全探索でチェックをして、それを基にK回繰り返したパターンも導き出そうとしましたが、以下まで書いたところで時間切れでした・・・

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

group = a.group_by { |i| i }
bit = Array.new(a.max, 0)
group.each do |kk, v|
  bit[kk-1] = v.size
end

save = []
count = 0
a.each do |num|
  count += save.count { |i| i < num }
  save << num
end

最終的に完成させたコードがこちらです。

n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
l = Array.new(n, 0)
r = Array.new(n, 0)

(n - 1).times do |i|
  (i + 1).upto(n - 1) do |j|
    if a[i] > a[j]
      r[i] += 1
    elsif a[i] < a[j]
      l[j] += 1
    end
  end
end

r[n - 1] = 0
l[0] = 0
count = 0
n.times do |i|
  count += r[i] * (k * (k + 1) / 2) + l[i] * ((k - 1) * k / 2)
end
puts count % 1000000007