Zenn
📚

yukicoder contest 362 参加記

2022/09/30に公開
yukicoder
idea

https://yukicoder.me/contests/405

8 位でした！

A - A+B問題

やるだけ。なぜか入力が複数行形式なので気をつける。

2nd でした。くやしい。

↓書きたかったコード

A = gets.to_i
B = gets.to_i
puts A + B

↓現実

A = gets
B = gets
puts A.to_i + B.to_i

B - 基数の変換

Ruby ならやるだけ。また複数行形式だけど、これは C な言語を使い手の人への配慮なのだろうか？

1st でした。やった！
コードは以下の通り。

N = gets.to_i
M = gets.to_i
puts M.to_s(N)

Ruby だと Integer#to_s(base) で base 進数への変換ができますね。

C - 数当てゲーム

数当てゲームって、二分探索か？と思ったら全然違いました……。
なんか変な WA を繰り返してしまったのであほです。

  1. 1.0 を 1/0 と書き間違えて RE
  2. puts - B が (puts) - (B) と解釈されて RE
  3. 浮動小数点形式で出力したら WA

x と Ax + B が等しくなるようにすればいいので、つまり:

  • A = 1 のときは x は任意の整数（ここで B は必ず 0 になる）
  • A \ne 1 のときは x = \frac{B}{1 - A}

書きたかったコードは以下の通り。

A = gets.to_i
B = gets.to_i
if A == 1
  puts 1333
else
  puts B / (1 - A)
end
現実？
A = gets.to_i
B = gets.to_i
if A == 1
    if B == 0
        puts 1
        exit
    else
        puts -1
        exit
    end
end
puts -B / (A - 1)

D - 置換の符号

転倒数の偶奇と勘違いして 1 ペナ。置換の符号ってなんだっけ？

なんか試してみると、偶数頂点のサイクルは奇数個の互換、奇数頂点のサイクルは偶数個の互換からつくれるっぽい。
置換のグラフは必ずいくつかのサイクルに分解できるので、それぞれのサイクルごとに互換の個数を足したものが全体の互換の数になる。

なのでグラフを構築して DFS 、偶数頂点のサイクルの数が奇数なら -1 、偶数なら 1 が答えになる。

こうしたかったコード

N = gets.to_i
A = gets.split.map(&:to_i)

graph = Array.new(N) { [] }
N.times do |u|
  v = A[u]
  graph[u] << v
  graph[v] << u
end

ans = 1
visited = [false] * N
stack = []
N.times do |s|
  next if visited[s]
  visited[s] = true
  stack << s
  count = 0
  while (u = stack.pop)
    count += 1
    graph[u].each do |v|
      next if visited[v]
      visited[v] = true
      stack << v
    end
  end
  ans *= -1 if count.odd?
end

puts ans
現実？
N = gets.to_i
A = gets.split.map(&:to_i)

graph = Array.new(N) { [] }
N.times do |u|
    v = A[u] - 1
    graph[u] << v
    graph[v] << u
end

count = 0
visited = [false] * N
N.times do |s|
    next if visited[s]
    visited[s] = true
    count += 1
    stack = [s]
    while (u = stack.pop)
        count += 1
        graph[u].each do |v|
            next if visited[v]
            visited[v] = true
            stack << v
        end
    end
end

puts count.even? ? 1 : -1

E - 否定論理積と充足可能性

え、要するに P_{A_0} | P_{A_1} | P_{A_2} | P_{A_3} | P_{A_4} | P_{A_5} のことだよね？これが充足しないってことある？
サンプルケースも全部 YES だな！全部大文字ヨシ！ YES を Text 提出ヨシ！
…… WA（そんなぁぁぁぁぁあぁ）

↑これは問題文をちゃんと読まなかった人の末路です

この問題では (x | y) が \overline{ x \wedge y } を指すらしい。えー？シェファーの棒記号なんて聞いたことねーよ！
は？面白くね―――！逆に一周回って面白え――！

真面目に、座圧して bit 全探索をしました。
はい。

A = gets.split.map(&:to_i)

B = A.uniq.sort
a = A.map { B.index(_1) }

(1 << a.size).times do |bits|
    p, q, r, s, t, u = a.map { bits[_1] == 1 }
    if !(!(!(p & q) & r) & !(!(s & t) & u))
        puts "YES"
        exit
    end
end

puts "NO"

はいじゃないが。

Discussion