AtCoder Beginner Contest404振り返り

結果はAC完答でパフォーマンス475、新Rating364（+12）でした。 B問題に手こずってしまいました。 回転する操作を行う回数が 0,1,2,3 回のいずれであるかを 4 通り全て試すことで解くことができたのですが、複雑に考えてしまいその方針に辿りつけませんでした。

B問題　解答

atcoder.jp

回転数が0〜3回の場合でループを回し、まずカウントを行いそのあとで回転をさせています。 ９０度回転の実装は、移動後の配列nsを用意してns[j][n - 1 - i] = s[i][j]で元の位置を記録しています。 回転の実装をどうするか本番中に悩んでいたので、このやり方を覚えておきたいと思います。

n = gets.to_i
s = Array.new(n) { gets.chomp }
t = Array.new(n) { gets.chomp }
ans = 1001001001
4.times do |ri|
  now = ri
  n.times do |i|
    n.times do |j|
      now += 1 if s[i][j] != t[i][j]
    end
  end
  ans = [ans, now].min

  ns = Array.new(n) { Array.new(n) }
  n.times do |i|
    n.times do |j|
      ns[j][n - 1 - i] = s[i][j]
    end
  end
  ns.map! { |row| row.join }
  s = ns
end
puts ans

AtCoder Beginner Contest401振り返り

AtCoder ABC401振り返り

結果はAB2完、パフォーマンス252、新Rating339（△11）でした。 C問題はAnを配列の合計値を都度求める方法をイメージしましたが、TLEにならないような工夫の効いた効率の良い方法を思いつくことができませんでした。 回答案を見るとコード量が少なくシンプルに実装できるとわかりました。 全体の計算量はO(n)になるようです。Geminiに質問したらs -= a[i - k]やs += a[i] はインデックスを直接指定するためO(1)の操作になるのですね。正確に計算量見積もりができるようになりたいです。 また来週。

C問題　解答

atcoder.jp

n, k = gets.split.map(&:to_i)
s = k # s: An-k + ... +An-1　sをkで初期化
a = Array.new(n+1, 1) # 長さn+1、要素は全て1の配列を用意
# Ak~Anを求める
(k..n).each do |i|
  a[i] = s # a[i]はsになる
  # sを更新
  s -= a[i - k] # sの先頭を削除
  s += a[i] # sの最後尾を追加
  s %= 1000000000
end
puts a[n]

AtCoder Beginner Contest399振り返り

AtCoder ABC399振り返り

ABC3完。パフォーマンス544。新Rating350（+21）。

C問題

atcoder.jp

連結成分をBFSで求める実装。 過去問でやっていたのでほぼそのまま。

#!/usr/bin/env ruby
n, m = gets.split.map(&:to_i)

# bfs
to = Array.new(n){[]} # 各頂点の隣接している頂点
m.times do
  a, b = gets.split.map{ |x| x.to_i - 1 }
  to[a].push(b)
  to[b].push(a)
end

visited = Array.new(n, false) # 訪問済みを管理する配列
def bfs(sv, to, visited)
  queue = [sv] # キューにスタートする頂点を入れる
  visited[sv] = true # その頂点を訪問済みにする
  until queue.empty? # キューに頂点がある限り
    v = queue.shift # キューの先頭を取り出す
    to[v].each do |u| # 取り出した頂点の隣接頂点を見ていく
      next if visited[u] # 訪問済みの頂点ならスキップ
      queue.push(u) # 未訪問であればキューに追加し、
      visited[u] = true # 訪問済みにする
    end
  end
end

x = 0 # 連結成分数
n.times do |v| # 各頂点を見ていく
  next if visited[v] # 訪問済みならスキップ
  bfs(v, to, visited)
  x += 1 # 連結成分をカウント
end
# 森となる必要な辺の数 = 頂点-連結成分 = n-x
# 答え（削除する辺の数） = 現状の辺の数-必要な辺の数 = m - (n-x)
puts m - n + x

グラフ理論メモ

• 単純無向グラフ

自己ループ（ある頂点からそれ自身への辺）や多重辺（同じ2つの頂点間に複数の辺が存在すること）をもたないグラフ

• サイクル

グラフの辺をいくつか辿っていくと、出発した頂点に再び戻ってこられる経路のこと。

• 木

連結でサイクルを持たないグラフ。辺の数は 頂点数 - 1 。連結成分の数は 1 。

• 森

サイクルを持たないグラフ（各連結成分が木である）。森全体の辺の数は 頂点数 - 連結成分の数

AtCoder Beginner Contest398振り返り

AtCoder ABC398振り返り

ABC3完。パフォーマンス339。新Rating329（+1）。 コンテスト開始前にPCの環境を整えるのに手間取って10分ロスしてしまった。 またB問題でコード修正を保存せずに提出してしまってペナルティをくらった。 ちょっと緩んでますね、、

B問題（bit全探索での実装）

atcoder.jp bit全探索はたまに触れないと忘れてしまうな。

#!/usr/bin/env ruby
def is_full(b)
  b.sort!
  return true if b[0] == b[1] && b[1] == b[2] && b[2] != b[3] && b[3] == b[4]
  return true if b[0] == b[1] && b[1] != b[2] && b[2] == b[3] && b[3] == b[4]
  false
end

a = gets.split.map(&:to_i)
# bit全探索　各7枚のカードにつき選ぶ、選ばれないで2通りなので2^7通り
(0..(1 << 7) - 1).each do |i| # 0~127の整数を列挙
  b = []
  (0..6).each do |j| # iについて選ばれている場所を確認
    b << a[j] if (i & (1 << j)) > 0
  end

  if b.size == 5 # カードがちょうど5枚選ばれる場合
    if is_full(b)
      puts "Yes"
      exit
    end
  end
end

puts "No"

C問題

atcoder.jp 提出コードではわざわざハッシュにto_aをして変換していた。 ハッシュにselectできるのね。

#!/usr/bin/env ruby
n = gets.to_i
a = gets.split.map(&:to_i)
h = Hash.new{ |h, k| h[k] = [] }
a.each_with_index do |v, i|
  i += 1
  h[v] << i
end
uniq_numbers = h.select { |num, person| person.size == 1 }
if uniq_numbers.empty?
  puts -1
else
  max_number = uniq_numbers.keys.max
  puts uniq_numbers[max_number]
end

終わりに

最近英語学習に時間を注ぎたいのもあって、今月はコンテストのみ参加していて日頃の練習をやめている。C問題の正答率は上がっているが、これからは早解き練習をしないとレーティングは上がらなそう。ようやく400が見えてきているし頑張りたいところ。日頃の学習時間の時間配分を見直さないといけない。

AtCoder Beginner Contest397振り返り

AtCoder ABC397振り返り

C問題撃破。パフォーマンス443。新Rating328（+12）。 自身最高レーティング更新。

C問題

atcoder.jp

提出コード

n = gets.to_i
a = gets.split.map(&:to_i)
len = a.size
set1 = Set.new
cb1 = []
set2 = Set.new
cb2 = []
(0..len-2).each do |i|
  cb1 << set1.add(a[i]).size
end
(len-1).downto(1) do |i|
  cb2 << set2.add(a[i]).size
end
cb2.reverse!

ans = 0
(0..cb1.size-1).each do |i|
  ans = [ans, (cb1[i] + cb2[i])].max
end
puts ans

リファクタ

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

numl = [0] * (n + 1)
numr = [0] * (n + 1)

st = Set.new
(0...n).each do |i|
  st.add(a[i])
  numl[i + 1] = st.size
end

st = Set.new
(n - 1).downto(0).each do |i|
  st.add(a[i])
  numr[i] = st.size
end

ans = 0
(1...n).each do |i|
  ans = [ans, numl[i] + numr[i]].max
end

puts ans

レーティング400が見えてきたけどまだまだ遠いな、、 気長に楽しんで続けよう。

AtCoder Beginner Contest396振り返り

AtCoder ABC396振り返り

C問題撃沈。パフォーマンス322。新Rating316（+0）。 C問題は降順ソート、累積和は分かったのだけど、2重ループの計算量を削減する実装ができなかった。 解説動画を見て納得。

C問題

atcoder.jp

解答

n, m = gets.split.map(&:to_i)
b = gets.split.map(&:to_i).sort.reverse
w = gets.split.map(&:to_i).sort.reverse
ans = 0
sumb = 0
sumw = 0
maxw = 0
(0..n-1).each do |i|
  sumb += b[i]
  sumw += w[i] if i < m
  maxw = [sumw, maxw].max
  ans = [ans, sumb+maxw].max
end
puts ans

AtCoder Beginner Contest395振り返り

AtCoder ABC395振り返り

ABC3完。パフォーマンス441。新Rating316（+13）。 D問題でまた鳩の問題だったから笑った。問題作成者は鳩好きなのかな？ 前回の鳩問題を経験していたので、全く太刀打ちできない訳ではなかったものの、解ききれなかった。

D問題

atcoder.jp

p2b：ハトからバッグの場所がわかる

b2h：バッグから巣の場所がわかる

h2b：巣からバッグの場所がわかる

これらを管理して解く。これをすぐに思いつける人はすごい。

解答

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

p2b = Array.new(n) { |i| i }
b2h = Array.new(n) { |i| i }
h2b = Array.new(n) { |i| i }

q.times do
  type, a, b = gets.split.map(&:to_i)
  a -= 1
  b -= 1 if b

  case type
  when 1
    p2b[a] = h2b[b]
  when 2
    h2b[a], h2b[b] = h2b[b], h2b[a]
    b2h[h2b[a]] = a
    b2h[h2b[b]] = b
  when 3
    ans = b2h[p2b[a]]
    puts ans + 1
  end
end

ひとこと

2月は毎日 ACした。コンテストでのC問題の正答率も上がってきているので成果が出てきていると思う。

• streak 31
• Accept数 314